The 3n + 1 Problem
Consider the following algorithm to generate a sequence of numbers. Start with an integer n. If n is even, divide by 2. If n is odd, multiply by 3 and add 1. Repeat this process with the new value of n, terminating when n = 1. For example, the following sequence of numbers will be generated for n = 22: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 It is conjectured (but not yet proven) that this algorithm will terminate at n = 1 for every integer n. Still, the conjecture holds for all integers up to at least 1, 000, 000. For an input n, the cycle-length of n is the number of numbers generated up to and including the 1. In the example above, the cycle length of 22 is 16. Given any two numbers i and j, you are to determine the maximum cycle length over all numbers between i and j, including both endpoints. Input The input will consist of a series of pairs of integers i and j, one pair of integers per line. All integers will be less than 1,000,000 and greater than 0. Output For each pair of input integers i and j, output i, j in the same order in which they appeared in the input and then the maximum cycle length for integers between and including i and j. These three numbers should be separated by one space, with all three numbers on one line and with one line of output for each line of input. Sample Input 1 10 100 200 201 210 900 1000 Sample Output 1 10 20 100 200 125 201 210 89 900 1000 174
Minesweeper
Have you ever played Minesweeper? This cute little game comes with a certain operating system whose name we cant remember. The goal of the game is to find where all the mines are located within a M N field. The game shows a number in a square which tells you how many mines there are adjacent to that square. Each square has at most eight adjacent squares. The 44 field on the left contains two mines, each represented by a * character. If we represent the same field by the hint numbers described above, we end up with the field on the right: *... .... .*.. .... *100 2210 1*10 1110
Input The input will consist of an arbitrary number of fields. The first line of each field contains two integers n and m (0 < n,m 100) which stand for the number of lines and columns of the field, respectively. Each of the next n lines contains exactly m characters, representing the field. Safe squares are denoted by . and mine squares by *, both without the quotes. The first field line where n = m = 0 represents the end of input and should not be processed. Output For each field, print the message Field #x: on a line alone, where x stands for the number of the field starting from 1. The next n lines should contain the field with the . characters replaced by the number of mines adjacent to that square. There must be an empty line between field outputs. Sample Input 44 *... .... .*.. .... 35 **... ..... .*... 00 Sample Output Field #1: *100 2210 1*10 1110 Field #2: **100 33200 1*100
The Trip
A group of students are members of a club that travels annually to different locations. Their destinations in the past have included Indianapolis, Phoenix, Nashville, Philadelphia, San Jose, and Atlanta. This spring they are planning a trip to Eindhoven. The group agrees in advance to share expenses equally, but it is not practical to share every expense as it occurs. Thus individuals in the group pay for particular things, such as meals, hotels, taxi rides, and plane tickets. After the trip, each students expenses are tallied and money is exchanged so that the net cost to each is the same, to within one cent. In the past, this money exchange has been tedious and time consuming. Your job is to compute, from a list of expenses, the minimum amount of money that must change hands in order to equalize (within one cent) all the students costs. Input Standard input will contain the information for several trips. Each trip consists of a line containing a positive integer n denoting the number of students on the trip. This is followed by n lines of input, each containing the amount spent by a student in dollars and cents. There are no more than 1000 students and no student spent more than $10,000.00. A single line containing 0 follows the information for the last trip. Output For each trip, output a line stating the total amount of money, in dollars and cents, that must be exchanged to equalize the students costs. Sample Input 3 10.00 20.00 30.00 4 15.00 15.01 3.00 3.01 0 Sample Output $10.00 $11.99
LCD Display A friend of yours has just bought a new computer. Before this, the most powerful machine he ever used was a pocket calculator. He is a little disappointed because he liked the LCD display of his calculator more than the screen on his new computer! To make him happy, write a program that prints numbers in LCD display style. Input The input file contains several lines, one for each number to be displayed. Each line contains integers s and n, where n is the number to be displayed (0 n 99, 999, 999) and s is the size in which it shall be displayed (1 s 10). The input will be terminated by a line containing two zeros, which should not be processed. Output Print the numbers specified in the input file in an LCD display-style using s - signs for the horizontal segments and s | signs for the vertical ones. Each digit occupies exactly s + 2 columns and 2s + 3 rows. Be sure to fill all the white space occupied by the digits with blanks, including the last digit. There must be exactly one column of blanks between two digits. Output a blank line after each number. You will find an example of each digit in the sample output below. Sample Input 2 12345 3 67890 00 Sample Output -- --| | || | | | | || | | -- -- -- -|| | | | || | | | -- ----- --- --- --- --|||||||| |||||||| |||||||| --- --- --|||||||| |||||||| |||||||| --- --- --- ---
