Problem 1 --------- The Acme Component Manufacturing Company (ACM) produces computer components for other companies. In order to keep track of what is inside each box that is shipped and where it is going, they use a three digit code on the package, easily readable by a scanner. Unfortunately, ACM's main competitor, Barry's Subsystems (BS), has hacked into ACM's mainframe, and the scanning program was lost! In a fit of panic, ACM's CEO has hired you to reconstruct the scanning program so they can continue business. Each package contains a three digit code, xyz, where x, y, and z are between 1 and 9. Here is the key: x: Destination y: Contents z: # ordered 1 Microsquash 1 Widgets 2 Picard Bell 2 Gadgets 3 Base 13 Research Company 3 Woozats 4 AT&V 4 Thingamajigs 5 Panaromic 5 Whatzits 6 Rain Microsystems 6 Integral Processors 7 Million Industries 7 Tristors 8 Dandy's Radio Shock 8 Ristors 9 Fruit Basket Hardware 9 Capitors The scanner is still working and will input the three digit code into your program, which should return output in the following format: Example 1 --------- input: 868 output: Dandy's Radio Shock: 8 Integral Processors Example 2 --------- input: 454 output: AT&V: 4 Whatzits Note: Your program must output ONLY ONE LINE, and it must be in exactly the format shown in the examples. Problem 2 --------- Murphy's Car Wash in Park City has been getting complaints. Some of their customers are quite absent-minded. After waiting in line to get their Porches and BMWs to the washing bay, they discover that they don't have anything smaller than a $100 bill. Since the coin changer only accepts one-dollar bills and five-dollar bills, they have to go to the bank to get some small change and wait in the line again. In order to keep his customers happy, Murphy has decided to build a new kind of coin changer. Instead of just taking small bills, he would like to connect directly to the local bank and allow his customers to withdraw money from their accounts in the form of coins they can use in the car wash machines. You have been given the job of programming this new device, called the Automatic Coin Machine (ACM), so that it outputs the proper number of coins when a user requests them. The input to your program will be a floating point number. It will contain exactly two decimal places and be less than 100 dollars. (Park City car washes are pretty expensive, too.) Your program should output the minimum number of coins required to create that total amount of money. (Assume that the ACM contains only quarters, dimes, nickels, and pennies.) Example 1 --------- input: 6.89 output: 32 Example 2 --------- input: 0.78 output: 6 Note: Your program must output ONLY ONE LINE, and it must be in exactly the format shown in the examples. Problem 3 --------- The Allied Commande Militaire (ACM) is planning to send supplies to the troops in Bosnia. These supplies are dropped from airplanes, and each plane carries two large packages. The ACM has many different sizes of packages that can be dropped, so they can provide supplies for various numbers of soldiers. They assume that the supplies will be used by troops who are working in an area that is perfectly circular and that the distribution of troops on the ground is uniform. The ACM leaders who ordered the drop wish to evaluate the results of their efforts, and that is where you come in. Each of the packages contains a homing device that automatically reports the exact point of landing. Since the radius of the area to be supplied by each one is known, it is possible to determine just how well the airplane pilots could aim. For this problem, you are to write a program that does only one part of the calculation necessary for this evaluation. Your program will input the point of impact of a package and the radius of its circle of coverage. It should output two things on separate lines: a. The number of points of intersection of the circumferences of the two circles. If the circles do not intersect, this should be 0; if the circles cross one another, it should be 2; if the circles are tangent to one another, the output should be 1. b. Whether or not one of the circles is completely enclosed by the other one. Your program must output either "inside" or "not inside" Note that the center of one of the circles may lie within the other circle, but unless all of the area of one circle is contained in the area of the other, the correct output is "not inside". Also, one circle could be inside another even if they are tangent. Input to your program will be in the format: X1 Y1 R1 X2 Y2 R2 Where X1,Y1,R1 specify the X and Y coordinates of the first package, and R1 specifies the radius of the first package. X2, Y2, and R2 specify the same things for the second package. All of these are floating point values. Example 1 Example 2 --------- --------- input: input: 0 0 3 0 0 3 0 0 1 0 2.5 1 output: output: 0 2 inside not inside Note: Your program must output ONLY TWO LINES, and they must be in exactly the format shown in the examples. Problem 4 --------- When the king of Disorgania died, his sons were left with the task of splitting up his gold figurines and bullion bars between them. Since neither one trusted the other, they commanded Merlin, the court wizzard, to decide upon a method of comparing the weights of the gold in such a way that they each got exactly the same amount. Merlin knew that if he did not perform his task properly, the prince who received the lesser amount of treasure would have him beheaded. With that incentive, the wizzard invented a device that he called an Avarice Control Machine (ACM). (Of course, he didn't tell either prince about that or his head would certainly have rolled!) In reality, the ACM was simply a balance scale. It had two dishes upon which gold objects were placed. If the sums of the objects on the two dishes was equal, the two dishes would be the same level; i.e., they would balance. The problem with the ACM was that it took so long to find a combination of objects that would balance. What Merlin needed was a computer program to make that decision quickly so he didn't have to try so many combinations in search of a solution. For this question, you are to write that program. Your program is to accept as input a number N, which is how many gold objects you have. The program should then accept as input N weight values. Each weight value will be given to you on a separate line. Your program should then output which objects that should be placed in each dish so that the scale will be balanced. You may assume that there will always be a solution such that the scale will balance, that the number of objects will be less than 20, and that each weight value is a whole number (i.e. no fractional pounds). It does not matter in which order the weights are listed in your output. If there are more than one possible solution, only one solution needs to be given. Example 1 Example 2 --------- --------- input: input: 4 6 7 5 2 12 6 7 1 1 1 12 output: output: Dish1: 7 1 Dish1: 7 12 Dish2: 6 2 Dish2: 1 12 1 5 Note: Your program must output ONLY TWO LINES, and they must be in exactly the format shown in the examples. Problem 5 --------- The computing community was terribly disappointed that the world's best chess program, IBM's Deep Blue, was soundly defeated by Garry Kasparov at the annual ACM Convention in Philadelphia last month. They have decided to invest $100M over the next year to build a faster machine, to be called the Automatic Chess Machine (ACM), and to write better software. You have been invited to participate in that software development effort. Your job is to write the code that controls movements of the knight. Of all the chess pieces, the knight is the most interesting. It is the only piece that can hop over other pieces. Its move is shaped like the letter L. It moves two squares in one direction, and then one square in a perpendicular direction. The knight cannot move off the edge of the board and the knight must land in an empty square for the purpose of this problem. Here are some sample knight moves on a 5x5 board: --------------------- --------------------- | | | K | | | | | | | | | --------------------- --------------------- | | | | | | | | K | | | | --------------------- --------------------- | | K | | | | | | | | K | | --------------------- --------------------- | | | | | | | | | | | | --------------------- --------------------- | | | | | | | | | | | | --------------------- --------------------- (K is where the knight started and/or ended.) Using these rules, a knight could move to as many as eight different places in a single move: --------------------- | | 1 | | 2 | | --------------------- | 8 | | | | 3 | --------------------- | | | K | | | --------------------- | 7 | | | | 4 | --------------------- | | 6 | | 5 | | --------------------- Your problem: Given a chess board with some other immobile pieces on it, report the minimum number of moves it takes the knight to move from square A to square B. The board that you will use is 8x8 squares. Input will be in the form of 8 lines of 8 characters which represent the state of the board. Periods represent empty squares, #'s represent squares with other pieces in them, and the starting point of the knight is the letter A. Output should be an integer reporting the minimum number of moves it will take the knight to get to square B. There will always be a solution for the cases that we will use to test your program. Example 1 --------- input: ........ .#...... ...#B... ..A.#... .....##. ........ ....#... ........ output: 1 Example 2 --------- input: ........ ........ ...#.... .A...... ..B..... #....#.. ..#..... ........ output: 4 Note: Your program must output ONLY ONE LINE, and it must be in exactly the format shown in the examples.