Day 1. Problem 1: THE RUNNING MAN ================================= A man has escaped from prison, and trying to avoid the polie he enters a square maze. The maze is composed of walking paths, doors and walls. Each door connects two or more paths. The maze has only one entrance, which is also the exit from the maze, and it is at the border of the maze. The police, using a remote control device, can lock any door inside the maze, except the entrance. Initially, all doors are unlocked. The location of the running man into the maze is known, and it must be on the path. The movement into the maze can have any direction, up, down, left, right but no diagonal steps are allowed. Evidently, the running man can not be on a closed door or on a wall. You are requested to help the police to trap the running man forever into the maze. However, ONLY ONE DOOR must be locked, and this door must be different than the entrance. The maximum size of the maze is 50 x 50. INPUT ===== Your program should read the input from the file INPUT.TXT, which is an ASCII file. The first line contains one positive integer number, denoting the side of the maze in cells. The next line contains the location of the running man. Each location is declared by a pair of numbers separated by a space character. In each location the first number is the horizontal coordinate and the second is the vertical coordinate. The numbering stars from the lower-left corner of the maze (1,1). The following lines (until the end of the input file) contain the description of the maze. The symbols are the following: D denotes a door, E is the entrance/exit of the maze, P is a path and W denots a wall, that no one can walk through. Any two symbols are separeted by a space character. OUTPUT ====== Your program should produce its output into the file OUTPUT.TXT as follows: The first line contains the string "YES" if it is possible to trap the running man by locking only one door, or "NO" otherwise. If the answer is YES, the next line contains an integer denoting how many doors qualify. The rest of the file contains the locations of the doors (one location per line) that if any of them is locked, then the running man can not escape the maze. Example ------- INPUT.TXT 5 4 4 W W W W W W W D P W W D P W W W P D P W W E W W W OUTPUT.TXT YES 1 3 4 TIME LIMIT PER TEST: 3 seconds ============================== Day 1. Problem 2: TASK EXECUTION ================================ Assume that we have a number of tasks that must be executed. However, the tasks are not independent to each other. We say that task 2 depends on task 1, if the execution of task2 can start after the completion of task 1. However, we may find tasks that at any given time can be executed in parallel, saving time. Given a number of tasks and their dependencies, determine the shortest time that all tasks can be executed in a computer with an infinite number of processors. Then, you are requested to determine the minimum number of processors in order to execute the tasks in the (previously found) shortest time. Each task takes 1 time unit of execution. The tasks are represented by positive integers from 1 to N (N<=200). INPUT ===== Your program should read the input from the file INPUT.TXT as follows. The first line contains a positive integer number N denoting the number of tasks to be executed in the computer, and another positive integer number M, denoting the number of dependencies. The next M lines until the end of the input file, contain the dependencies between the tasks. For example, when the input line, which corresponds to a dependency, contains the string "2 3", this means that in order to start the execution of task 3, task 2 must be completed first. Data is always correct and there is always a solution. OUTPUT ====== Your program should write the output into the file OUTPUT.TXT as follows. The file has only one line, which contains two positive integer numbers, separated by space character. The first number T denotes the minimum number of time units that we need in order to execute all tasks, assuming an infinite number of processors. The second number denotes the minimum number of processors we can use in order to execute the tasks in T time units. Example ------- INPUT.TXT 6 6 1 4 2 5 3 6 4 6 4 5 5 6 OUTPUT.TXT 4 2 TIME LIMIT PER TEST: 1 second ============================= Day 1. Problem 3: FACTORIALS ============================ For a positive integer number N, find all positive integer numbers X (if any such number exists) with the property that the number 1*2*3*...*X has exactly N decimal digits. Assume that N is at most 150,000. INPUT ----- The file INPUT.TXT has a single line which contains a positive integer number denoting the number N. OUTPUT ------ Your program should write the output into the file OUTPUT.TXT. The first line should contain the string "NO", if such a number does not exist. Otherwise, the first line should contain a positive integer denoting how many X numbers exist. The next line (until the end of the file) should contain all X numbers found, one number per line. Example ------- INPUT.TXT 5 OUTPUT.TXT 1 8 TIME LIMIT PER TEST: 2 SECONDS ============================== Day 2. Problem 1: STREET NETWORK ================================ The street network of a city is composed of streets and nodes. In a node, two or more streets can meet. All streets are one-way streets. Note also that, two nodes can be connected directly by more than one street, and one node can have a street that loops back to itself. Write a computer program in order to address the following issues: 1. Is it possible to start from at least one node A and visit ALL streets exactly once ? 2. How many nodes can serve as starting points in order to satisfy the property of the previous case ? 3. For each node X, how many paths of length S exist starting from X and ending to X, where any street or node can be visited more than once ? Input ----- Your program should read the input from the file INPUT.TXT as follows: In the first line there is a positive integer number N (N<=50), denoting the number of nodes in the city street network. The second line contains a positive integer number S (S<=3) denoting the path length. The next N lines contain the network description in matrix form. More precisely, the element in row I and column J is the number of streets from node I to node J. Output ------ Your program should generate the output in the file OUTPUT.TXT as follows: The first line contains the string "YES" if you can start from a node, travel through all streets exactly once, and arrive either at the starting point, or at another node. Otherwise, the string "NO" should appear in the output. If the answer is "YES", the next line of the output file should contain a positive integer number denoting how many nodes can serve as starting points. Finally, the last line of the output file should contain N positive integers (separated by a space) that show for each node how many different paths with length S exist such that each path leads from the node back to itself. These numbers should be sorted in increasing order. Example 1 --------- INPUT.TXT 3 2 1 1 0 1 1 1 0 1 1 OUTPUT.TXT YES 3 2 2 3 Example 2 --------- INPUT.TXT 3 2 1 1 0 1 1 2 0 0 1 OUTPUT.TXT NO 1 2 2 TIME LIMIT PER TEST: 3 seconds ============================== Day 2. Problem 2: CYCLE DETECTION ================================= Assume we have a network of computers, where each computer is connected with others by means of cables. Each cable connects exactly two computers, and two computers can be connected to each other by only one cable. Given a network of computers you are requested to determine all the cables that participate in a cycle. Also, for each cable you must determine the number of cycles in which this cable participates. A cycle is a sequence of cables, starting from computer A and leading to itself. However, each computer, other than A, in the cycle, should participate only once. Input ----- Your program should read the input from the file INPUT.TXT as follows. The first line contains a positive integer number N (N<=20) denoting the number of computers in the network. The next N lines describe the computer connections in a matrix form. Thus, each line has N elements, separated by a space character. If an entry in line L and column C is 0, this means that there is no direct connection between computers L and C. Otherwise there is a direct connection between them. Output ------ Your program should write the output into the file OUTPUT.TXT as follows. The first line contains a positive integer denoting the number M of cables that participate in at least one cycle. Then, one line follows, containing a sequence of M positive integer numbers (separated by a space character) representing the number of cycles that each cable participates in. This sequence must be sorted in increasing order. If there is no cable that participates in cycle(s), the output file should contain a single line with the string "NO CYCLE". Example 1 --------- INPUT.TXT 6 0 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 OUTPUT.TXT 7 2 2 2 2 2 2 2 Example 2 --------- INPUT.TXT 4 0 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 OUTPUT.TXT NO CYCLE TIME LIMIT PER TEST: 2 seconds ============================== Day 2. Problem 3: QUADTREES =========================== A binary image is an image containing pixels colored by only two colors, either black or white. We assume that each binary image is composed by N x N pixels, where N is a power of 2 and N<=1024. Given two binary images I1 and I2, their intersection is a new binary image I3, such that a pixel in I3 is black if and only if it is black in both I1 and I2. A quadtree is a rooted tree which represents a binary image. The root corresponds to the whole image. If the image is one colored (black or white), the quadtree contains only the root labeled with 'b' if ot is black, and 'w' if it is white. Otherwise, the root is labeled 'i' (standing for "internal"), and the image is split to 4 equal parts (see figure), which are also binary images. For each of these new subimages, the procedure is the same. If any of these 4 subimages is 0-colored or 1-colored, then it is labeled 'b' or 'w' respectively. Otherwise, it is split in 4 sub-subimages. This procedure may be repeated until the pixel level at most. The numbering of the children of a parent node is illustrated in the following figure. Subquadrant 1 is placed as the left-most child, and subquadrant 4 is placed as the right-most child in the quadtree representation. The same rule is followed recursively for all the levels of the quadtree. ________ ________ | | | | 2 | 1 | BBWB i | | | BBWW i b b w |________|________| WWBB b w w w | | | WWBB | 4 | 3 | | | | |________|________| In the pre-order traversal of a quadtree, we first visit the root. Then, after the root we visit its 4 children (if they exist), following the above given ordering. For each of these 4 children, the same rule applies in a recursive way, where every child is taken as the root of the corresponding subtree. Your job is, given the preorder traversal of two quadtrees (corresponding to two images) to find the number of nodes contained in the quadtree of their intersection. Input ----- Your program should read the input from the file INPUT.TXT as follows. The first line contains a positive integer number denoting the size N of the images. The next two lines contain the preorder strings of the quadtrees of two images (one string per line). Each string represents the preorder traversal of the quadtree of the corresponding image. In the preorder string, three characters are allowed: 'i' denoting an internal node, 'b' denoting a black quadrant and 'w' denoting a white quadrant. Output ------ Your program should write the output into the file OUTPUT.TXT. The file containes one line, denoting the total number of nodes (leaf + internal) of the quadtree corresponding to the intersection. Example ------- INPUT.TXT 4 iiwwwbibbwwbw iwbwiwwbw OUTPUT.TXT 9 TIME LIMIT PER TEST: 3 seconds ==============================