ACM ICPC: The Northeast North America Regional Final Rochester Institute of Technology, November 15, 2014 Problem 1: Avoidland Avoidland is a puzzle played on an n × n board with n pawns. The pawns are initially placed on the squares of the board, at most one pawn per square. The goal is to move the pawns so that they “avoid” each other – there cannot be a row or a column with more than one pawn. In one move a pawn can move to a neighboring unoccupied square, that is, a square that shares a side with the pawn’s current location and there is no pawn on it. Given the initial locations of the pawns, what is the minimum number of moves needed to solve the puzzle? Input specification: The first line contains k, the number of Avoidland puzzles. Each Avoidland puzzle is described on several lines. The first line contains n, then n lines follow. The i-th line contains the initial row and column coordinates of the i-th pawn, separated by space. Each coordinate is an integer between 1 and n. You may assume that n is at most 1,000,000. Output specification: The output contains one line for each Avoidland puzzle. The line contains the minimum number of moves needed to solve the puzzle. Sample input: 2 3 1 3 2 3 3 1 4 1 4 1 4 4 1 1 4 Sample output: 1 4 Explanation: For sample input 1, we can move the second pawn to location (2,2). For sample input 2, we can move the first pawn to location (1,3), then to location (2,3), and then move the second pawn to location (3,1), then to location (3,2). 1 ACM ICPC: The Northeast North America Regional Final Rochester Institute of Technology, November 15, 2014 Problem 2: Brick Wall Pat and Mat are trying to build a brick wall. They have three types of bricks – all have the same depth and height but they are of three diﬀerent widths: 1, 2, and 3. As every builder knows (and Pat and Mat learned after watching their walls fall down quite a few times), a wall is built by layering rows of bricks, with the added requirement that for any two neighboring bricks there has to be a brick above that covers the connection of the two bricks (unless the bricks are in the top-most row). Pat and Mat somehow managed to build quite a few rows and now they are about to do the last row. But they are having troubles ﬁguring out whether it is possible to build the last row so that all connections in the row below are covered. Of course, all the rows have to be of the same length and aligned on the sides. Help! Input specification: The ﬁrst line contains k, the number of diﬀerent walls that need to be ﬁnished. Then 2k lines follow, where every wall is described on two lines. The ﬁrst of these lines contains four numbers N, c1 , c2 , c3 , separated by spaces, where N is the number of bricks in the (currently) top-most row and ci describes the number of bricks of width i for i = 1, 2, 3 that are available for the last row. The second line describes the currently top-most row – it contains a sequence b1 , b2 , . . . , bN of brick lengths for the bricks that form the row, in the order given by the sequence. You may assume that N is at most 100 and each of c1 , c2 , and c3 is at most 300. Output specification: The output contains one line for each wall. The i-th line contains the string ”YES” if it is possible to build the last row for the i-th brick wall, and ”NO” otherwise. Sample input: 3 5 2 5 2 5 2 2 3 1 3 6 3 1 1 2 1 1 1 3 3 2 3 3 2 1 2 3 Explanation: For the ﬁrst sample input, a possible solution is shown in the ﬁgure below, with one brick of length 2 unused. Sample output: YES NO NO 1 ACM ICPC: The Northeast North America Regional Final Rochester Institute of Technology, November 15, 2014 Problem 3: Cake ˇ Zofka really likes cakes. Her most recent favorite is a rectangular-shaped cake with hard chocolate glazing and white marzipan roses on top. The glazing has been pre-cut in a gridlike pattern at the bakery since this type of glazing is diﬃcult to cut after it hardens. The bakers pride themselves in creating various creations with the roses – they place every rose in the middle of one of the grid squares (at most one rose per square) but the placement ˇ diﬀers each time. Zofka invited her friends to share the cake with her - together with her there are as many people as there are roses on the cake as she and each of her friends like ˇ a piece with a rose. Zofka can cut only rectangular pieces of the cake along the grid lines. How should she cut the cake so that she and each of her friends gets a rectangular piece with a rose and there is the smallest possible amount of leftover cake? Input specification: The ﬁrst line contains k, the number of cakes. Each cake is described on several lines. The ﬁrst line contains p, q, and n, where p × q are the dimensions of the cake and n is the number of roses. Then n lines follow, the i-th line contains the coordinates of the i-th rose, where the ﬁrst coordinate is between 1 and p and the second coordinate is between 1 and q. You may assume that p and q are at most 10,000. Output specification: The output contains n + 1 lines for each cake. The ﬁrst n lines contain four numbers each: the j-th line contains aj , bj , cj , dj , where 1 ≤ aj ≤ cj ≤ p and 1 ≤ bj ≤ dj ≤ q and (aj , bj ) and (cj , dj ) correspond to the grid squares at the opposite corners of the rectangular piece for the j-th person. The rectangular pieces have to be non-overlapping. The last line contains a single number, the area of the leftovers. The area of the leftovers should be the smallest possible. Sample input: Explanation: 1 4 2 3 1 4 A possible solution for the sample input is shown in the ﬁgure below. The rectangular pieces cover the cake entirely, so there are no leftovers. This solution is described in the sample output. Note that there are several other correct outputs for the sample input. 5 4 2 4 4 5 Sample output: 1 3 3 1 0 1 1 5 4 2 4 4 2 3 4 5 5 1 ACM ICPC: The Northeast North America Regional Final Rochester Institute of Technology, November 15, 2014 Problem 4: Cover up Dezider is making a game board for the game of Convexity. He drilled a bunch of holes in a piece of wood. As the name of the game suggests the holes were on the boundary of a convex polygon. After turning over the piece of wood, Dezider froze—he had damaged the famous Picasso lithograph—The Bull No. 8. Now the question is: how to fix the damage? Drawing a bunch of straight lines to cover the holes seems like a good repair method but, of course, Dezider would like to draw as few lines as possible. He needs your help. Write a program that, given the positions of the holes, finds the smallest number of straight lines that can cover the holes. Input specification: The first line contains k, the number of problems. Each of the next k lines contains a description of one problem. The line starts with n, the number of holes. Then 2n numbers, the coordinates of the holes, follow. You can assume n ≤ 1,000 and the coordinates are integers between -1,000,000 and 1,000,000. The holes lie on the boundary of a convex polygon. Output specification: The output contains one line for each problem. The line for the i-th problem contains the smallest number ℓ, such that ℓ straight lines can cover the holes. Sample input: 2 4 0 0 1 1 1 0 0 1 8 0 0 2 2 0 2 2 0 1 0 1 2 0 1 2 1 Sample output: 2 3 1 ACM ICPC: The Northeast North America Regional Final Rochester Institute of Technology, November 15, 2014 Problem 5: Hopper A hopper is a virtual creature that visits Java programs and explores their arrays. Scientists observed a hopper and came to the following conclusions: • a hopper only visits arrays with integer entries, • a hopper always explores a sequence of array elements using the following rules: – a hopper cannot jump too far, that is, the next element is always at most D indices away (how far a hopper can jump depends on the length of its legs), – a hopper doesn’t like big changes in values—the next element diﬀers from the current element by at most M , more precisely the absolute value of the diﬀerence is at most M (how big a change in values a hopper can handle depends on the length of its arms), and – a hopper never visits the same element twice. • a hopper will explore the array with the longest exploration sequence. The scientists now need to prepare arrays for further study of hoppers and they need your help. They want a program that given an array and values D and M computes the length of the longest exploration sequence in the array. Input specification: The ﬁrst line contains k, the number of problems. Then descriptions of the problems follow. Each problem is described on two lines. The ﬁrst line of a problem description contains three numbers n, D, M , where n is the length of the array (as described above, D is the maximum length of a jump the hopper can make, and M is the maximum diﬀerence in values a hopper can handle). The next line contains n integers—the entries of the array. We have 1 ≤ D ≤ 7, 1 ≤ M ≤ 10, 000, 1 ≤ n ≤ 10, 000 and the integers in the array are between −1, 000, 000 and 1, 000, 000. Output specification: The output contains one line for each problem—the length of the longest exploration sequence. The hopper can start and end at any location and the length is computed as the number of visited locations. Sample input: Sample output: 3 8 1 8 1 8 1 8 3 2 3 7 2 7 1 7 1 8 2 6 4 3 5 1 8 2 6 4 3 5 1 8 2 6 4 3 5 1 ACM ICPC: The Northeast North America Regional Final Rochester Institute of Technology, November 15, 2014 Problem 6: Origami Filip found a pile of square origami papers. In preparation for winter, and partly because he did not really know what origami is, he decided to cut the papers into smaller pieces, place the pieces on the blades of his ceiling fan, and turn the fan on. (He has a loft bed so he can reach the ceiling fan easily.) As the pieces blew away, he watched it “snow”, over and over. Now Filip is a little older, wiser, and he needs to clean his room. As he is picking up the pieces of cut paper, he notices that there are nice patterns on them. He sorts them by patterns and now he would like to tape them back together the way they used to be. Each paper was a square, though the squares were of several diﬀerent sizes. The trouble is, Filip is not sure if he found all the pieces! Help him ﬁgure out whether he can form a square out of the pieces he got. Each piece is a polygon (Filip is very proud of his straight-line cutting abilities) and each piece originally touched the boundary of the square. Filip remembers that he cut each square into at most 5 pieces. To form a square, the pieces cannot overlap. The patterns on the pieces allow us to orient them so that it is suﬃcient to consider only 90 degree rotations; however, you may need to ﬂip some pieces over. Input specification: The ﬁrst line contains k, the number of diﬀerent origami patterns. The pieces for each pattern are described on several lines. The ﬁrst line is empty, followed by a line that contains n, the number of paper pieces of the current pattern. Then 2n lines follow. The (2i − 1)-st line contains pi , the number of vertices of the i-th polygon piece. The (2i)-th line contains coordinates x1 , y1 , x2 , y2 , . . . , xpi , ypi . The coordinates represent the polygon – traversing through the points outlines the shape of the polygon (counterclockwise). You may assume that such traversal will be non-self-crossing. The number of pieces n is at most 5, every polygon has at most 30 vertices, and the coordinates are integers between -10 and 10. Output specification: The output contains one line for each origami pattern. The line contains the word “YES” if it is possible to ﬁt the pieces together to form a square, and “NO” otherwise. Sample input: 3 6 1 1 1 5 0 5 0 3 -1 3 -1 1 6 0 0 2 0 2 4 0 4 1 3 0 2 5 -1 -1 1 -1 1 0 0 1 -1 0 1 3 4 0 0 1 0 1 4 0 4 3 3 3 7 3 7 6 3 3 3 7 3 7 6 2 6 0 1 4 1 4 0 5 0 5 4 0 4 6 0 0 5 0 5 1 2 1 2 2 0 2 Sample output: YES YES NO Explanation: Figures corresponding to the three sample inputs are below. Sample input 1: Sample input 2: Sample input 3: 2 ACM ICPC: The Northeast North America Regional Final Rochester Institute of Technology, November 15, 2014 Problem 7: Rebel Die The rebel die needs to escape from the board prison. To accomplish the escape it needs to blend in with the board on its way. Unfortunately, the guards colored the board using various colors and ﬁguring out the correct camouﬂage seems very diﬃcult. The die is trying to get from the top-left corner square to the bottom-right corner square. Fortunately, its sides are of the same size as the squares of the grid and each grid square is colored by a single color. The die wants to color its sides to blend in. The only moves it can do is to ﬂip (along an edge) onto one of the neighboring squares (for most squares there are four neighboring squares). To go unnoticed the top color of the die must always match the color of the square on which it is (in particular, in the starting position the top color of the die must match the color of the top-left corner square and in the ﬁnal position the top color of the die must match the color of the bottom-right corner square). The die cannot do any other moves (for example, it cannot rotate on a square). Please help the die to ﬁgure out if a good camouﬂage exists. Input specification: The ﬁrst line contains k, the number of boards. Each board is described on several lines. The ﬁrst line contains two integers m (the height of the board) and n (the width of the board). Then m lines follow. Each of the m lines contains n integers. Each integer encodes a color. Assume that 1 ≤ m, n ≤ 100 and the colors are integers from {0, 1, . . . , 29}. Output specification: The output contains one line for each board. The line for a board contains “YES” if there exists a coloring of the die that allows the die to ﬂip from the top-left corner square (the square in ﬁrst column of the ﬁrst row) to the bottom-right corner square (the square in the last column of the last row) on that board. If such a coloring does not exist then the line contains “NO”. Sample input: 2 4 0 0 2 5 4 0 1 2 3 4 1 4 4 6 4 1 2 3 4 2 0 1 7 3 0 4 8 2 3 4 5 3 4 5 6 1 Sample output: YES NO Explanation: For the ﬁrst sample input, the coloring for the rebel die is shown below on a cube net. This is the only camouﬂage that allows the die to get from the top-left corner to the bottom-right corner and there is only one way how to do so. 0 0 2 5 4 1 0 2 8 3 2 1 4 4 6 2 0 1 7 3 0 4 8 ACM ICPC: The Northeast North America Regional Final Rochester Institute of Technology, November 15, 2014 Problem 8: Sheep Pen David and Martin retired from their jobs and became shepherds. After each winter they need to rebuild the sheep pen. Each year they have a diﬀerent collection of straight fence segments of various lengths. Naturally, they want to build a sheep pen that covers the largest area. They always spend a lot of time choosing, rearranging, and placing the segments but they are never sure whether they got the optimal solution. Please help them. Input specification: The ﬁrst line contains k, the number of years. Then k lines follow. Each line starts with n, the number of fence segments and then contains a list of n integers, the lengths (in meters) of the fence segments. The lengths are integers between 1 and 100. The number of fence segments n is between 3 and 50. Output specification: The output contains one line for each year. The line for year i contains the maximum area (in square meters) of a polygon whose sides have lengths given by the input for the i-th year. Not all segment lengths listed need to be used. The answers should be output with precision of two decimal places (rounded to the nearest number with two decimal digits). If no sheep pen can be built, output 0.00. Sample input: 3 4 1 1 1 1 3 1 1 1 5 1 1 2 2 7 Sample output: 1.00 0.43 2.00 1

© Copyright 2020 ExploreDoc