We can all benefit by doing occasional "toy" programs, when artificial restrictions are set up, so that we are forced to push our abilities to the limit. … The art of tackling miniproblems with all our energy will sharpen our talents for the real problems. Donald E. Knuth Quarterfinal Central region of Russia Rybinsk, October 17-2013 1. Box of Bricks (64 Mb, 1 sec / test)........................................................................2 2. Hanoi tower (64 Mb, 1 sec / test)..........................................................................2 3. Plunder & Flee – 2 (64 Mb, 1 sec / test)................................................................4 4. Blobs' Exhibition (64 Mb, 1 sec / test)..................................................................5 5. Number Game (64 Mb, 1 sec / test).......................................................................6 6. Evil & Odious (64 Mb, 1 sec / test).......................................................................6 7. Checkers (64 Mb, 1 sec / test)...............................................................................7 8. Redirect (64 Mb, 3 sec / test).................................................................................8 9. Klingon Battle Bagel (64 Mb, 1 sec / test)..........................................................11 10. Meteorite (64 Mb, 1 sec / test)...........................................................................12 11. Triangles (64 Mb, 1 sec / test)...........................................................................13 Input file name Output file name: INPUT.TXT OUTPUT.TXT 2011-2012 ACM Central Region of Russia Quarterfinal Programming Contest 1. Box of Bricks (64 Mb, 1 sec / test) Pasha assembled box of bricks in the form of a rectangular parallelepiped and thought over the question: what is a minimal number of bricks lay on the route between two opposite corners of the parallelepiped, if it is allowed to pass from brick to other brick through the common face, edge or vertex? In the figure opposite bricks are highlighted. Help Pasha to write a program that calculates minimal number of bricks on the route. Input Integer n, m, k – the size of rectangular parallelepiped (in bricks). Output Integer – the minimal number of bricks. Limitations 1 ≤ n, m, k ≤ 1000 Example Input.txt 3 3 3 2. Output.txt 3 Hanoi tower (64 Mb, 1 sec / test) Each programmer knows the puzzle “The Hanoi Tower”. We will briefly remind you the conditions of this task. There are 3 pivots: A, B, C. Initially, n disks of different diameter are placed on the pivot A: the smallest disk is placed on the top and every next one is placed in an increasing order of their diameters. The second and the third pivots are still empty. You have to move all the disks from pivot A to pivot B, using pivot C as an auxiliary. By one step you can take off 1 upper disk and put it either on an empty pivot or on another pivot over a disk with a bigger diameter. Almost all books on programming contain a recursive solution of this task. In the following example you can see the procedure, written in Pascal. Procedure Hanoi (A, B, C: integer; N:integer); Begin If N>0 then Begin Hanoi (A, C, B, N-1); Writeln(‘Disk ’, N, ‘ from ‘, A, ‘ to ‘, B); Hanoi (C, B, A, N-1) 2 2011-2012 ACM Central Region of Russia Quarterfinal Programming Contest End End; The number of step Disk From To Combination 0. AAA 1. 1 A B BAA 2. 2 A C BCA 3. 1 B C CCA 4. 3 A B CCB 5. 1 C A ACB 6. 2 C B ABB 7. 1 A B BBB Here, for example, the combination «BСA» indicate that the smallest disk is on pivot B, the medium one is on pivot С, the biggest one is on pivot A. The members of jury, in preparation for the championship, played this exciting game, from time to time making notes of current combinations (each on a separate sheet of paper). However, later, the sheets with recorded combinations were mixed. Write a program that establishes if the given combination is occurred during the game. Input The first line of an input file contains two integer n – the number of disks, and m – the number of combinations. The following m lines contain m combinations. Each combination contains n capital letters (“A”, “B” or “C”) – the disposition of the n disks between the pivots. The first (leftmost) letter designates position (a pivot name) of the smallest disk, the second letter – position of the second largest, and so on… Output The output file must contain m lines – m combinations sorted in order of their appearing in game. Limitations 1 ≤ n ≤ 250; 1 ≤ m ≤ 1000 Example Input.txt 3 4 ACB ВСА ABB BAA Output.txt BAA ВСА ACB ABB Input.txt 3 1 BCA Output.txt BCA 3 2011-2012 ACM Central Region of Russia Quarterfinal Programming Contest 3. Plunder & Flee – 2 (64 Mb, 1 sec / test) Hacker Kirill successfully coped with the task that "Plunder & Flee Inc." management had set before him last year, and he was transferred to the central office. Now he faces a new challenge of improving the computer network in the central office. The network consists of n workstations coupled by n–1 network cables; each pair of workstations has at most a single connection. Information is relayed between stations until it reaches the recipient. Currently, the network is set up in such a way that only a single route exists between any two stations. The solution is cheap but it has a major shortcoming: any cable failure renders the network inoperable. The management asked Kirill to improve the network using the least possible number of additional cables so as to keep the network operational in case of a single cable failure. Write a program that, given the network structure, will determine the minimum number of additional cables necessary to improve the network as described above. Limitations 2 ≤ n ≤ 1000; 1 ≤ ai, bi ≤ n. Input The first line of the input file contains integer n, the number of workstations in the network. The following n–1 lines describe the communication links. They contain space-delimited numbers of workstations connected by cable i: integers ai and bi. The workstations are identified with natural numbers ranging from 1 to n. Output The first line of the output file should contain integer m, the number of additional cables. Then m lines should follow, each consisting of a space-delimited pair of integers denoting the numbers of newly connected stations. Example Input.txt 3 1 2 2 3 Output.txt 1 1 3 Input.txt 4 1 4 2 4 3 4 Output.txt 2 1 2 2 3 4 2011-2012 ACM Central Region of Russia Quarterfinal Programming Contest 4. Blobs' Exhibition (64 Mb, 1 sec / test) Blobs, a renowned painter from Flower Town is about to have a solo show at the local art gallery. He presented k works to be exhibited but unfortunately the gallery has only n exhibit spaces. Each exhibit space is a wall-mounted painting holder. During preparations it turned out that the holders are designed for paintings of different weight. Holder number i can carry an exhibit weighting no more than di grams. As it is impossible to display all the works anyway, Blobs estimated the artistic value ai of each painting. He also weighted all of them to know the weights wi (in grams). Please help Blobs in selecting a set of paintings to be displayed, maximizing the total artistic value. Write a program that will map the set of paintings having the maximum total artistic value to the available exhibit spaces. If several optimal solutions exist, any of them will be accepted as correct. Limitations All numbers are integer. 1 ≤ n ≤ k ≤ 10 000; 1 ≤ di, aj, wj ≤ 1 000 000; 1 ≤ i ≤ n; 1 ≤ j ≤ k. Input The first line of the input file contains two space-delimited integers n and k. The second line contains n space-delimited integers describing maximum loads for holders: d1, d2, d3, … dn. Then k lines follow, with two space-delimited numbers each: aj and wj, the artistic value and the weight of the j-th painting. The paintings are listed in ascending order of numbers: the third line of input contains a1, w1, the fourth – a2, w2, the fifth – a3, w3, and so on. Output The output file should contain n integers separated with spaces—the numbers of paintings to be placed in corresponding exhibit spaces. Here, the number in position i is the number of painting to be displayed in the exhibit space i. If an exhibit space is empty then output 0 in the corresponding position. Example Input.txt 5 10 1 2 3 4 5 10 3 4 3 11 8 1 5 5 8 7 1 5 5 8 3 4 2 7 3 Output.txt 6 9 1 8 10 5 2011-2012 ACM Central Region of Russia Quarterfinal Programming Contest 5. Number Game (64 Mb, 1 sec / test) Vasya, a school whiz kid, feels bored during math classes, so he occasionally plays different games with Petya, a non-achiever who shares a desk with him. Once, Vasya proposed to play the following game. Petya picks two successive prime numbers, multiplies them and tells the product to Vasya, who is to find out the numbers. First, Vasya had to explain that two primes are successive if there are no other primes between them. Petya was surprised to see how quickly Vasya figured out the numbers. Then Vasya proposed that they switch roles. Please help Petya to find the chosen numbers. Write a program to find two successive prime numbers x and y given their product. Limitations 2 ≤ x < y ≤ 106; x, y are successive prime numbers. Input The input file contains a single integer, the arithmetical product of x and y. Output The output file should contain two space-delimited integers x and y, the least of them going first. Example Input.txt 15 Input.txt 35 Input.txt 77 6. Output.txt 3 5 Output.txt 5 7 Output.txt 7 11 Evil & Odious (64 Mb, 1 sec / test) A non-negative integer is called evil if has an even number of ones in its binary representation. Similarly, a non-negative integer is called odious if has an odd number of ones in its binary representation. Let us write down evil and odious numbers in ascending order. Number index 1 2 3 4 5 6 7 8 9 10 11 12 13 14 … Evil number 0 3 5 6 9 10 12 15 17 18 20 23 24 27 … Odious 1 2 4 7 8 11 13 14 16 19 21 22 25 26 … number Let E(n) be the n-th evil number in this list. Similarly, let O(n) be the n-th odious number. Write a program to calculate the sum of n-th evil and odious numbers E(n) + O(n) given their index n. 6 2011-2012 ACM Central Region of Russia Quarterfinal Programming Contest Limitations 1 ≤ n ≤ 1 000 000. Input The input file contains a single integer, n. Output The output file should contain a single integer, the sum E(n) + O(n). Example Input.txt 1 Input.txt 10 7. Output.txt 1 Output.txt 37 Checkers (64 Mb, 1 sec / test) An 8×8 chess board is used to play checkers. Each player starts with 12 normal pieces (“men”) on the black squares of the three rows closest to their own side. During of the game, the pieces may only move on unoccupied black squares. The players take turns moving one of the pieces. A normal piece can slide diagonally forward to an adjacent square. Forward direction is defined as the direction toward the last row, which is the most distant from the player. A normal piece can capture an opponent's piece. To do so, the piece is moved two squares diagonally in any direction “jumping over” the opponent's piece, which is later removed from the board. If the new position of the jumping piece allows to capture another opponent's piece (either “man” or “king”) then the move is continued until the jumping piece reaches the position where capture is not possible. A single opponent's piece can be jumped over only once during a move. Captured pieces are removed from the board only when the move is finished. Jumping is mandatory. When there is more than one way for a player to jump, one may choose which sequence to make. Write a program that will analyze the given checkers position and determine the maximum number of black pieces that can be captured by white in a single move, assuming there are no “kings” in the game. Input The input file consists of 8 lines, 8 characters each. Capital Latin letters “W” are used to denote white pieces, “B” for black. Empty squares of the board are marked with period characters (“.”). Output The output file should contain a single integer, the maximum number of black pieces that can be captured by white in a single move, for the given position. 7 2011-2012 ACM Central Region of Russia Quarterfinal Programming Contest Example Input.txt ........ ........ .B.B.B.. ........ .B.B.... ........ .B.B.... W....... Input.txt ........ ........ .B.B.B.. ........ .B.B.... ........ ...B.... W....... 8. Output.txt 6 Output.txt 0 Redirect (64 Mb, 3 sec / test) It is well known that Web search deals with electronic documents available at certain addresses (links) on the net. However, the address of a document is not necessarily unique, and a single document may be accessed through multiple links. Let us consider a special case of this situation – link redirection. When the client requests a page at address A, the server responds with a special code providing the address of a new page B, and the client navigates to this address. This process is known as redirection. Page B may as well redirect the client to a new page C and so on. Thus, the same document is made available at addresses A, B and C. Redirection data can come from various sources, e. g. from a web crawler that takes link A during scheduled crawling and goes through the whole chain of redirects. Another source may be Twitter API: tweets always contain so-called shortened links (tinylinks), and links to the original documents can be obtained from the extended data in tweets. If you have multiple sources, conflicts may arise: suppose, first we obtained data from Twitter (A->B), then the crawler takes link A leading in D. Alternatively, the service may have been overloaded, and at first the crawler received an error attempting to retrieve document A, though later the service became operational, and the crawler reached the target document at the second attempt. Also, the link may become invalid if the document is outdated. If we want to compute some statistics for the document, say, the number of links to this document, we need a way to bring all the references to some “common denomi8 2011-2012 ACM Central Region of Russia Quarterfinal Programming Contest nator”. The most practical “denominator” is the final link in the redirect chain. U is said to be the final link in the redirect chain if there is no redirect U->V leading to link V. The final link in the redirect chain will be also called the true address of the document. You are given information about N redirects, each being a pair <ui vi> (1 ≤ i ≤ N,), where ui is the original link, and vi is the link this redirect leads to. The redirect may come in the form <ui NULL> meaning that link ui is invalid. The links are given in the order of entry, i. e., the redirect occurring later in the list contains more up-to-date information. Write a program to process the available information about redirects and to determine the true address of the document for each of the M links. When solving the problem, the following conflicts may arise: if the chain of redirects for some link U is looped we suppose that the true address of this link is NULL; if several redirection options exist for some link U we consider the latest redirect as the correct one; if there is no information about redirects for some link U we suppose that the true address of this link is U. Limitations 1 ≤ N, M ≤ 100 000 0<|vi|,|ui|,|qi|≤10. (The length of each vi, ui, qi will not exceed 10 characters.) Links may contain uppercase and lowercase letters, numbers, and the following 15 characters listed inside the quotation marks: “& ? ! # ; ( ) . % : + - _ ~ / ”. Input The first line of the input file contains integer N. Each of the following N lines contains two links ui vi separated by one or more space characters. Line number N+2 contains integer M. The following M lines contain links qi, for which the true addresses are to be found. Output The output file should contain M lines, each being the true address of link qi. Example Input.txt 2 youtu.be/J NULL t.co/iqrw youtu.be/J 1 t.co/iqrw Input.txt 5 ti.ny/doc1 ti.ny/doc2 ti.ny/doc2 ti.ny/doc1 Output.txt NULL Output.txt NULL NULL jfgi.ru 9 2011-2012 ACM Central Region of Russia Quarterfinal Programming Contest ti.ny/doc3 ti.ny/doc2 t.co/asdqt bit.ly/sos bit.ly/sos jfgi.ru 4 ti.ny/doc1 ti.ny/doc3 t.co/asdqt ya.ru ya.ru 10 2011-2012 ACM Central Region of Russia Quarterfinal Programming Contest 9. Klingon Battle Bagel (64 Mb, 1 sec / test) Two opponents play a game on a checkered field of size N×M. The first player places several shapes of “Klingon battle bagel” spaceship in the field. The shape of the ship is a solid 3 × 3 square having a hole in the center (see Fig.). Ships X X X can touch the edges of the field and each other but cannot intersect. The second player tries to find all the ships, firing at the cells of the X X field. The second player has made K shots at different cells hitting the X X X ships, and F shots at other cells that missed. Write program to calculate the minimum and the maximum number of ships that can be located in the field. Input The number of rows N and the number of columns M of the playing field are given in the first line of the input file, separated with a space character. The second line contains the number of hits H and the number of misses F. Output Space-delimited values of the minimum and the maximum number of ships possibly located on the field. Output “BAZINGA!” (without quotation marks) if no solution exists for the input data. Limitations 1 ≤ N, M ≤ 100 000. 0 ≤ H, F ≤ N×M; 0 ≤ H, F ≤ N×M. Example Input.txt 7 7 1 1 Input.txt 7 7 5 13 Input.txt 3 3 9 0 Output.txt 1 4 Output.txt 1 4 Output.txt BAZINGA! 11 2011-2012 ACM Central Region of Russia Quarterfinal Programming Contest 10. Meteorite (64 Mb, 1 sec / test) The Ministry of Emergency Situations (MES) was informed about the fall of a large meteorite that exploded in the atmosphere. The employees promptly examined the impact site and mapped the affected area in detail. It turned out that the affected area is bounded by a complex-shape polygon M. Unfortunately, there is a large city in this area. The boundaries of the city also represent a polygon, G. It is natural to expect that the major damage requiring the intervention of MES occurred at the intersection of polygons M and G. As an urgent measure, it was decided to calculate the number of separate parts of the city falling into the major damage zone. Note that none of the vertices of polygons M and G lies on the boundary of another polygon. Write a program that calculates the number of parts in the intersection of polygons M and G. Input The first line contains integer N, the number of vertices in polygon M. The following N lines contain the coordinates of the vertices of M in the order of contour traversal. Coordinate values are separated with one or several space characters. The next line contains integer K, the number of vertices in G, and the following K lines contain the coordinates of its vertices. Output Output a single number – the count of separate parts in the intersection of polygons M and G. Limitations 3 ≤ N, K ≤ 300 All coordinates are non-negative integers not exceeding 32000. Example Input.txt 4 0 0 3 5 7 1 4 3 3 2 2 2 0 7 2 Output.txt 2 12 2011-2012 ACM Central Region of Russia Quarterfinal Programming Contest 11. Triangles (64 Mb, 1 sec / test) N nails are hammered in the wall. Some pairs of nails are connected with wires, possibly multiple. You may assume that there are no wires connecting nail to itself. Each wire is colored: white, blue, or red. We say that three wires form a triangle if there is a cycle connecting three nails. We call a triangle multi-colored if it is formed by wires of three distinct colors. Write a program to compute the number of multi-colored triangles for a given list of wires. Input The first line of the input file contains two space-delimited numbers N and M—the number of nails and the number of wires. Each of the following M lines contains three integers: numbers of nails being connected by a wire, and the color of that wire. The color is indicated by integers 1, 2, or 3. Output The output file should contain a single integer, the number of multi-colored triangles. Limitations 2 ≤ N ≤1000 0 ≤ M ≤ 3000 Example Input.txt 4 8 1 2 1 1 3 1 2 3 1 1 3 2 1 4 3 1 4 3 4 3 1 3 4 2 Output.txt 4 Example explanation The multi-colored triangles are formed by the following triples of wires: • (1,3,1), (3,4,2), (1,4,3); • (1,3,1), (3,4,2), (1,4,3); • (1,3,2), (4,3,1), (1,4,3); • (1,3,2), (4,3,1), (1,4,3). 13 2011-2012 ACM Central Region of Russia Quarterfinal Programming Contest Please note. In the example, the first and the second triangles, as well as the third and the fourth ones seem to be identical, however, given that there are two wires of the same color between the nails #1 and #4, the triangles are considered to be different as different wires are used to form the triangles. © RSATU, 2013 (http://www.rsatu.ru) Task authors: © Sergey G. Volchenkov, 2013 © Vladimir N. Pinaev, 2013 © Michael Y. Kopachev, 2013 © Alexander Kiselyov, 2013 © Oleg Strekalovsky, 2013 ([email protected]) ([email protected]) ([email protected]) ([email protected]) ([email protected]) 14

© Copyright 2017