2011年四川理工ACM程序设计竞赛试题.doc

2011年四川理工学院“达内杯”大学生程序设计竞赛试题1、Big integerProblem DescriptionCalculate the factorial of NInputInput a positive integer that less than 99.OutputThe factorial of NSample Input50Sample Output50! =304140932017133780436126081660647688443776415689605120000000000002、Look for treasuresProblem DescriptionThere are some treasures and one exit in the maze. People would consume his physical strength while he is walking, and he will resume some physical strength when he picks a treasure. Because of the limit of physical strength, John must plot his physical strength properly if he wants to walk out the maze and get all the treasures in the maze at the same time.Now, you would write a program to help John to solve the problem. Johns physical strength will decrease and if the physical strength is equal 0, he can not move.InputThe input file is named as “in.dat”, the content of this file is shown as follows:100 141 4 22 4 24 4 25 3 25 51 1 0 1 00 1 1 1 00 1 0 0 10 1 1 1 00 1 1 1 15 5The first line: the initializing physical strength of John and the consumed physical strength of each step.The second line: the total number of treasuresLine 3 to line N+2: there are 3 numbers at each line, the front two numbers is the coordinate of treasure: X,Y, the third number is the physical strength that John will get while he pick the treasure.The next line: the number of line and row (A,B, A,B=50) of the mazeThe next A lines: the map of the maze, the number 0 means it can not pass, and 1 means can pass (the position of treasures is mark with 1 at some place)The last line: the coordinate of exit (the coordinate of origin is (1,1) )OutputIf John can pick all of the treasures and walk out the maze, put out the remaining physical strength. On the other wise, put out “no, he can not”.Sample InputSample Output923、SnookerProblem DescriptionBackground: Philip likes to play the QQ game of Snooker when he wants a relax, though he was just a little vegetable-bird. Maybe you hadnt played that game yet, no matter, Ill introduce the rule for you first.There are 21 object balls on board, including 15 red balls and 6 color balls: yellow, green, brown, blue, pink, black.The player should use a white main ball to make the object balls roll into the hole, the sum of the balls fixed value he made in the hole is the players score. The player should firstly made a red ball into the hole, after that he gains red-balls value(1 points), then he gets the chance to make a color ball, then alternately. The color ball should be took out until all the red-ball are in the hole. In other word, if there are only color balls left on board, the player should hit the object balls in this order: yellow(2 point), green(3 point), brown(4 point), blue(5 point), pink(6 point), black(7 point), after the ball being hit into the hole, they are not get out of the hole, after no ball left on board, the game ends, the player who has the higher score wins the game. (PS: red object balls never get out of the hole.)I just illustrate the rules that maybe used.For example, if there are 12 red balls on board(if there are still red ball left on board, it can be sure that all the color balls must be on board either). So suppose Philp can continuesly hit the ball into the hole, he can get the maximun score is12 * 1 (12 red-ball in one shoot) + 7 * 12(after hit a red ball, a black ball which was the most valuable ball should be the target) + 2 + 3 + 4 + 5 + 6 + 7(when no red ball left, make all the color ball in hole).Now, your task is to judge whether Philip should make the decision to give up when telling you the condition on board(How many object balls still left not in the hole and the other players score). If Philp still gets the chance to win, just print Yes, otherwise print No. (PS: if the max score he could get on board add his current score is equal to the opponents current score, still output Yes)InputThe first line contains a numble N indicating the total conditions. Then followed by N lines, each line is made of three integers:Ball_Left P_Score O_Score represeting the ball number left on board, Philps current score, and the opponents current score.All the input value are in 32 bit integer value range.OutputYou should caculate the max score left Philp can gain, and judge whether he has the possiblity to win.Sample Input212 1 11 30 39Sample OutputYesNo4、Box of BricksProblem DescriptionLittle Bob likes playing with his box of bricks. He puts the bricks one upon another and builds stacks of different height. “Look, Ive built a wall!”, he tells his older sister Alice. “Nah, you should make all stacks the same height. Then you would have a real wall.”, she retorts. After a little consideration, Bob sees that she is right. So he sets out to rearrange the bricks, one by one, such that all stacks are the same height afterwards. But since Bob is lazy he wants to do this with the minimum number of bricks moved. Can you help?InputThe input consists of several data sets. Each set begins with a line containing the number n of stacks Bob has built. The next line contains n numbers, the heights hi of the n stacks. You may assume 1n50 and 1hi100.The total number of bricks will be divisible by the number of stacks. Thus, it is always possible to rearrange the bricks such that all stacks have the same height.The input is terminated by a set starting with n = 0. This set should not be processed.OutputFor each set, print the minimum number of bricks that have to be moved in order to make all the stacks the same height.Output a blank line between each set.Sample Input65 2 4 1 7 50Sample Output5 5、Subset sequenceProblem DescriptionConsider the aggregate An= 1, 2, , n . For example, A1=1, A3=1,2,3. A subset sequence is defined as a array of a non-empty subset. Sort all the subset sequece of An in lexicography order. Your task is to find the m-th one. (For example,n=3,the subset sequences are A1=1, A2=1,2,A3=1,2,3,A4=1,3,A5=2,A6=2,3,A7=3,m=5,the 5th one is 2).InputThe input contains several test cases. Each test case consists of two numbers n and m ( 0 n= 20, 0 m= the total number of the subset sequence of An ). The 0 in one line is to end.OutputFor each test case, you should output the m-th subset sequence of An in one line.Sample Input1 12 12 22 30Sample Output111 226、Hotel ManagementProblem DescriptionThere are many suites in a hotel, and how to manage for more profit is a important business for the manager. Assume one suite is priced at 160-dollar a day that could makes every suite is booked by the guest. However, as the price is up with every $20, three guests would be lost. Certainly that there is a daily maintenance cost, about $40, for every used suites.InputPlease input the number of suites in this Hotel.Output Please programming for suggest a price