C++作业题

Solved Flags ID Title 1191  A   The Worm Turns 1312  B   The Game 1720  C   Brainman 1823  D   Cantoring Along 2556  E   Football Foundation (FOFO) 2967  F   Eazzzzzy Worm is an old computer game. There are many versions, but all involve maneuvering a "worm" around the screen, trying to avoid running the worm into itself or an obstacle. We'll simulate a very simplified version here. The game will be played on a 50 x 50 board, numbered so that the square at the upper left is numbered (1, 1). The worm is initially a string of 20 connected squares. Connected squares are adjacent horizontally or vertically. The worm starts stretched out horizontally in positions (25, 11) through (25, 30), with the head of the worm at (25, 30). The worm can move either East (E), West (W), North (N) or South (S), but will never move back on itself. So, in the initial position, a W move is not possible. Thus the only two squares occupied by the worm that change in any move are its head and tail. Note that the head of the worm can move to the square just vacated by the worm's tail. You will be given a series of moves and will simulate the moves until either the worm runs into itself, the worm runs off the board, or the worm successfully negotiates its list of moves. In the first two cases you should ignore the remaining moves in the list. Input There will be multiple problems instances. The input for each problem instance will be on two lines. The first line is an integer n (<100) indicating the number of moves to follow. (A value of n = 0 indicates end of input.) The next line contains n characters (either E, W, N or S), with no spaces separating the letters, indicating the sequence of moves. Output Generate one line of output for each problem instance. The output line should be one of the follow three: The worm ran into itself on move m. The worm ran off the board on move m. The worm successfully made all m moves. Where m is for you to determine and the first move is move 1. Sample Input 18 NWWWWWWWWWWSESSSWS 20 SSSWWNENNNNNWWWWSSSS 30 EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE 13 SWWWWWWWWWNEE 0 Sample Output The worm successfully made all 18 moves. The worm ran into itself on move 9. The worm ran off the board on move 21. The worm successfully made all 13 moves. Source:  East Central North America 2001 Practice Problem ID in problemset: 1191 A game of Renju is played on a 19 X 19 board by two players. One player uses black stones and the other uses white stones. The game begins in an empty board and two players alternate in placing black stones and white stones. Black always goes first. There are 19 horizontal lines and 19 vertical lines in the board and the stones are placed on the intersections of the lines. Horizontal lines are marked 1, 2, ..., 19 from up to down and vertical lines are marked 1, 2, ..., 19 from left to right. The objective of this game is to put five stones of the same color consecutively along a horizontal, vertical, or diagonal line. So, black wins in the above figure. But, a player does not win the game if more than five stones of the same color were put consecutively. Given a configuration of the game, write a program to determine whether white has won or black has won or nobody has won yet. There will be no input data where the black and the white both win at the same time. Also there will be no input data where the white or the black wins in more than one place. Input The first line of the input file contains a single integer t (1 ≤ t ≤ 11), the number of test cases, followed by the input data for each test case. Each test case consists of 19 lines, each having 19 numbers. A black stone is denoted by 1, a white stone is denoted by 2, and 0 denotes no stone. Output There should be one or two line(s) per test case. In the first line of the test case output, you should print 1 if black wins, 2 if white wins, and 0 if nobody wins yet. If black or white won, print in the second line the horizontal line number and the vertical line number of the left-most stone among the five consecutive stones. (Select the upper-most stone if the five consecutive stones are located vertically.) Sample Input 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Sample Output 1 3 2 Source:  Tehran 2004 Iran Nationwide Problem ID in problemset: 1312 C.   Brainman Time Limit: 1.0 Seconds   Memory Limit: 65536K Raymond Babbitt drives his brother Charlie mad. Recently Raymond counted 246 toothpicks spilled all over the floor in an instant just by glancing at them. And he can even count Poker cards. Charlie would love to be able to do cool things like that, too. He wants to beat his brother in a similar task. Here's what Charlie thinks of. Imagine you get a sequence of N numbers. The goal is to move the numbers around so that at the end the sequence is ordered. The only operation allowed is to swap two adjacent numbers. Let us try an example: Start with: 2 8 0 3 swap (2 8) 8 2 0 3 swap (2 0) 8 0 2 3 swap (2 3) 8 0 3 2 swap (8 0) 0 8 3 2 swap (8 3) 0 3 8 2 swap (8 2) 0 3 2 8 swap (3 2) 0 2 3 8 swap (3 8) 0 2 8 3 swap (8 3) 0 2 3 8 So the sequence (2 8 0 3) can be sorted with nine swaps of adjacent numbers. However, it is even possible to sort it with three such swaps: Start with: 2 8 0 3 swap (8 0) 2 0 8 3 swap (2 0) 0 2 8 3 swap (8 3) 0 2 3 8 The question is: What is the minimum number of swaps of adjacent numbers to sort a given sequence?Since Charlie does not have Raymond's mental capabilities, he decides to cheat. Here is where you come into play. He asks you to write a computer program for him that answers the question. Rest assured he will pay a very good prize for it. Input The first line contains the number of scenarios. For every scenario, you are given a line containing first the length N (1 ≤ N ≤ 1000) of the sequence,followed by the N elements of the sequence (each element is an integer in [-1000000, 1000000]). All numbers in this line are separated by single blanks. Output Start the output for every scenario with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. Then print a single line containing the minimal number of swaps of adjacent numbers that are necessary to sort the given sequence. Terminate the output for the scenario with a blank line. Sample Input 4 4 2 8 0 3 10 0 1 2 3 4 5 6 7 8 9 6 -42 23 6 28 -100 65537 5 0 0 0 0 0 Sample Output Scenario #1: 3 Scenario #2: 0 Scenario #3: 5 Scenario #4: 0 Source:  TUD Programming Contest 2003 Problem ID in problemset: 1720 D.   Cantoring Along Time Limit: 1.0 Seconds   Memory Limit: 65536K The Cantor set was discovered by Georg Cantor. It is one of the simpler fractals. It is the result of an infinite process, so for this program, printing an approximation of the whole set is enough. The following steps describe one way of obtaining the desired output for a given order Cantor set: 1. Start with a string of dashes, with length 3order 2. Replace the middle third of the line of dashes with spaces. You are left with two lines of dashes at each end of the original string. 3. Replace the middle third of each line of dashes with spaces. Repeat until the lines consist of a single dash. For example, if the order of approximation is 3, start with a string of 27 dashes: --------------------------- Remove the middle third of the string: --------- --------- and remove the middle third of each piece: --- --- --- --- and again: - - - - - - - - The process stops here, when the groups of dashes are all of length 1. You should not print the intermediate steps in your program. Only the final result, given by the last line above, should be displayed. Input Each line of input will be a single number between 0 and 12, inclusive, indicating the order of the approximation. The input stops when end-of-file is reached. Output You must output the approximation of the Cantor set, followed by a newline. There is no whitespace before or after your Cantor set approximation. The only characters that should appear on your line are '-' and ' '. Each set is followed by a newline, but there should be no extra newlines in your output. Sample Input 0 1 3 2 Sample Output - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -1 3 1 9 1 3 1 27 1 3 1 9 1 3 1 - - - - - - - - - - - - - - - -1 3 1 9 1 3 1 27 1 3 1 9 1 3 1 81 1 3 1 9 1 3 1 27 1 3 1 9 1 3 1 - - - - - - - - - - - - - - - - urce:  Mid Atlantic North America 2002 Problem ID in problemset: 1823 E.   Football Foundation (FOFO) Time Limit: 0.5 Seconds   Memory Limit: 65536K The football foundation (FOFO) has been researching on soccer; they created a set of sensors to describe the ball behavior based on a grid uniformly distributed on the field. They found that they could predict the ball movements based on historical analysis. Each square sensor of the grid can detect the following patterns: N  north (up the field) S  south (south the field) E  east (to the right on the field) W  west (to the left on the field) For example, in grid 1, suppose the ball was thrown into the field from north side into the field. The path the sensors detected for this movement follows as shown. The ball went through 10 sensors before leaving the field. Comparing with what happened on grid 2, the ball went through 3 sensors only once, and started a loop through 8 instructions and never exits the field. You are selected to write a program in order to evaluate line judges job, with the following out put based on each grid of sensors, the program needs to determine how long it takes to the ball to get out of the grid or how the ball loops around. Input There will be one or more grids of sensors for the same game. The data for each is in the following form. On the first line are three integers separated by blanks: The number of rows in the grid, the number of columns in the grid, and the number of the column in which the ball enters from the north. The grid column's number starts with one at the left. Then come the rows of direction instructions. The lines of instructions contain only the characters N, S, E or W, with no blanks. The end of input is indicated by a grid containing 0 0 0 as limits. Output For each grid in the input there is one line of output. Either the ball follows a certain number of sensors and exits the field on any one of the four sides or else the ball follows the behavior on some number of sensors repeatedly. The sample input below corresponds to the two grids above and illustrates the two forms of output. The word "step" is always immediately followed by "(s)" whether or not the number before is 1. Sample Input 3 6 5 NEESWE WWWESS SNWWWW 4 5 1 SESWE EESNW NWEEN EWSEN 0 0 0 Sample Output 10 step(s) to exit 3 step(s) before a loop of 8 step(s) Source:  Mexico and Central America 2006 Problem ID in problemset: 2556 F.   Eazzzzzy Time Limit: 1.0 Seconds   Memory Limit: 65536K Draw triangle, parallelogram and rectangle. * **** **** *** **** **** ***** **** **** ******* **** **** ********* **** **** Triangle (5) Parallelogram (4x5) Rectangle (4x5) In the above figure between first brackets the dimension is given. For triangle the height will be given, for parallelogram and rectangle the width and height will be given. The character dot ('.') in the above figure will be represented by ASCII character space in the output. Input First line of each input set indicates category C. If C=1 it is a triangle. Then following line of input indicates the height H ranging 1≤H≤10. If C=2 it is a parallelogram. Then following line of input have two integers width W and height H ranging 1≤W≤10 and 1≤H≤10. If C=3 it is a rectangle. Then following line of input have two integers width W and height H ranging 1≤W≤10 and 1≤H≤10. C= -1 indicates the end of input set. This will not be considered as input. Output Output will be drawn by character '*' as following. Print a blank line after each output. Sample input 1 5 2 5 3 3 4 6 -1 Sample output: * *** ***** ******* ********* ***** ***** ***** **** **** **** **** **** **** Problem Setter: MD. Nazmul Kibria. Source:  CUET Easy Contest Problem ID in problemset: 2967