IOI'92 Problems - Bonn, Germany, July 1992 TASK 4.1.1: "MYSTERIOUS CONTINENTS" =================================== A MAP is a 48 by 16 rectangle of COORDINATES. Two coordinates are CONNECTED if they are neighbours either in south-north or in east-west direction. Initially each coordinate is only known to be either WATER (W) or GROUND (G). There are four GROUND TYPES (GT): G, M, P, and C. And there are four WATER TYPES (WT): W, O, B, and L. It is assumed that outside the map there is OCEAN (O). There are certain geographic rules for changing the type of a coordinate (RELABELING). It may become a: - MOUNTAIN (M): If a GT is connected to 4 other GT. - PENINSULA (P): If a GT is connected to 3 WT, or to 2 WT and at least 1 P, or to 1 WT and at least 2 P. - COASTLINE (C): If a GT is not M and not P. - OCEAN (O): If a WT is connected to at least one O. - BAY (B): If an O is connected to at least 2 B and at most one O, or to 1 B and at least 2 GT, or to at least 2 GT and at least one O. - LAKE (L): If a W remains unchanged till no other relabeling is possible any more. It may happen, that after a certain coordinate has been relabeled, it can be relabeled once again later, because the types of some neighbours have changed in the meantime. A map is EXPLORED if no relabeling is possible any more. PROBLEM STATEMENT ================= Implement a program which does the following in that order: 1. Read a map of an unknown continent from an ASCII input file and display it on the screen, together with the initial coordinate type statistics, as shown in Example-1. 2. Explore the map and relabel the coordinates correctly with M, P, C, O, B, or L according to the geographic rules. 3. Display the explored map on the screen, with the final coordinate type statistics, as shown in Example-2. 4. Write a screen copy showing the explored map and the final coordinate type statistics to an ASCII output file. TECHNICAL CONSTRAINTS ===================== Constraint-1: Put your solution program into an ASCII text file named "C:\IOI\DAY-1\411-PROG.xxx". Extension .xxx is: - .BAS for BASIC programs, .C for C programs, - .LCN for LOGO programs, .PAS for PASCAL programs. Constraint-2: The name of the ASCII input file for reading an unknown map from must be "C:\IOI\DAY-1\411-MAP.IN". Constraint-3: The name of the ASCII output file for writing explored map and statistics to must be "C:\IOI\DAY-1\411-MAP.OU". EXAMPLE(S) ========== Example-1: The screen display, including initial statistics, of the unknown map in file "C:\IOI\DAY-1\411-MAP.IN" should look like: WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWGGGGGGWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWGGWWGGWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWGGGWGGWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWGGWWGGWWWGGGWGWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWGGGGGGGGGGGGGWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWGGGWWWGGWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWGGGWWWGGWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWGGGGWWGGWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWGGWWWGGWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWGWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWGWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWGGGWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW MYSTERIOUS: G=61 W=707 ALL=768 Example-2: The screen display of the explored map, including final statistics and the file "C:\IOI\DAY-1\411-MAP.OU" should look like: OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOCCCCCCOOOOOOOOOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOCCLLCCOOOOOOOOOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOCMPLCCOOOOOOOOOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOCCLLCCBBBCCCBPOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOBCCCCCCCCMCCCCBOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOBCMCBBBCCOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOOCMCBOOCCOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOOCMMPOOCCOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOOBCCBOOCCOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOOOBPBOOOOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOOOBPBOOOOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOOOPPPOOOOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO EXPLORED: P=8 C=47 M=6 O=685 B=17 L=5 ALL=768 SAMPLE FILES ============ We provided these correct example files for your convenience: "C:\IOI\DAY-1\411-MAP.IN" and "C:\IOI\DAY-1\411-MAP.OU". WARNING: Successful execution of your program with Example-1 above does not necessarily guarantee that your program is correct !!! CREDITS ======= Read from a file and display unknown map correctly ......... 5 points All Mountains correctly relabeled with M ................... 10 points All Peninsulas correctly relabeled with P .................. 20 points All Coastlines correctly relabeled with C .................. 5 points All Ocean correctly relabeled with O ....................... 10 points All Bays correctly relabeled with B ........................ 20 points All Lakes correctly relabeled with M ....................... 5 points Initial Statistics correct ................................. 5 points Final Statistics correct ................................... 10 points Structure of output file correct ........................... 5 points Technical constraints completely obeyed .................... 5 points ---------------------------------------------------------------------- maximal 100 points TASK 4.1.2: "A MAZING WORKSHOP" =============================== A MAZE completely covers an AREA of N times M squares. It consists of many WALL squares and of many SPACE squares, the latter of which include one ENTRY square and one TREASURE square. A PATH is a sequence of adjacent space squares (bounded by walls) from the entry to a dead end, we refer to as an ENDPOINT. The LENGTH of a path is the number of squares it covers, including entry and endpoint. The maze must be such that paths may fork but do not join, so for example no two paths can have the same endpoint. The entry is located somewhere at the top of the maze. The treasure is positioned at the endpoint of a path with maximal length. The N times M area should be covered with paths as much as possible. It is nice to watch a maze growing over an area while it is computed. Because the algorithm is too fast for the eye, a DELAY TIME after each drawn square is necessary. PROBLEM STATEMENT ================= Implement the following set of TOOLS dealing with mazes. The tools should be executable in any order and repetition through a main menue: Tool-1: Set the main maze parameters N and M interactively. Tool-2: Set a DELAY TIME interactively. Tool-3: Compute a new correct maze basically using a random generator and display the maze while it is growing. Tool-4: Write a generated maze and its size parameters to an ASCII text file, exactly as it is shown in Example-2. Tool-5: Read an unknown maze from an ASCII text file and highlight the path from entry to treasure. TECHNICAL CONSTRAINTS ===================== Constraint-1: Represent each square by a two-character string: - walls by two times ASCII character #219 ...... "[[" - paths and entry by two blanks ................ " " - treasure by T and blank ...................... "T " - highlighted paths by full-stop and blank ..... ". " Constraint-2: N and M must be greater than 2 and not larger than 20. Constraint-3: Put your solution program into an ASCII text file named "C:\IOI\DAY-1\412-PROG.xxx". Extension .xxx is: - .BAS for BASIC programs, .C for C programs, - .LCN for LOGO programs, .PAS for PASCAL programs. Constraint-4: The name of the ASCII text file for reading and writing mazes must be "C:\IOI\DAY-1\412-MAZE.IO". EXAMPLE(S) ========== Example-1: A screen display of sample file "C:\IOI\DAY-1\412-MAZ1.IO" by Tool-5 should look like: N = 10, M = 8, DELAY TIME = 100 [[[[[[[[[[[[. [[[[[[ [[[[[[ . . [[ [[ [[[[ [[. [[ [[ [[ [[ . . [[ [[ [[ [[ [[. . [[ [[[[ [[ [[. [[[[ [[ [[T . . . [[ [[[[[[[[[[[[[[[[[[[[ LENGTH = 13 Example-2: The same maze's file output by Tool-4 should look like: 10 8 [[[[[[[[[[[[ [[[[[[ [[[[[[ [[ [[ [[[[ [[ [[ [[ [[ [[ [[ [[ [[ [[ [[ [[ [[[[ [[ [[ [[[[ [[ [[T [[ [[[[[[[[[[[[[[[[[[[[ SAMPLE FILES ============ We provided these correct example files for your convenience: "C:\IOI\DAY-1\412-MAZ1.IO" and "C:\IOI\DAY-1\412-MAZ2.IO". WARNING: Successful execution of your program with these examples does not necessarily guarantee that your program is correct !!! CREDITS ======= Main menue with all tools available ........................ 5 points Tools available in any order and repetition ................ 10 points Tool-1 enables setting N and M ............................. 5 points Tool-2 enables setting DELAY TIME .......................... 5 points Tool-3 computes structurally correct mazes ................. 30 points Tool-3 displays the maze while it is growing ............... 10 points Tool-4 writes maze to a file exactly as in example-2 ....... 5 points Tool-5 reads unknown maze and highlights longest path ...... 20 points Technical constraints completely obeyed .................... 10 points ---------------------------------------------------------------------- maximal 100 points Problem Chosen for the first session ( 5 hours ) ***TASK 4.1.3 "ISLANDS IN THE SEA" =============================== The SEA is represented by an N times N grid. Each ISLAND is a "*" on that grid. The task is to reconstruct a MAP of islands only from some CODED INFORMATION about the horizontal and vertical distribution of the islands. To illustrate this code, consider the following map: * * * 1 2 * * * * 3 1 * * * 1 1 1 * * * * * 5 * * * * 2 1 1 * 1 1 1 4 2 2 1 1 2 3 2 1 The numbers on the right of each row represent the order and size of the groups of islands in that rows. For example, "1 2" in the first row means that this row contains a group of one island followed by a group of two islands; with sea of arbitrary length to the left and right of each island group. Similarly, the sequence "1 1 1" below the first column means that this column contains three groups with one island each, etc. PROBLEM STATEMENT ================= Implement a program which repeats the following steps until a given input file containing several information blocks has been read completely: 1. Read the next information block from an ASCII input file (for the data structure of that file see also the examples below) and display it on the screen. Each information block consists of the size of the square grid, followed by the row constraints and the column constraints. Each constraint for a single row or column appears on a single line as a sequence of numbers separated by spaces and terminated by 0. 2. Reconstruct the map (or all of the maps, if more then one solution is possible, see Example-4) and display it/them on the screen. 3. Write the map(s) to the end of an ASCII output file. Each blank must be represented by a pair of spaces. Each island should be represented by a '*' followed by a space. Different maps satisfying the same constraints should be separated by a blank line. If there is no map satisfying the constraints, indicate it by a line saying "no map". The solutions to the different information blocks must be separated by a line saying "next problem". TECHNICAL CONSTRAINTS ===================== Constraint-1: N must be not less than 1 and not larger than 8. Constraint-2: Put your solution program into an ASCII text file named "C:\IOI\DAY-1\413-PROG.xxx". Extension .xxx is: - .BAS for BASIC programs, .C for C programs, - .LCN for LOGO programs, .PAS for PASCAL programs. Constraint-3: The name of the ASCII input file for reading the coded information from must be "C:\IOI\DAY-1\413-SEAS.IN". Constraint-4: The name of the ASCII output file for writing the map(s) to must be "C:\IOI\DAY-1\413-SEAS.OU". EXAMPLE(S) ========== 6 Example-1 (the problem above): 6 is the size of the grid. 1 2 0 <-- The start of the first line constraint 3 1 0 1 1 1 0 5 0 2 1 1 0 1 0 1 1 1 0 <-- The start of the first column constraint 1 2 0 4 0 2 3 0 2 0 1 2 0 4 Example-2. Solution: columns: 1 2 3 4 0 row 1: 1 0 row 2: * 2 0 row 3: * * 0 row 4: 0 1 0 2 0 0 2 Example-3. Note that there is no map 0 satisfying the constraints. 0 2 0 2 0 2 Example-4. Note that there are two different maps 1 0 satisfying the constraints. 1 0 1 0 1 0 SAMPLE FILES ============ We provided these correct example files for your convenience: "C:\IOI\DAY-1\413-SEAS.IN" and "C:\IOI\DAY-1\413-SEAS.OU". WARNING: Successful execution of your program with these examples does not necessarily guarantee that your program is correct !!! CREDITS ======= Read an information block from the input file and display it .............................. 5 points Process all information blocks one by one until the input file is read completely .................... 10 points Reconstruct one map for each information block (if it has a solution) and display it ................ 35 points Write the solution map to the output file .................. 5 points Reconstruct all possible maps (if there are several solutions) and display them .................... 20 points Write all solution maps correctly separated to the output file ............................... 10 points Identify information blocks having no solution ............. 5 points Technical constraints completely obeyed .................... 10 points ---------------------------------------------------------------------- maximal 100 points Second Session Problems TASK 4.2.1: "HAMILTON'S ROBOT" ============================== On a plane there are given N positions P1, P2, ..., PN with integer coordinates (X1,Y1), (X2,Y2), ..., (XN,YN). A robot should move through all these positions starting at P1. It should come to each position only once with the exception of P1 which also has to be the position at the end of the tour. There are constraints on the robot's movements. It can only move along straight lines. From P1 it can start in any direction. Reaching one of the Pi, before moving on to another position it must turn 90 degrees either to the left or to the right. A robot program consists of five types of statements: 1. "ORIENTATION Xk Yk": usable as the first statement only. The robot turns to the direction of the position Pk (k between 2 and N). 2. "MOVE-TO Xj Yj" : if the robot can reach Pj without changing its current orientation, then it moves to the position Pj (j between 1 and N). Otherwise the statement is not executable. 3. "TURN-LEFT" : the robot changes its orientation 90 degrees to the left. 4. "TURN-RIGHT" : the robot changes its orientation 90 degrees to the right. 5. "STOP" : deactivates the robot. This is the necessary last statement of each robot program. PROBLEM STATEMENT ================= Implement a program that does the following: 1. Read the value of N and the coordinates for N given positions from an ASCII input file (see Example) and display the data on the screen. 2. Develop a robot program for a valid tour through all positions (as defined above) if one exists. 3. If there is no possible tour, the robot program must consist just of the "STOP"-statement. 4. Display on the screen, whether a tour is possible or not and, if there exists one, its length (rounded, 2 digits after the decimal point). The length of a tour the sum of the lengths of the straight line pieces. 5. Write the robot program to an ASCII output file exactly as is shown in Example. TECHNICAL CONSTRAINTS ===================== Constraint-1: Put your solution program into an ASCII text file named "C:\IOI\DAY-2\421-PROG.xxx". Extension .xxx is: - .BAS for BASIC programs, .C for C programs, - .LCN for LOGO programs, .PAS for PASCAL programs. Constraint-2: The name of the ASCII input file for reading the positions from must be "C:\IOI\DAY-2\421-ROBO.IN". Constraint-3: The name of the ASCII output file for writing the robot program to must be "C:\IOI\DAY-2\421-ROBO.OU". Constraint-4: Program must reject inputs where N is less than 4 or greater than 16, without trying to find a tour! EXAMPLE(S) ========== Input: An input file contains in the first line the value for N and in the following N lines the X and Y coordinates of the selected positions, for example: 4 2 -2 0 2 -1 -1 3 1 Output: For these 4 positions one shortest robot program with length = 12.65 is: ORIENTATION 3 1 MOVE-TO 3 1 TURN-LEFT MOVE-TO 0 2 TURN-LEFT MOVE-TO -1 -1 TURN-LEFT MOVE-TO 2 -2 STOP SAMPLE FILES ============ We provide these correct files with the above input and output for your convenience: "C:\IOI\DAY-2\421-ROBO.IN" and "C:\IOI\DAY-2\421-ROBO.OU". WARNING: Successful execution of your program with this example does not necessarily guarantee that your program is correct !!! CREDITS ======= Read input data correctly from every file and display it.... 5 points Algorithm for computing a valid tour ok .................... 30 points Generated robot program syntactically correct, if tour does not exist .................................. 10 points Generated robot program syntactically correct, if tour does exist ...................................... 15 points Screen display gives all required information .............. 5 points Displayed length of computed tour correct .................. 10 points Robot program correctly written to a file .................. 10 points Technical constraints obeyed ............................... 15 points ---------------------------------------------------------------------- maximal 100 points Problem Chosen for the second session ( 5 hours ) ***TASK 4.2.2: "CLIMBING A MOUNTAIN" =================================== A mountain climbers club has P members, numbered from 1 to P. Every member climbs at the same speed and there is no difference in speed between climbing up and down. Climber number i consumes C(i) units of SUPPLIES per day and can carry at most S(i) such units. All C(i) and S(i) are integer numbers. Assume that a climber with a sufficient amount of supplies would need N days to reach the top of the mountain. The mountain may be too high, so that a single climber cannot carry all the necessary supplies. Therefore a GROUP of climbers starts at the same place and at the same time. A climber who descends prematurely before reaching the top gives his unneeded supplies to other climbers. The climbers do not rest during the expedition. The PROBLEM is to plan a schedule for the climbing club. At least one climber must reach the top of the mountain and all climbers of the selected group return to the starting point. PROBLEM STATEMENT ================= Implement a program which does the following: 1. Read from the keyboard the integer number N of days needed to arrive at the top, the number P of climbers in the club, and (for all i from 1 to P) the numbers S(i) and C(i). You may assume that the inputs are integers. Reject inputs that make no sense. 2. Try to find a schedule for climbing the mountain. Determine a possible group a(1), ..., a(k) of climbers who should participate in the party and (for all j from 1 to k) the number M(j) of supplies which climber a(j) carries at the start. Note that there may not exist a schedule for all combinations of N and the S(i) and C(i). 3. Output the following information on the screen: a) the number k of climbers actually participating in the party, b) the total amount of supplies needed, c) the climber numbers a(1), .., a(k), d) for all a(j), j between 1 and k, the initial amount M(j) of supplies to carry for climber a(j), e) the day D(j) when climber a(j) starts descending. 4. A schedule is OPTIMAL if a) the number of participating climbers is minimal and b) among all groups satisfying condition a) the total of consumed supplies is minimal. Try to find a nearly optimal schedule. TECHNICAL CONSTRAINTS ===================== Constraint-1: Put your solution program into an ASCII text file named "C:\IOI\DAY-2\422-PROG.xxx". Extension .xxx is: - .BAS for BASIC programs, .C for C programs, - .LCN for LOGO programs, .PAS for PASCAL programs. Constraint-2: Programs must reject inputs where N is less than 1 or greater than 100. P must be not less than 1 and not greater than 20. EXAMPLE(S) ========== The following could be a dialogue with your program: Days to arrive to top: 4 Number of club members: 5 Maximal supply for climber 1 : 7 Daily consumption for climber 1 : 1 Maximal supply for climber 2 : 8 Daily consumption for climber 2 : 2 Maximal supply for climber 3 : 12 Daily consumption for climber 3 : 2 Maximal supply for climber 4 : 15 Daily consumption for climber 4 : 3 Maximal supply for climber 5 : 7 Daily consumption for climber 5 : 1 2 climbers needed, total amount of supplies is 10. Climber(s) 1, 5 will go. Climber 1 carries 7 and descends after 4 day(s) Climber 5 carries 3 and descends after 1 day(s) Plan another party (Y/N) Y Days to arrive to top: 2 Number of club members: 1 Maximal supply for climber 1 : 3 Daily consumption for climber 1 : 1 Climbing party impossible. Plan another party (Y/N) N Good bye SAMPLE FILES ============ For your convenience, some files containing test data and correct sample output have been prepared; please look into the directory "C:\IOI\DAY-2". WARNING: Successful execution of your program with these examples does not necessarily guarantee that your program is correct !!! CREDITS ======= User dialogue as illustrated above.......................... 10 points Find a solution for the special case where all C(i)=1 and all S(i) are equal ...................................... 20 points Find a solution for general case ........................... 20 points Find a nearly optimal solution for general case ............ 30 points Detect unsolvable situations ............................... 10 points Technical constraints obeyed ............................... 10 points ---------------------------------------------------------------------- maximal 100 points TASK 4.2.3: "RUBIK'S TOOLKIT" ============================= This problem is based on the puzzle game "Rubik's cube". If you already know Rubik's cube you may skip this paragraph and the next one. Rubik's cube is a cube that consists of 3 x 3 x 3 smaller cubes. Initially each of the six faces of Rubik's cube is coloured uniformly in a different colour; we call this the initial cube. Every face of Rubik's cube consists of 3 x 3 faces of a layer of nine smaller cubes. Imagine you are looking at any of the six faces of Rubik's cube. The layer of 3 x 3 smaller cubes you see can be rotated by a multiple of 90 degrees, where the axis of rotation is orthogonal to the face and goes through its centre. The result is another 3 x 3 x 3 cube where the colour pattern of the face you are looking at has been rotated and the colour patterns of the four neighbouring faces have changed. In our problem the faces of the cube are given names instead of colours: U=Up, R=Right, F=Front, B=Back, L=Left and D=Down. Any move sequence to turn the cube may be described as a string of the letters {U, R, F, B, L, D} where each letter stands for a basic rotation: the 90 degrees clockwise rotation of the corresponding face. PROBLEM STATEMENT with EXAMPLE(S) ================================= Write a program that allows the user to repeatedly solve any of the given three subproblems in any order. You may assume that the length of each input string is at most 35. 1. This subproblem is the translation of a given move sequence into a move sequence where no primitive rotation is applied more than 3 times in sequence. Your algorithm should reject non-legal input sequences. Some examples are provided for clearness: Input Output L --> L LL --> LL LLL --> LLL LLLL --> "the empty sequence" LLLLL --> L LLRRRFFFFRLB --> LLLB HELLO --> "error" 2. The second subproblem is to find out whether two given move sequences yield the same result when applied to the initial cube. The examples may illustrate this: Input, Input, Output 1st sequence 2nd sequence RL LR yes RU UR no RRFFRRFFRRFFRRFF FFRRFFRR yes RRFFRRFFRRFFRRFF RRFFRRFF no 3. The third subproblem is to determine how many times a given move sequence has to be applied to the initial cube until the cube is in its initial state again. The smallest such number greater zero is sought. We provide some examples: Input Output L 4 DD 2 BLUB 36 RUF 80 BLUFF 180 TECHNICAL CONSTRAINTS ===================== Constraint-1: Put your solution program into an ASCII text file named "C:\IOI\DAY-2\423-PROG.xxx". Extension .xxx is: - .BAS for BASIC programs, .C for C programs, - .LCN for LOGO programs, .PAS for PASCAL programs. SAMPLE FILES ============ none CREDITS ======= Main menu and user dialogue o.k. ........................... 15 points Subproblem 1: Transformation o.k. .......................... 20 points Rejects wrong inputs ......................... 10 points Subproblem 2: Correctness .................................. 25 points Subproblem 3: Correctness .................................. 25 points Technical constraints obeyed ............................... 5 points ---------------------------------------------------------------------- maximal 100 points