SSSTA十一假期算法组训练赛.doc

SSSTA十一假期算法组训练赛A - No BrainerCrawling in process. Crawling failed Time Limit:1000MS Memory Limit:30000KB 64bit IO Format:%I64d & %I64u Submit Status DescriptionZombies love to eat brains. Yum.InputThe first line contains a single integer n indicating the number of data sets. The following n lines each represent a data set. Each data set will be formatted according to the following description: A single data set consists of a line X Y, where X is the number of brains the zombie eats and Y is the number of brains the zombie requires to stay alive. OutputFor each data set, there will be exactly one line of output. This line will be MMM BRAINS if the number of brains the zombie eats is greater than or equal to the number of brains the zombie requires to stay alive. Otherwise, the line will be NO BRAINS. Sample Input34 53 34 3Sample OutputNO BRAINSMMM BRAINSMMM BRAINSB - Financial ManagementCrawling in process. Crawling failed Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u Submit Status DescriptionLarry graduated this year and finally has a job. Hes making a lot of money, but somehow never seems to have enough. Larry has decided that he needs to grab hold of his financial portfolio and solve his financing problems. The first step is to figure out whats been going on with his money. Larry has his bank account statements and wants to see how much money he has. Help Larry by writing a program to take his closing balance from each of the past twelve months and calculate his average account balance. InputThe input will be twelve lines. Each line will contain the closing balance of his bank account for a particular month. Each number will be positive and displayed to the penny. No dollar sign will be included. OutputThe output will be a single number, the average (mean) of the closing balances for the twelve months. It will be rounded to the nearest penny, preceded immediately by a dollar sign, and followed by the end-of-line. There will be no other spaces or characters in the output. Sample Input100.00489.1212454.121234.10823.05109.205.271542.25839.1883.991295.011.75Sample Output$1581.42C - Stump RemovalCrawling in process. Crawling failed Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status DescriptionAlways thinking of the cows grazing experience, FJ has found that he must remove N (1 = N = 50,000) unsightly stumps from the pasture. The stumps are conveniently arranged in a straight line and numbered 1.N with each stump having some height H_i (1 = H_i 0) specifying the number of cases to follow. Each case consists of three lines of input, one for each weighing. Sally has identified each of the coins with the letters A-L. Information on a weighing will be given by two strings of letters and then one of the words up, down, or even. The first string of letters will represent the coins on the left balance; the second string, the coins on the right balance. (Sally will always place the same number of coins on the right balance as on the left balance.) The word in the third position will tell whether the right side of the balance goes up, down, or remains even. OutputFor each case, the output will identify the counterfeit coin by its letter and tell whether it is heavy or light. The solution will always be uniquely determined. Sample Input1 ABCD EFGH even ABCI EFJK up ABIJ EFGH even Sample OutputK is the counterfeit coin and it is light. E - BlocksCrawling in process. Crawling failed Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u Submit Status DescriptionDonald wishes to send a gift to his new nephew, Fooey. Donald is a bit of a traditionalist, so he has chosen to send a set of N classic baby blocks. Each block is a cube, 1 inch by 1 inch by 1 inch. Donald wants to stack the blocks together into a rectangular solid and wrap them all up in brown paper for shipping. How much brown paper does Donald need? InputThe first line of input contains C, the number of test cases. For each case there is an additional line containing N, the number of blocks to be shipped. N does not exceed 1000.OutputYour program should produce one line of output per case, giving the minimal area of paper (in square inches) needed to wrap the blocks when they are stacked together.Sample Input59102627100Sample Output30348254130F - IP AddressCrawling in process. Crawling failed Time Limit:1000MS Memory Limit:30000KB 64bit IO Format:%I64d & %I64u Submit Status DescriptionSuppose you are reading byte streams from any device, representing IP addresses. Your task is to convert a 32 characters long sequence of 1s and 0s (bits) to a dotted decimal format. A dotted decimal format for an IP address is form by grouping 8 bits at a time and converting the binary representation to decimal representation. Any 8 bits is a valid part of an IP address. To convert binary numbers to decimal numbers remember that both are positional numerical systems, where the first 8 positions of the binary systems are: 27 26 25 24 23 22 21 20 128 64 32 16 8 4 2 1 InputThe input will have a number N (1=N=9) in its first line representing the number of streams to convert. N lines will follow. OutputThe output must have N lines with a doted decimal IP address. A dotted decimal IP address is formed by grouping 8 bit at the time and converting the binary representation to decimal representation. Sample Input400000000000000000000000000000000 00000011100000001111111111111111 11001011100001001110010110000000 01010000000100000000000000000001 Sample Output0.0.0.03.128.255.255203.132.229.12880.16.0.1G - 生日蛋糕Crawling in process. Crawling failed Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u Submit Status Description7月17日是Mr.W的生日，ACM-THU为此要制作一个体积为N的M层生日蛋糕，每层都是一个圆柱体。 设从下往上数第i(1 = i = M)层蛋糕是半径为Ri, 高度为Hi的圆柱。当i Ri+1且Hi Hi+1。 由于要在蛋糕上抹奶油，为尽可能节约经费，我们希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。 令Q = S 请编程对给出的N和M，找出蛋糕的制作方案（适当的Ri和Hi的值），使S最小。 （除Q外，以上所有数据皆为正整数） Input有两行，第一行为N（N = 10000），表示待制作的蛋糕的体积为N；第二行为M(M = 20)，表示蛋糕的层数为M。Output仅一行，是一个正整数S（若无解则S = 0）。Sample Input1002Sample Output68Hint圆柱公式 体积V = R2H 侧面积A = 2RH 底面积A = R2 H - RobotCrawling in process. Crawling failed Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u Submit Status DescriptionThe Robot Moving Institute is using a robot in their local store to transport different items. Of course the robot should spend only the minimum time necessary when travelling from one place in the store to another. The robot can move only along a straight line (track). All tracks form a rectangular grid. Neighbouring tracks are one meter apart. The store is a rectangle N x M meters and it is entirely covered by this grid. The distance of the track closest to the side of the store is exactly one meter. The robot has a circular shape with diameter equal to 1.6 meter. The track goes through the center of the robot. The robot always faces north, south, west or east. The tracks are in the south-north and in the west-east directions. The robot can move only in the direction it faces. The direction in which it faces can be changed at each track crossing. Initially the robot stands at a track crossing. The obstacles in the store are formed from pieces occupying 1m x 1m on the ground. Each obstacle is within a 1 x 1 square formed by the tracks. The movement of the robot is controlled by two commands. These commands are GO and TURN. The GO command has one integer parameter n in 1,2,3. After receiving this command the robot moves n meters in the direction it faces. The TURN command has one parameter which is either left or right. After receiving this command the robot changes its orientation by 90o in the direction indicated by the parameter. The execution of each command lasts one second. Help researchers of RMI to write a program which will determine the minimal time in which the robot can move from a given starting point to a given destination. InputThe input consists of blocks of lines. The first line of each block contains two integers M = 50 and N = 50 separated by one space. In each of the next M lines there are N numbers one or zero separated by one space. One represents obstacles and zero represents empty squares. (The tracks are between the squares.) The block is terminated by a line containing four positive integers B1 B2 E1 E2 each followed by one space and the word indicating the orientation of the robot at the starting point. B1, B2 are the coordinates of the square in the north-west corner of which the robot is placed (starting point). E1, E2 are the coordinates of square to the north-west corner of which the robot should move (destination point). The orientation of the robot when it has reached the destination point is not prescribed. We use (row, column)-type coordinates, i.e. the coordinates of the upper left (the most north-west) square in the store are 0,0 and the lower right (the most south-east) square are M - 1, N - 1. The orientation is given by the words north or west or south or east. The last block contains only one line with N = 0 and M = 0. OutputThe output contains one line for each block except the last block in the input. The lines are in the order corresponding to the blocks in the input. The line contains minimal number of seconds in which the robot can reach the destination point from the starting point. If there does not exist any path from the starting point to the destination point the line will contain -1. Sample Input9 100 0 0 0 0 0 1 0 0 00 0 0 0 0 0 0 0 1 00 0 0 1 0 0 0 0 0 00 0 1 0 0 0 0 0 0 00 0 0 0 0 0 1 0 0 00 0 0 0 0 1 0 0 0 00 0 0 1 1 0 0 0 0 00 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 1 07 2 2 7 south0 0Sample Output12I - Square DestroyerCrawling in process.Crawling failedTime Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64uSubmitStatusDescriptionThe left figure below shows a complete 3*3 grid made with 2*(3*4) (=24) matchsticks. The lengths of all matchsticks are one. You can find many squares of different sizes in the grid. The size of a square is the length of its side. In the grid shown in the left figure, there are 9 squares of size one, 4 squares of size two, and 1 square of size three. Each matchstick of the complete grid is identified with a unique number which is assigned from left to right and from top to bottom as shown in the left figure. If you take some matchsticks out from the complete grid, then some squares in the grid will be destroyed, which results in an incomplete 3*3 grid. The right figure illustrates an incomplete 3*3 grid after removing three matchsticks numbered with 12, 17 and 23. This removal destroys 5 squares of size one, 3 squares of size two, and 1 square of size three. Consequently, the incomplete grid does not have squares of size three, but still has 4 squares of size one and 1 square of size two.As input, you are given a (complete or incomplete) n*n grid made with no more than 2n(n+1) matchsticks for a natural number 5 = n . Your task is to compute the minimum number of matchsticks taken out to destroy all the squares existing in the input n*n grid. InputThe input consists of T test cases. The number of test cases (T ) is given in the first line of the input file. Each test case consists of two lines: The first line contains a natural number n , not greater than 5, which implies you are given a (complete or incomplete) n*n grid as input, and the second line begins with a nonnegative integer k , the number of matchsticks that are missing from the complete n*n grid, followed by k numbers specifying the matchsticks. Note that if k is equal to zero, then the input grid is a complete n*n grid; otherwise, the input grid is an incomplete n*n grid such that the specified k matchsticks are missing from the complete n*n grid. OutputPrint exactly one line for each test case. The line should contain the minimum number of matchsticks that have to be taken out to destroy all the squares in the input grid. Sample Input22033 12 17 23Sample Output33J - Triangle WarCrawling in process.Crawling failedTime Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64uSubmitStatusDescriptionTriangle War is a two-player game played on the following triangular grid: Two players, A and B, take turns filling in any dotted line connecting two dots, with A starting first. Once a line is filled, it cannot be filled again. If the line filled by a player completes one or more triangles, she owns the completed triangles and she is awarded another turn (i.e. the opponent skips a turn). The game ends after all dotted lines are filled in, and the player with the most triangles wins the game. The difference in the number of triangles owned by the two players is not important. For example, if A fills in the line between 2 and 5 in the partial game on the left below: Then, she owns the triangle labelled A and takes another turn to fill in the line between 3 and 5. B can now own 3 triangles (if he wishes) by filling in the line between 2 and 3, then the one between 5 and 6, and finally the one between 6 and 9. B would then make one more move before it is As turn again. In this problem, you are given a number of moves that have already been made. From the partial game, you should determine which player will win assuming that each player plays a perfect game from that point on. That is, assume that each player always chooses the play that leads to the best possible outcome for himself/herself. InputYou will be given a number of games in the input. The first line of input is a positive integer indicating the number of games to follow. Each game starts with an integer 6 = m = 18 indicating the number of moves that have been made in the game. The next m lines indicate the moves made by the two players in order, each of the form i j (with i j) indicating that the line between i and j is filled in that move. You may assume that all given moves are legal. OutputFor each game, print the game number and the result on one line as shown below. If A wins, print the sentence A wins. If B wins, print B wins. Sample Input4 6 2 4 4 5 5 9 3 6 2 5 3 5 7 2 4 4 5 5 9 3 6 2 5 3 5 7 8 6 1 2 2 3 1 3 2 4 2 5 4 5 10 1 2 2 5 3 6 5 8 4 7 6 10 2 4 4 5 4 8 7 8 Sample OutputGame 1: B wins. Game 2: A wins. Game 3: A wins. Game 4: B wins.K - Heavy TransportationCrawling in process.Crawling failedTime Limit:3000MS Memory Limit:30000KB 64bit IO Format:%I64d & %I64uSubmitStatusDescriptionBackgroundHugo Heavy is happy. After the breakdown of the Cargolifter project he can now expand business. But he needs a clever man who tells him whether there really is a way from the place his customer has build his giant steel crane to the place where it is needed on which all streets can carry the weight.Fortunately he already has a plan of the city with all streets and bridges and all the allowed weights.Unfortunately he has no idea ho