********************************************************************** BRONZE PROBLEMS ********************************************************************** Four problems numbered 11 through 14 ********************************************************************** Problem 11: Parkside's Triangle [Don Piele, 1989] Bessie taught the cows to make Parkside's Triangle. It is generated from two numbers: the size and the seed. The size N (1 <= N <= 20) determines how many rows are in the triangle and the seed S (1 <= S <= 9) determines the first number in the triangle. Here are two examples: N=5, S=3 N=6, S=1 3 4 6 9 4 1 2 4 7 2 7 5 7 1 5 3 5 8 3 8 8 2 6 6 9 4 9 3 7 1 5 1 8 6 2 3 The first line of any triangle has no blanks at its front. Analyze the above examples, discover the rule, and write a program that will generate Parkside's Triangle given any size N (1 <= N <= 20) and any seed S (1 <= S <= 9). PROBLEM NAME: pktri1 INPUT FORMAT: * Line 1: Two space-separated integers: N and S SAMPLE INPUT (file pktri1.in): 5 3 OUTPUT FORMAT: * Lines 1..N: Parkside's Triangle as above; no trailing blanks on any line. SAMPLE OUTPUT (file pktri1.out): 3 4 6 9 4 5 7 1 5 8 2 6 3 7 8 ********************************************************************** Problem 12: Alignment of the Planets [Traditional, 2005] Actually, this problem is about alignment of N (1 <= N <= 770) cows numbered 1..N who are grazing in their field that is about 15,000x15,000 units. Their grazing locations all fall on integer coordinates in a standard x,y scheme (coordinates are in the range 0..15,000). Bessie looks up and notices that she is exactly lined up with Sara and Julie. She wonders how many groups of three aligned cows exist within the field. Given the locations of all the cows (no two cows occupy the same location), figure out all sets of three cows are exactly collinear. Keep track of the sets, sorting the cows in each set by their ID number, lowest first. Then sort the sets by the three ID numbers (lowest first), breaking ties by examining the second and third ID numbers. HINT: Be careful of floating point arithmetic. Floating point comparison for equality almost never works as well as one would hope. PROBLEM NAME: align INPUT FORMAT: * Line 1: A single integer, N * Lines 2..N+1: Line i+1 describes cow i's location with two space-separated integers that are her x and y coordinates SAMPLE INPUT (file align.in): 8 0 0 0 4 1 2 2 4 4 3 4 5 5 1 6 5 INPUT DETAILS: Eight cows grazing on a grid whose lower left corner looks like this: . . . . * . * * . * . . . . . . . . * . . . * . . . . . . . . . . * . * . . . . . . OUTPUT FORMAT: * Line 1: A single integer that is the number of sets of three cows that are exactly collinear. A set of four collinear cows would, of course, result in four sets of three collinear cows. * Lines 2..?: Each line contains three space-separated integers that are the cow ID numbers of three collinear cows. The lines are sorted as specified above. This output section is empty if no collinear sets exist. SAMPLE OUTPUT (file align.out): 1 1 3 4 OUTPUT DETAILS: The digits mark the collinear cow IDs: . . . . * . * * . 4 . . . . . . . . * . . . 3 . . . . . . . . . . * . 1 . . . . . . ********************************************************************** Problem 13: Finding Bovine Roots [Kolstad, 2005] The cows are trying to find their roots. They are not so smart as humans when they find square roots, the cows lose the integer portion of their square root calculation. Thus, instead of calculating the square root of 2 to be 1.4142135623730950488016887242096980785696, they deduce that it is 0.4142135623730950488016887242096980785696. The square root of 16 is calculated to be 0 (obviously an error). The erroneous ciphering does, however, lead to an interesting question. Given a string of digits of length L (1 <= L <= 9), what is the smallest integer whose bovine square root decimal part begins with those digits? By way of example, consider the string "123". The square root of 17 is approximately 4.1231056256176605498214098559740770251472 so the bovine square root is: 0.1231056256176605498214098559740770251472 whose decimal part (just after the period) starts with 123. It turns out that 17 is the smallest integer with this property. HINT: Be careful of floating point arithmetic. It engenders rounding errors that can be surprising. TIME LIMIT: 0.5 seconds PROBLEM NAME: roots INPUT FORMAT: * Line 1: A single integer, L * Line 2: L digits (with no spaces) SAMPLE INPUT (file roots.in): 3 123 OUTPUT FORMAT: * Line 1: A single integer that is the smallest integer whose bovine square root starts with the supplied string SAMPLE OUTPUT (file roots.out): 17 OUTPUT DETAILS: sqrt(17) ~= 4.1231056256176605498214098559740770251472 ********************************************************************** Problem 14: Cow Bowling [IOI, 1994] The cows don't use actual bowling balls when they go bowling. They each take a number (in the range 1..99), though, and line up in a standard bowling-pin-like triangle like this: 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Then the other cows traverse the triangle starting from its tip and moving "down" to one of the two diagonally adjacent cows until the "bottom" row is reached. The cow's score is the sum of the numbers of the cows visited along the way. The cow with the highest score wins that frame. Given a triangle with N (1 <= N <= 350) rows, determine the highest possible sum achievable. PROBLEM NAME: bowl INPUT FORMAT: * Line 1: A single integer, N * Lines 2..N+1: Line i+1 contains i space-separated integers that represent row i of the triangle. SAMPLE INPUT (file bowl.in): 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 OUTPUT FORMAT: * Line 1: The largest sum achievable using the traversal rules SAMPLE OUTPUT (file bowl.out): 30 OUTPUT DETAILS: 7 * 3 8 * 8 1 0 * 2 7 4 4 * 4 5 2 6 5 The highest score is achievable by traversing the cows as shown above. **********************************************************************