********************************************************************** BRONZE PROBLEMS ********************************************************************** Four problems numbered 11 through 14 ********************************************************************** Problem 11: Countable Numbers [Woburn Competition, ICPSC, 1999] Cow hooves have no fingers to speak of, so they count in binary instead of decimal. Of course, with only four hooves, they can't count so very high in normal binary. They've devised a clever counting method, though. They stand on one to four of their legs after putting marks in the dirt. The marks represent binary 0's; their leg locations represent binary 1's. This means that they can represent numbers whose binary representation has four or fewer 1's. Given a range of positive integers (both the start number and stop number are in the range 1..15,000,000), determine how many numbers in that range the cows can represent with four or fewer one bits. PROBLEM NAME: cnums INPUT FORMAT: * Line 1: Two space-separated numbers: the beginning and end of a range to be checked SAMPLE INPUT (file cnums.in): 100 105 OUTPUT FORMAT: * Line 1: The count of numbers in the range that can be represented by four or fewer 1's using binary arithmetic. SAMPLE OUTPUT (file cnums.out): 5 OUTPUT DETAILS: Num Binary Number of 1's Representable by cows? 100 1100100 3 Yes 101 1100101 4 Yes 102 1100110 4 Yes 103 1100111 5 No 104 1101000 3 Yes 105 1101001 4 Yes ********************************************************************** Problem 12: Long Division [Traditional, 2005] The cows know their math ability is weak. Help them learn to divide by showing them the proper answer for several long division problems. Read in a pair of positive integers (each of which fits in 27 bits) and show their quotient to exactly 35 decimal places (even if many of those decimal places are '0'). If the answer is less than one, output exactly one leading 0 before the decimal point. Do not round the final digit. PROBLEM NAME: ldiv INPUT FORMAT: * Line 1: A single integer: the numerator * Line 2: A single integer: the denominator SAMPLE INPUT (file ldiv.in): 489384 583 INPUT DETAILS: Calculate 489384/583 OUTPUT FORMAT: * Line 1: The quotient with exactly 35 decimal places. SAMPLE OUTPUT (file ldiv.out): 839.42367066895368782161234991423670668 OUTPUT DETAILS: Even though the next digit after ...0668 is 9, no rounding is performed ********************************************************************** Problem 13: Boggled Cows [Traditional, 2005] The cows spent this year's spring break at Padre Island in Texas playing the popular word game called Boggle. Of course, since they are bad readers, they did not do so well. Your job will be to help them. Given a 5x5 matrix of not necessarily unique letters (range: 'A'..'Z') and an alphabetically sorted dictionary of fewer than 5,000 words no longer than 26 characters, find all the possible words that can be formed from the letters in the matrix using these rules: * Start the word with any character in the matrix * The next letter of any word can be any of the up to eight letters found above, below, to the right, to the left, or on any diagonal from the current letter * No letter can be used twice Of course, letters on the edge of the matrix have fewer options for subsequent letters. If a word can be formed using more than one traversal of the matrix, report it once for each possible traversal. Every input dataset contains at least one word. The auxiliary file named 'dict6.txt' contains dictionary words, one per line. PROBLEM NAME: boggle INPUT FORMAT: * Lines 1..5: Each line contains five capital letters that represent a line of the letter matrix. Line 1 represents the top line of the matrix, and so on. SAMPLE INPUT (file boggle.in): YIRFM JQUFK VUZZQ BUQQA TSYJE OUTPUT FORMAT: * Lines 1..?: Each line of the output contains a word that can be formed following the rules above. The output file must be sorted into alphabetical order. SAMPLE OUTPUT (file boggle.out): BUZZ BUZZ JA STU URI OUTPUT DETAILS: If a hypothetical dict6.txt file contained: BUZZ BUZZER BUZZERS JA STU URI then the output will be as shown. Consider determination for the word 'BUZZ': * The B is in row 4, column 1 * One U is in row 4, column 2 * The first Z is in row 3, column 3 * The second Z is in row 3, column 4 --and- * The B is in row 4, column 1 * The other U is in row 3, column 2 * The first Z is in row 3, column 3 * The second Z is in row 3, column 4 The other words follow from the letter layout. ********************************************************************** Problem 14: Acrophobic cows [Hal Burch, 2005] Like so many other creatures, the cows are 'acrophobic' and fear heights. They enjoy 'safe' spots in their pasture where they can't 'fall'. These spots are recognizable by the fact that their elevation is equaled or exceeded by the eight grid spots the surround them. No 'safe' spot is on the edge of a grid of elevations. Given a H by W grid (1 <= H <= 200; 1 <= W <= 200) of positive heights (all of which fit in a 31-bit integer), count the number of 'safe' spots the cows will enjoy. PROBLEM NAME: accow INPUT FORMAT: * Line 1: Two space-separated integers: H and W * Lines 2..?: Line 2 begins the description of the elevation grid (using the standard space-separated integers pattern, as always). A total of H groups of lines describe the grid, each group starting on a new line. Each line but the final line of a group contains 20 integers. The final line contains the remaining integers to make a total of W integers for that group. SAMPLE INPUT (file accow.in): 4 5 2 3 4 5 7 7 1 8 9 10 8 1 3 2 8 9 9 9 9 9 INPUT DETAILS: Four rows with five columns OUTPUT FORMAT: * Line 1: One integer: the number of safe grid locations SAMPLE OUTPUT (file accow.out): 3 OUTPUT DETAILS: The three safe points are the two 1's and the 2. **********************************************************************