Little Cubes / Big Cube This is a puzzle involving six colors: {blue, white, orange, red, green, yellow} and eight little cubes: {cube#1, cube#2, cube#3, cube#4, cube#5, cube#6, cube#7, cube #8}. Each little cube is colored with all six colors, one color per face. Your program needs to determine if there is a way to assemble the eight little cubes into a big 2x2x2 cube in such a way that the big cube is ALSO colored with all six colors, one color per face. If a solution exists, the program must describe one. Otherwise the program must state that there is no solution. An input file looks like this: 2 bworgy bwogry bworgy bwogry bworgy bwogry bworgy bwogry bworgy bworgy bwogry bworgy bworgy bowrgy bworgy bworgy The first line of the file is a left-justified, non-zero digit. This tells how many puzzles there are in the input. Then comes a series of blank-line-separated puzzle descriptions. Each puzzle description is a series of eight contiguous, left-justified lines. The Nth line in the puzzle description tells how cube#N is colored by giving the first letter of THE COLOR OF EACH FACE in the order: top, bottom, left, right, front, back. For example, line 3 of the second puzzle description above is "bwogry", which means that on cube#3, the top face is blue, the bottom white, the left orange, the right green, the front red, and the back yellow. Each of the lines of a puzzle description will consist of one contiguous string of six letters, as shown. Since it can affect the MEANING of the assignment of the colors, let us agree on a convention for naming the faces of little (and big) cubes: Choose some face of the cube, and call it the FRONT face. The LEFT FACE is THE ONE TO YOUR LEFT AS YOU LOOK DIRECTLY AT THE FRONT FACE. Naturally the right face is opposite the left, the back opposite the front, the top above the front and the bottom opposite the top. In solving the puzzle, you are free to rotate the little cubes any way that you like before they go into the big cube. So on input, it really does not matter WHICH face is chosen to be called the front. Here is the sample output file corresponding to the input above: No Solution to problem #1. A Solution to problem #2: In top , left , front : Cube # is .. 1. Arrangement is: (top = green ) (bottom = yellow ) (left = orange ) (right = red ) (front = white ) (back = blue ) In top , left , back : Cube # is .. 2. Arrangement is: (top = green ) (bottom = yellow ) (left = orange ) (right = red ) (front = white ) (back = blue ) In top , right , front : Cube # is .. 5. Arrangement is: (top = green ) (bottom = yellow ) (left = orange ) (right = red ) (front = white ) (back = blue ) In top , right , back : Cube # is .. 6. Arrangement is: (top = green ) (bottom = yellow ) (left = white ) (right = red ) (front = orange ) (back = blue ) In bottom, left , front : Cube # is .. 4. Arrangement is: (top = green ) (bottom = yellow ) (left = orange ) (right = red ) (front = white ) (back = blue ) In bottom, left , back : Cube # is .. 3. Arrangement is: (top = red ) (bottom = yellow ) (left = orange ) (right = green ) (front = white ) (back = blue ) In bottom, right , front : Cube # is .. 8. Arrangement is: (top = green ) (bottom = yellow ) (left = orange ) (right = red ) (front = white ) (back = blue ) In bottom, right , back : Cube # is .. 7. Arrangement is: (top = green ) (bottom = yellow ) (left = orange ) (right = red ) (front = white ) (back = blue ) Your output must be like that above: When a solution is described, the output must 1. tell which little cube (by number) is in which corner of the big cube (the corner is described by listing all the faces of the big cube that it contributes to, e.g. bottom, right, back), and 2. describe the orientation of the little cube within its position in the big cube by telling what colors are on the six faces, ASSUMING NOW THAT THE FACES OF THE LITTLE CUBE ARE NAMED TO MATCH UP WITH THE FACES OF THE BIG CUBE. (for example, since in the sample output above, cube#7 is in the bottom, right, back corner of the big cube, we assume that the bottom face of cube#7 is the one that forms part of the bottom face of the big cube, and similarly for the right and back faces of cube#7. Big Fractions This problem requires you to reduce fractions to lowest terms. The catch is that the numbers in the numerator and denominator can be very big -- up to 30 decimal places. Here is a sample input file: 3 0123456789 / 1234567890 1145171 / 555518333 100000 / 1000000000 All numbers in the input file will be positive integers. The first number, N, will be on a line by itself, left-justified, with no leading zeros. N tells how many fractions there are to process in the input file. Next will come N more lines, each containing one fraction formatted as shown above: first the numerator left-justified, then a blank, the "/" symbol, another blank, and finally the denominator beginning immediately in the next space. Numerators and denominators may have up to 30 digits, and may have leading zeros. The numerator will always be less than the denominator. The output corresponding to the input above looks like this: The fraction: 0123456789 / 1234567890 in reduced form, equals: 1 / 10 The fraction: 1145171 / 555518333 in reduced form, equals: 67363 / 32677549 The fraction: 100000 / 1000000000 in reduced form, equals: 1 / 10000 Use the exact same format and spacing as the example output. In particular, make sure that there are FOUR lines of output for each fraction input, as shown, and separate the output corresponding to successive input lines with a single blank line. The "answer fraction" you give on the fourth line of each section of output must be in reduced form, meaning that its numerator and denominator must not have any integer divisors in common (except plus and minus one, of course.) The Next Permutation A permutation is a rearrangement of items. For example, there are 6 permutations of the digits (1 2 3): (1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 1 2), (3 2 1) Given two permutations, P = (p1 p2 . . . pn) Q = (q1 q2 . . . qn) of the numbers from 1 to n, we say that P alphabetically precedes Q if pi = qi for 1 <= i <= k-1, and pk < qk, for some k, 1 <= k <= n. For example, the permutations of (1 2 3) above are in "alphabetical order." Write a program which, when given a permutation, will generate the "alphabetically next" permutation. In particular, assume that an input file contains 1 or more lists of digits. Within a list, successive digits will be separated by a single blank. Each list will be on a separate line. The first digit on each line will tell the number of digits on the rest of the line, and the rest of the digits will be a permutation. The file will end with a line with a single 0 on it. Your program is to read the file, and for each permutation, print out that permutation, and the "alphabetically next" permutation. NOTES: You may assume that all data is valid. In particular, there will be the correct number of digits on each line, all the digits (except the first) will be different from each other, and none of the permutations will be the "alphabetically last" one (like 5 4 3 2 1). The first number on a line will never be larger than 9. EXAMPLE: if the input file contains: 3 2 3 1 9 1 4 6 2 9 5 8 7 3 5 2 4 5 3 1 0 your output should be: (2 3 1) -> (3 1 2) (1 4 6 2 9 5 8 7 3) -> (1 4 6 2 9 7 3 5 8) (2 4 5 3 1) -> (2 5 1 3 4) As the example illustrates, each line of input must result in one line of output. Include the arrows and the parentheses as shown. ODOMETER TRIPLE PALINDROMES BACKGROUND A number forms a palindrome if it reads the same backward and forward. Charlie, palindrome laureate of Computer Science graduates, owns a Puffin II automobile that keeps track of miles in tenths and has two odometers: (1) a five-digit main odometer, which shows the integer part of the car's total mileage (0-99999, no tenths) and cannot be reset, and (2) a five-digit trip odometer, which can be reset to 00000 by pushing a button and shows mileage in tenths (0.0 to 9999.9) since the last reset. When Charlie saw his Puffin II new in the showroom, both odometers read 00000, so he exclaimed, "Hey, a triple palindrome!" By this he meant that the five-digit main odometer reading formed a palindrome, the five-digit trip odometer reading (forgetting the decimal point) formed a palindrome, and the ten-digit number formed by placing them end to end, with the main odometer on the left, also formed a palindrome. When the main odometer read 00090 and the trip odometer read 0090.0, Charlie filled his car with gas and reset the trip odometer. To his surprise, he observed another triple palindrome after he had driven just 10.0 miles; the main odometer and trip odometer both read 00100 (00100 total miles and 0010.0 since the last reset). Charlie immediately wondered if any integer total mileage was a "good" reset mileage, i. e., one at which he could reset the trip odometer to zero and still observe a triple palindrome sometime before the trip odometer rolls over 9999.9 miles later. The answer is no; for example, if he had reset the trip odometer when the main odometer read 00089 total miles, he would not have found a triple palindrome in the next 10000 miles. Hence, 89 total miles is not a "good" reset mileage. REQUIRED PROGRAM Your task is to write a program that will determine if a Puffin II integer total mileage is a "good" reset mileage or not. The program is to read in a series of integer total mileages. For each input total mileage, it is to reset the trip odometer to zero at this total mileage, determine if a triple palindrome will result before the trip odometer rolls over at 9999.9, and display the results. The program must repeat this process until the input total mileage is 0; it should halt (without producing further output) when 0 is input. Each input mileage will be an integer in the range 0-99999. For each non-0 input mileage, the output must appear on one line. If no triple palindrome will occur, this line must show the reset mileage as read in followed by one or more blanks and the words "NO TRIPLE". If a triple palindrome will occur, this line must show the reset mileage as read in followed by the main and trip odometer readings when the first triple palindrome will occur. All output values except trip odometer readings must be printed as five-digit integers with any necessary leading 0's; the trip odometer readings must be printed with a decimal point, four digits before (including any necessary leading 0's) and one digit after. Adjacent values on a line must be separated by one or more blanks. The output lines for different input mileages must be separated by one blank line. SAMPLE INPUT: 87642 1200 999 0 CORRESPONDING OUTPUT: 87642 97379 9737.9 01200 NO TRIPLE 00999 01110 0111.0 Pyramids Everyone is familiar with the method of making a "basic pyramid". You make a pattern like this, to a desired depth: * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * If you leave out some of the asterisks in the "basic pyramid", printing blanks instead, you can get some pretty designs, like this: Divisor is: 2 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * This last pattern is based on the idea of displaying the asterisk only if the corresponding number in Pascal's triangle is divisible by 2. (There are more rows in the second example than in the first, and the first two rows are blank.) You can get many striking patterns by using divisors other than 2. Your task is to write a program that gets a series of divisors, Q, and writes a pattern for each Q according to the following set of rules: (Assume the rows of a "basic pyramid" are numbered from top to bottom, starting with row zero at the top, and that the asterisks in each row are numbered from right to left starting with "asterisk zero" on the left.) 1. Print the "basic pyramid" pattern, EXCEPT print asterisk K in row N ONLY IF "N choose K" IS DIVISIBLE BY Q. Otherwise, just print a blank in that position. 2. Center the pattern in an 80 character output display, with the position for (row 0, asterisk 0) in the 40th column of the display, and all the other characters positioned accordingly below. 3. Print 38 rows of the pattern: rows 0 through 37. Each row is to be outputted, even if all its characters are going to be blanks (four such rows appear in the second pattern on the previous page). Single-space the display. "N choose K" is, of course, the Kth number in row N (using the numbering system described previously), of Pascal's triangle. These numbers are also called "The Binomial Coefficients." One formula for "N choose K" is N!/[(N-K)! * K!]. Here are rows 0 through 4 of Pascal's triangle: row # rows 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 Note that we use the convention that "N choose N" and "N choose 0" equal one, including the case when N is zero. INPUT: The input to the program is a series of P+1 positive integers, written on the first P+1 lines of the input file, one number to a line, left justified. The first integer is the number, P, of pyramids your program is supposed to make, followed by P more integers, which are the divisors to use for the respective pyramids. Each input integer will be between 1 and 500, inclusive, with no leading zeros. OUTPUT: The program must output the P pyramids, one after another, with a break of at least two lines between successive pyramids. There must be one pyramid using each divisor given, and the pyramids must be printed in the same order that the divisors appear in on the input. In addition, there must be a line of output just before each pyramid which states what divisor was used to generate it. As an example, note that the second pattern on the previous page is the first few lines of the output for the case where the input is: 1 2 The Schedule Maker It's time to get organized! Write a program to input lists of a week's worth of events, and output nice Gantt chart schedules of each week, showing what will occur, and when. Here is an example of an input file: 2 6 math 123 s3 MTuTh 8:00 pharm 10 s1 MWF 8:00 beer 230 s9 TuThF 15:00 cs 354 s2 FMW 12:00 bcis 21 s6 TuWThF 15:00 psy 201 s2 TuTh 12:00 4 cs 4000 s2 MWF 15:00 cs 2500 MWF 11:00 cs 3750 MWF 14:00 OFFICE TuTh 11:00 Note that SOME EVENTS OVERLAP: they are scheduled for the same time on the same day. For example, according to lines 3 and 4 of the input, "math 123 s3" and "pharm 10 s1" are both scheduled for monday at 8:00. An input file is a series of non-blank lines. A line either consists of just one positive integer left-justified, with no leading zeros, or a "