1994 IOI Problems DAY 1 PROBLEMS DAY 1 - PROBLEM 1 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Fig. 1 Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base. * Each step can go either diagonally down to the left or diagonally down to the right. * The number of rows in the triangle is > 1 but <= 100. * The number in the triangle, all integers are between 0 and 99 inclusive. In the example above the route through 7,3,8,7,5 produces the highest sum 30. INPUT DATA Data about the number of rows in the triangle are first read from the INPUT.TXT file followed by the rows of the triangle. In our example, INPUT.TXT appears as follows: 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 OUTPUT DATA The highest sum is written as an integer in the OUTPUT.TXT file. In our example this file would contain the number 30. DAY 1 - PROBLEM 2 1 2 3 4 5 6 7 ***************************** 1* * * * **** ***** * **** * 2* * * * * * * * ***** ***** **** * 3* * * * * * * ********** ****** * * 4* * * * ***************************** Fig 1.(string of *'s is a wall) N W + E S Figure 1 shows the map of a castle. Write a program that calculates 1) The number of rooms in the castle. 2) The size in modules of the largest room. 3) Which wall to remove from the castle (joining two existing rooms) to make as large a room as possible. The castle is divided into a grid of square modules m rows by n columns ( m<= 50, n<=50). Each module can have from zero to four walls, inclusive. INPUT.TXT The map is stored in the INPUT.TXT file in the form of numbers, one for each module. * The file starts with the number of modules in the north-south direction and the number of modules in the east-west direction. * In the following lines each module is described by a number (0<=p<=15). This number is the sum of: 1 (= wall to the west), 2 (= wall to the north), 4(=wall to the east), 8(=wall to the south). Inner walls are defined twice, a wall to the south in module 1,1 is also indicated as a wall to the north in module 2,1. The module at position 1,1 has a west, north and south wall so the sum is 1 + 2 + 8 = 11. * The castle always has at least two rooms. INPUT.TXT for our example: 4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13 OUTPUT DATA In the OUTPUT.TXT file, the following are written on three lines: 1) The number of rooms. 2) The area of the largest room counted in modules. 3) A suggestion of which wall to remove that will join two existing room to make as large a room as possible (first the row and then the column of the module next to the wall and finally the compass direction that points to the wall). There may be more than one but you need only choose one to display. ("4 1 E" is one of several possibilities) 5 9 4 1 E The last line refers to the removing the wall pointed to below. 1 2 3 4 5 6 7 ***************************** 1* * * * **** ***** * **** * 2* * * * * * * * ***** ***** **** * 3* * * * * * * ********** ****** * * 4*->* * * ***************************** Fig 2.(remove wall on the East wall of module 4 1) DAY 1 - PROBLEM 3 1 1 3 5 1 3 3 2 0 3 3 0 3 2 3 1 4 0 3 3 3 3 3 1 1 Fig. 1 Figure 1 shows a square. Each row, each column and the two diagonals can be read as a five digit prime number. The rows are read from left to right. The columns are read from top to bottom. Both diagonals are read from left to right. Using the data in the INPUT.TXT file, write a program that constructs such squares. * The prime numbers must have the same digit sum (11 in Fig. 1) * The digit in the top left-hand corner of the square is pre- determined (1 in the Fig.1). * A prime number many be used more than once in the same square. * If there are several solutions, all must be presented. * A five-digit prime number cannot begin with zeros, i.e. 00003 is NOT a five digit prime number. Input data The program reads data from the INPUT.TXT file. First the digit sum of prime numbers and then the digit in the top left-hand corner of the square. The file contains two lines. There will always be a solution to the given test data. In our example: 11 1 Output data In the OUTPUT.TXT file, write five lines for each solution found, where each line in turn consists of a five digit prime number. The above example has 3 solutions which means that the OUTPUT.TXT file contains the following (the empty line between the different solutions is optional): 1 1 3 5 1 1 4 0 3 3 3 0 3 2 3 5 3 2 0 1 1 3 3 1 3 1 1 3 5 1 3 3 2 0 3 3 0 3 2 3 1 4 0 3 3 3 3 3 1 1 1 3 3 1 3 1 3 0 4 3 3 2 3 0 3 5 0 2 3 1 1 3 3 3 1 DAY 2 PROBLEMS DAY 2 Problem 1 3 3 0 2 2 2 2 1 2 Figure 1 (Dial Positions) The nine numbers in figure 1 represent the position of 9 dials where each dial has one of four positions North or 12 o'clock (0) , East or 3 o'clock (1), South or 6 o'clock (2) and West or 9 o'clock (3). 0 3-+-1 2 There are 9 different ways to turn the dials on the clocks. Each way is called a move. Each move is selected by a number from 1 to 9. That number will turn the dials marked by a 1 90 degrees clockwise. Those marked with a 0 have no affect. The nine moves are displayed in figure 2 below. 1 1 0 1 1 1 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 Move 1 Move 2 Move 3 1 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 0 1 Move 4 Move 5 Move 6 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 Move 7 Move 8 Move 9 For example the following sequence of moves has the corresponding affect on the dials (they all end up at 12 o'clock (0). 3 3 0 3 0 0 2 2 2 Move 5 -> 3 3 3 Move 8 -> 2 1 2 2 2 2 3 0 0 0 0 0 3 3 3 Move 4 -> 0 3 3 Move 9 -> 3 3 3 0 3 3 0 0 0 0 0 0 0 0 0 The problem is write a program that will take any starting position for the clock and find the shortest sequence of moves which puts all the dials in the 12 o'clock (0) position. INPUT DATA Read nine numbers from the INPUT.TXT file. The example above will have the input data file: 3 3 0 2 2 2 2 1 2 OUTPUT DATA Write to the OUTPUT.TXT file the shortest sequence of moves (numbers), which turns all the dials to the 0 or 12 o'clock position. In our example the OUTPUT.TXT file could look as follows: 5849 Only one solution is required. Day 2 Problem 2 A man arrives at a bus stop at 12:00. He remains there during 12:00 - 12:59. The bus stop is used by a number of bus routes. The man notes the times of arriving buses. The times when buses arrive are given with the following rules: 1) Buses on the same route arrive at regular intervals from 12:00 to 12:59. 2) Times are given in whole minutes from 1 to 59. 3) Each bus route has at least 2 buses arriving at the station between 12 and 12:59. 4) The number of bus routes in the test example will be <= 17. 5) Buses from different routes may arrive at the same time. 6) Several bus routes can have the same time of first arrival and/or time interval. If two bus routes have the same starting time and interval, they are distinct and are both to be presented. Find the fewest number of bus routes that must stop at the bus stop to satisfy the input data. For each bus route, output the starting time and the interval. INPUT DATA The input file, INPUT.TXT, contains a number n (n<= 300) telling how many arriving buses have been noted, followed by the arrival times in ascending order. Out example: 17 0 3 5 13 13 15 21 26 27 29 37 39 39 45 51 52 53 If two buses arrive at the same time, that time is listed twice. OUTPUT DATA Write a table to the OUTPUT.TXT file with one line for each bus route. Each line in the file give the time of arrival for the first bus and the time interval in minutes. The order of the bus routes does not matter. If there are several solutions, only one is required. Our example gives: 0 13 3 12 5 8 DAY 2 Problem 3 Consider the magic list of 5 numbers 1 3 10 2 5 Any two number that are next to each other are considered neighbors. Also the two end numbers 1 and 5 as neighbors as if the list formed a circle of numbers. Starting with 2, we can form an unbroken sequence of integers from 2 to 21 using a single number in the list or by adding neighbors. Here is how the sequence is formed: 2, 3, 1+3=4, 5, 5+1=6, 2+5=7, 2+5+1=8, 5+1+3=9, 10, 2+5+1+3=11, 10+2=12, 3+10=13, 1+3+10=14, 3+10+2=15, 1+3+10+2=16, 10+5+2=17, 10+2+5+1=18, 5+1+3+10=19, 3+10+2+5=20, 1+3+10+2+5=21 You were given three number (n, m, and k) where n= the length of the list of numbers m= the starting number k= (smallest possible value for a member of the list, i.e. all numbers must be greater or equal to k). Your task is to choose n integers for the magic list where an unbroken sequence of all integers m, m+1, m+2,....max can be generated where max is as large as possible. INPUT DATA The INPUT.TXT file contains three integers (n,m,k). For the example the file would be: 5 2 1 OUTPUT DATA The file OUTPUT.TXT must contain: 1) The highest number (max) that can be generated with the list of numbers. 2) All arrangements of numbers in a circle that produce a sequence from m to max. (One per line.) Each arrangement is a list of numbers starting with the smallest number (which is not necessarily unique.) Note: 2 10 3 1 5 is not a valid solution, since it does not start with the smallest number. (1 3 10 2 5) and (1 5 2 10 3) must both be included in the output. Note that (1 1 2 3), (1 3 2 1), (1 2 3 1) and ( 1 1 3 2) should all be output. The output for our example would be: 21 1 3 10 2 5 1 5 2 10 3 2 4 9 3 5 2 5 3 9 4