ACM Regional Programming Contest 1997 Problem No. 1 - Heads Executable Program: PROG1.EXE Source Program: PROG1.CPP, PROG1.C, PROG1.PAS Input file: PROG1.IN Output file: PROG1.OUT Problem Description: The probability of n heads in a row tossing a fair coin is 2^-n Input: r lines containing each one an integer number n. the values of r and n are as follows. 0< r < 10, 0< n <=9000. Output: Print r lines each with the value of 2^-n for the given values of n, using the format: 2^-n = x.xxxE-y where each x is a decimal digit and each y is a decimal integer with no leading zeroes or spaces. Input file example: 8271 6000 1 Output file example: 2^-8271 = 1.517E-2490 2^-6000 = 6.607E-1807 2^- 1 = 5.000E-001 ACM Regional Programming Contest 1997 Problem No. 2 - Image Recognizer Executable Program: PROG2.EXE Source Program: PROG2.CPP, PROG2.C, PROG2.PAS Input file: PROG2.IN Output file: PROG2.OUT Problem Description: Consider an Image represented by a matrix of digits, each digit represents the brightness of a pixel, as shown below. In early image processing, one could detect a particular feature in the image by finding the location where the feature (template) best matches the image. Image: 0 1 0 1 1 0 0 Template: 0 0 1 1 1 1 0 0 0 0 1 1 1 0 2 0 0 2 0 0 1 2 0 1 2 0 3 3 3 3 0 0 0 3 3 2 3 3 0 0 1 1 1 0 0 1 To do this, you have to calculate, for each point y in the image where the template can fit entirely within the image, the cross-correlation S i(x) t(x-y) x where i and t are the image and template light function respectively and x runs over all points in the image. The point with maximum cross-correlation is accepted as the location of the feature in the image. Develop a program that takes pairs of images. For each pair, use the algorithm above and deliver the point of location (which is the pixel (x,y) in i where t has maximum cross-correlation) Give one answer per line. The Image starts al location (0,0) which is the upper-left corner. In the example below, the feature is detected at point of location (1,1). Which is The only output line. Notes: The image and templates sizes are variable and never will be greater than 50 by 50 points. The x-axis is horizontal and the y-axis is vertical. A character F in the input file indicates the end of pairs of images. If a template fits equally in more than one place, the correct answer will be the closest to the upper-left corner. You can take the exact format from the example below Input file example: I 0 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 2 0 1 2 0 0 3 3 2 3 3 0 0 1 1 0 0 0 1 T 0 0 1 1 1 1 0 2 0 0 2 0 3 3 3 3 0 0 F Output file example: (1,1) ACM Regional Programming Contest 1997 Problem No. 3 - DDF Executable Program: PROG3.EXE Source Program: PROG3.CPP, PROG3.C, PROG3.PAS Input file: PROG3.IN Output file: PROG3.OUT Problem Description : An integer a is a positive factor of an integer b if a is greater than zero and there exist some integer n such that a * n = b. consider a sequence of integer x1, x2, x3, ^xn. This sequence is a Decimal-Digit Factor Sequence (DDF) if each number in the sequence is a positive integer where x1 > 1 and for all positive integers i > 1, xi+1 is the sum of the digits of all positive factors of xi. The following is a DDF: 17, 9, 13, 5, 6, ^ positive factor of 17 = 1, 17 1 + (1 +7) = 9 positive factor of 9 = 1 ,3 ,9 1 + 3 + 9 = 13 positive factor of 13 = 1 , 13 1 + (1 + 3) = 5 positive factor of 5 = 1 , 5 1 + 5 = 6 It is known that any DDF beginning whit a number greater than or equal to 1000 repeats no number greater than or equal to 1000 and contains a number less than 1000. In addition, every DDF beginning whit a number less than 1000 contains no number greater than 999. Thus, every DDF must eventually repeat number less than 1000. It has also been show that every DDF eventually repeats a single number. That is, for each DDF, there exists a number xn , called the last term, such that for all j >n , xj = xn. Write a program that will find the longest DDF. You have to read the input file each line will have two numbers m , n which define the range were you have to find the longest DDF. In non case m and n will be greater than 3000. Many DDF«s will have the same last term, so you program should report only the first one. Input file example: 200 500 100 150 Output file example: Input1: 200 500 Output1: 285 66 36 46 18 30 27 22 9 13 5 6 12 19 11 3 4 7 8 15 Input2: 100 150 Output2: 102 36 46 18 30 27 22 9 13 5 6 12 19 11 3 4 7 8 15 ACM Regional Programming Contest 1997 Problem No. 4 - Tree Executable Program: PROG1.EXE Source Program: PROG4.CPP, PROG4.C, PROG4.PAS Input file: PROG4.IN Output file: PROG4.OUT You are to determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path. The input file will contain a description of the binary tree given as the inorder and postorder traversal sequences of that tree. Your program will read two line (until end of file) from the input file. The first line will contain the sequence of values associated with an inorder traversal of the tree and the second line will contain the sequence of values associated with a postorder traversal of the tree. All values will be greater than zero and less than 500. You may assume that no binary tree will have more than 25 nodes or less than 1 node. For each tree description you should output the value of the leaf node of a path of least value. In the case of multiple paths of least value you may pick any of the appropiate terminal nodes. Input file example: 3 2 1 4 5 7 6 3 1 2 5 6 7 4 7 8 11 3 5 16 12 18 8 3 11 7 16 18 12 5 255 255 Output file example: 1 3 255 ACM Regional Programming Contest 1997 Problem No. 5 - Evaluating an Equations Board Executable Program: PROG1.EXE Source Program: PROG5.CPP, PROG5.C, PROG5.PAS Input file: PROG5.IN Output file: PROG5.OUT Equations is a game that is played competitively in several parts (The game as described below is only a subset of the actual game). You are to write a program which evaluates an Equations board. The game equations is played with 13 cubes. Each cube will contain six of the following symbols, one symbol on each side: 0 1 2 3 4 5 6 7 8 9 + - x (Each symbol can be found on six of the cubes.) The symbols + ,- , and x stand for the binary operations addition, subtraction, and multiplication, respectively. There are two sections to an Equation board: Resources and Goal. At the beginning of a game of Equations, all of the cubes are rolled and placed into Resources section. For all examples below, assume that the following was rolled: 0 1 4 5 6 7 9 + + + - x x One of the players then sets a goal by taking one or two of the digits in the Resources section and placing them into the Goal section. (assume that you cannot have a goal with a leading 0 such as 09.) For all the examples below, the goal is 56. The central idea of the game is to make a solution which equals the goal and uses a subset of the other cubes. There are two main restrictions to the solution: 1) it can use only one-digit numbers. For instance, 49 + 7 is not a valid solution, since 49 is a two-digit number. 2) Parentheses may be used wherever valid in standard arithmetic. This means that 7 x ( 9 - 1) is a valid solution for the above goal, using the aboves cubes. However, the parenteheses cannot be used for implied multiplication, so 7 ( 9 - 1) is not a valid solution. Your program will read two lines at a time (until end of file) from the input file. This two lines represent the Resource and the Goal sections of an Equations board. There will be no embedded, leading or trailing blanks on each line; you may also assume that the two lines contain only the 13 symbols which are legal symbols in Equations. For each situation, the program should output "no solution" when you cannot make a solution which equals the goal using some or all cubes from Resources, or should output "solution" when you can make a solution that uses some or all cubes in Resource. Input file example: 999999+++++ 54 0149++-7+xx 56 0149++-7+-- 56 Output file example: solution solution no solution