Author:  Andrew Stankevich (text)  Time limit:  2 sec  
Input file:  ancient.in  Memory limit:  64 Mb  
Output file:  ancient.out 
Ancient Roman empire had a strong government system with various departments, including a secret service department. Important documents were sent between provinces and the capital in encrypted form to prevent eavesdropping. The most popular ciphers in those times were so called substitution cipher and permutation cipher.
Substitution cipher changes all occurrences of each letter to some other letter. Substitutes for all letters must be different. For some letters substitute letter may coincide with the original letter. For example, applying substitution cipher that changes all letters from 'A' to 'Y' to the next ones in the alphabet, and changes 'Z' to 'A', to the message 'VICTORIOUS' one gets the message 'WJDUPSJPVT'.
Permutation cipher applies some permutation to the letters of the message. For example, applying the permutation < 2, 1, 5, 4, 3, 7, 6, 10, 9, 8 > to the message 'VICTORIOUS' one gets the message 'IVOTCIRSUO'.
It was quickly noticed that being applied separately, both substitution cipher and permutation cipher were rather weak. But when being combined, they were strong enough for those times. Thus, the most important messages were first encrypted using substitution cipher, and then the result was encrypted using permutation cipher. Encrypting the message 'VICTORIOUS' with the combination of the ciphers described above one gets the message 'JWPUDJSTVP'.
Archeologists have recently found the message engraved on a stone plate. At the first glance it seemed completely meaningless, so it was suggested that the message was encrypted with some substitution and permutation ciphers. They have conjectured the possible text of the original message that was encrypted, and now they want to check their conjecture. They need a computer program to do it, so you have to write one.
No.  Input file (ancient.in ) 
Output file (ancient.out ) 

1 


2 


3 


4 


5 


Author:  Michail Mirzayanov (original idea), Roman Elizarov (text)  Time limit:  2 sec  
Input file:  box.in  Memory limit:  64 Mb  
Output file:  box.out 
Ivan works at a factory that produces heavy machinery. He has a simple job — he knocks up wooden boxes of different sizes to pack machinery for delivery to the customers. Each box is a rectangular parallelepiped. Ivan uses six rectangular wooden pallets to make a box. Each pallet is used for one side of the box.
Joe delivers pallets for Ivan. Joe is not very smart and often makes mistakes — he brings Ivan pallets that do not fit together to make a box. But Joe does not trust Ivan. It always takes a lot of time to explain Joe that he has made a mistake.
Fortunately, Joe adores everything related to computers and sincerely believes that computers never make mistakes. Ivan has decided to use this for his own advantage. Ivan asks you to write a program that given sizes of six rectangular pallets tells whether it is possible to make a box out of them.
No.  Input file (box.in ) 
Output file (box.out ) 

1 


2 


Author:  Elena Kryuchkova (original idea), Roman Elizarov (text)  Time limit:  2 sec  
Input file:  chandelier.in  Memory limit:  64 Mb  
Output file:  chandelier.out 
LampsOMatic company assembles very large chandeliers. A chandelier consists of multiple levels. On the first level crystal pendants are attached to the rings. Assembled rings and new pendants are attached to the rings of the next level, and so on. At the end there is a single large ring — the complete chandelier with multiple smaller rings and pendants hanging from it.
A specialpurpose robot assembles chandeliers. It has a supply of crystal pendants and empty rings, and a stack to store elements of a chandelier during assembly. Initially the stack is empty. Robot executes a list of commands to assemble a chandelier.
On command 'a' robot takes a new crystal pendant and places it on the top of the stack. On command '1' to '9' robot takes the corresponding number of items from the top of the stack and consecutively attaches them to the new ring. The newly assembled ring is then placed on the top of the stack. At the end of the program there is a single item on the stack — the complete chandelier.
Unfortunately, for some programs it turns out that the stack during their execution needs to store too many items at some moments. Your task is to optimize the given program, so that the overall design of the respective chandelier remains the same, but the maximal number of items on the stack during the execution is minimal. A pendant or any complex multilevel assembled ring count as a single item of the stack.
The design of a chandelier is considered to be the same if each ring contains the same items in the same order. Since rings are circular it does not matter what item is on the top of the stack when the robot receives a command to assemble a new ring, but the relative order of the items on the stack is important. For example, if the robot receives command '4' when items < i_{1}, i_{2}, i_{3}, i_{4} > are on the top of the stack in this order (i_{1} being the topmost), then the same ring is also assembled if these items are arranged on the stack in the following ways: < i_{2}, i_{3}, i_{4}, i_{1} >, or < i_{3}, i_{4}, i_{1}, i_{2} >, or < i_{4}, i_{1}, i_{2}, i_{3} >.
No.  Input file (chandelier.in ) 
Output file (chandelier.out ) 

1 


Author:  Andrew Stankevich (text and idea), Roman Elizarov (idea)  Time limit:  2 sec  
Input file:  document.in  Memory limit:  64 Mb  
Output file:  document.out 
Andy is fond of old computers. He loves everything about them and he uses emulators of old operating systems on his modern computer. Andy also likes writing programs for them. Recently he has decided to write a text editor for his favorite textmode operating system.
The most difficult task he has got stuck with is document indexing. An index of the document is the lexicographically ordered list of all words occurring in the document with the numbers of pages they occur at. Andy feels that he is not able to write the component of the editor that performs indexing, so he asks you to help.
A document is a sequence of paragraphs. Each paragraph consists of one or more lines. Paragraphs are separated from each other with exactly one blank line.
First, the document is paginated — divided into pages. Each page consists of up to n lines. Lines are placed on the page one after another, until n lines are placed. The following correction rules are then applied:
1) If the last line on a page is the last line of the paragraph, then the following empty line is skipped, i.e. it is not placed on any page. Therefore, the page never starts with a blank line.
2) If the last line on a page is the first line of a paragraph that contains more than one line (so called orphan line), then it is moved to the next page.
3) If the last line on a page is the nexttolast line of a paragraph that contains more than three lines, then this line is moved to the next page (otherwise, the last line of the paragraph would be alone on the page — so called widow line).
4) If the last line on a page is the nexttolast line of a paragraph that contains exactly two or three lines, then the whole paragraph is moved to the next page (so we have neither orphan, nor widow lines).
After applying the correction rules the next page is formed, and so on until the whole document is paginated.
A word is a continuous sequence of letters of the English alphabet. Case is not important.
The index of the document contains each word from the document and the list of the pages it occurs at. The numbers of pages a word occurs at must be listed in the ascending order. Numbers must be separated by commas. If a word occurs on three or more consecutive pages, only the first and the last page numbers of this range must be listed, separated by a dash, for example '35,710,12,13,15'.
4 ≤ n ≤ 100
The size of the input file does not exceed 20000 bytes. The length of each line of the document does not exceed 200 characters.
No.  Input file (document.in ) 
Output file (document.out ) 

1 


Author:  Roman Elizarov (original idea, text)  Time limit:  2 sec  
Input file:  easy.in  Memory limit:  64 Mb  
Output file:  easy.out 
Frank is a professional stock trader for Advanced Commercial Markets Limited (ACM Ltd). He likes 'easy trading' — using a straightforward strategy to decide when to buy stock and when to sell it.
Frank has a database of historical stock prices for each day. He uses two integer numbers m and n as parameters of his trading strategy. Every day he computes two numbers: P(m) — an average stock price for the previous m days, and P(n) — an average stock price for the previous n days. P(m) > P(n) is an indicator of the upward trend (traders call it bullish trend), and P(m) < P(n) is an indicator of the downward trend (traders call it bearish trend). In practice the values for P(m) and P(n) are never equal.
When a trend reverses from bearish to bullish it is a signal for Frank to buy stock. When a trend reverses from bullish to bearish it is a signal to sell.
Frank has different values for m and n in mind and he wants to backtest them using historical prices. He takes a set of k historical prices p_{i} For each i (n ≤ i ≤ k) he computes P_{i}(m) and P_{i}(n) — an arithmetic average of p_{im+1} ... p_{i} and p_{in+1} ... p_{i} respectively.
Backtesting generates trading signals according to the following rules.
1) If P_{i}(m) > P_{i}(n) there is a bullish trend for day i and a 'BUY ON DAY i' signal is generated if i=n or there was a bearish trend on day i1.
2) If P_{i}(m) < P_{i}(n) there is a bearish tread for day i and a 'SELL ON DAY i' signal is generated if i=n or there was a bullish trend on day i1.
Your task is to write a program that backtests a specified strategy for Frank — you shall print a signal for the first tested day (day n) followed by the signals in increasing day numbers.
1 ≤ m < n ≤ 100.
n < k ≤ 10000.
0 < p_{i} < 100 for 1 ≤ i ≤ k.
No.  Input file (easy.in ) 
Output file (easy.out ) 

1 


Author:  Elena Andreeva (original idea), Roman Elizarov (text)  Time limit:  2 sec  
Input file:  find.in  Memory limit:  64 Mb  
Output file:  find.out 
Closed polyline (with possible selfintersections) partitions a plane into a number of regions. One of the regions is unbounded — it is an exterior of the polyline. All the bounded regions together with the polyline itself form an interior of the polyline (shaded in the picture below). The border of the interior (bold line in the picture) is a polyline as well. This polyline has the same interior as the original one. Your task is to find the border of the interior of the given polyline.
To guarantee the uniqueness (up to the starting point) of the polyline representing the border we require that the following conditions are satisfied for it:
 it has no selfintersections, although may have selftouchings;
 no adjacent vertices of the border coincide;
 no adjacent edges of the border are collinear;
 when traversing the border, its interior is always to the left of its edges.
No.  Input file (find.in ) 
Output file (find.out ) 

1 


Author:  Georgiy Korneev (original idea), Roman Elizarov (text)  Time limit:  2 sec  
Input file:  gunman.in  Memory limit:  64 Mb  
Output file:  gunman.out 
Consider a 3D scene with OXYZ coordinate system. Axis OX points to the right, axis OY points up, and axis OZ points away from you. There is a number of rectangular windows on the scene. The plane of each window is parallel to OXY, its sides are parallel to OX and OY. All windows are situated at different depths on the scene (different coordinates z > 0).
A gunman with a rifle moves along OX axis (y = 0 and z = 0). He can shoot a bullet in a straight line. His goal is to shoot a single bullet through all the windows. Just touching a window edge is enough.
Your task is to determine how to make such shot.
No.  Input file (gunman.in ) 
Output file (gunman.out ) 

1 


2 


Author:  Andrew Stankevich (original idea, text, solution)  Time limit:  2 sec  
Input file:  heapsort.in  Memory limit:  64 Mb  
Output file:  heapsort.out 
A well known algorithm called heapsort is a deterministic sorting algorithm taking O(n log n) time and O(1) additional memory. Let us describe ascending sorting of an array of different integer numbers.
The algorithm consists of two phases. In the first phase, called heapification, the array of integers to be sorted is converted to a heap. An array a[1…n] of integers is called a heap if for all 1 ≤ i ≤ n the following heap conditions are satisfied:
 if 2i ≤ n then a[i] > a[2i];
 if 2i + 1 ≤ n then a[i] > a[2i + 1].
We can interpret an array as a binary tree, considering children of element a[i] to be a[2i] and a[2i + 1]. In this case the parent of a[i] is a[i div 2], where i div 2 = floor(i / 2). In terms of trees the property of being a heap means that for each node its value is greater than the values of its children.
In the second phase the heap is turned into a sorted array. Because of the heap condition the greatest element in the heapified array is a[1]. Let us exchange it with a[n], now the greatest element of the array is at its correct position in the sorted array. This is called extractmax.
Now let us consider the part of the array a[1 ... n1]. It may be not a heap because the heap condition may fail for i=1. If it is so (that is, either a[2] or a[3], or both are greater than a[1]) let us exchange the greatest child of a[1] with it, restoring the heap condition for i=1. Now it is possible that the heap condition fails for the position that now contains the former value of a[1]. Apply the same procedure to it, exchanging it with its greatest child. Proceeding so we convert the whole array a[1 ... n1] to a heap. This procedure is called sifting down. After converting the part a[1 ... n1] to a heap by sifting, we apply extractmax again, putting second greatest element of the array to a[n1], and so on.
For example, let us see how the heap a=(5, 4, 2, 1, 3) is converted to a sorted array. Let us make the first extractmax. After that the array turns to (3, 4, 2, 1, 5). Heap condition fails for a[1] = 3 because its child a[2] = 4 is greater than it. Let us sift it down, exchanging a[1] and a[2]. Now the array is (4, 3, 2, 1, 5). The heap condition is satisfied for all elements, so sifting is over. Let us make extractmax again. Now the array turns to (1, 3, 2, 4, 5). Again the heap condition fails for a[1]; exchanging it with its greatest child we get the array (3, 1, 2, 4, 5) which is the correct heap. So we make extractmax and get (2, 1, 3, 4, 5). This time the heap condition is satisfied for all elements, so we make extractmax, getting (1, 2, 3, 4, 5). The leading part of the array is a heap, and the last extractmax finally gives (1, 2, 3, 4, 5).
It is known that heapification can be done in O(n) time. Therefore, the most time consuming operation in heapsort algorithm is sifting, which takes O(n * log (n)) time.
In this problem you have to find a heapified array containing different numbers from 1 to n, such that when converting it to a sorted array, the total number of exchanges in all sifting operations is maximal possible. In the example above the number of exchanges is 1+1+0+0+0 = 2, which is not the maximum. (5, 4, 3, 2, 1) gives the maximal number of 4 exchanges for n=5.
No.  Input file (heapsort.in ) 
Output file (heapsort.out ) 

1 


Author:  Georgiy Korneev (original idea), Andrew Stankevich (text)  Time limit:  2 sec  
Input file:  irrelevant.in  Memory limit:  64 Mb  
Output file:  irrelevant.out 
Young cryptoanalyst Georgie is investigating different schemes of generating random integer numbers ranging from 0 to m  1. He thinks that standard random number generators are not good enough, so he has invented his own scheme that is intended to bring more randomness into the generated numbers.
First, Georgie chooses n and generates n random integer numbers ranging from 0 to m  1. Let the numbers generated be a_{1}, a_{2}, ..., a_{n}. After that Georgie calculates the sums of all pairs of adjacent numbers, and replaces the initial array with the array of sums, thus getting n1 numbers:a_{1} + a_{2}, a_{2} + a_{3}, ..., a_{n  1} + a_{n}. Then he applies the same procedure to the new array, getting n  2 numbers. The procedure is repeated until only one number is left. This number is then taken modulo m. That gives the result of the generating procedure.
Georgie has proudly presented this scheme to his computer science teacher, but was pointed out that the scheme has many drawbacks. One important drawback is the fact that the result of the procedure sometimes does not even depend on some of the initially generated numbers. For example, if n = 3 and m = 2, then the result does not depend on a_{2}.
Now Georgie wants to investigate this phenomenon. He calls the ith element of the initial array irrelevant if the result of the generating procedure does not depend on a_{i}. He considers various n and m and wonders which elements are irrelevant for these parameters. Help him to find it out.
No.  Input file (irrelevant.in ) 
Output file (irrelevant.out ) 

1 


Author:  Andrew Lopatin (original idea), Roman Elizarov (text)  Time limit:  2 sec  
Input file:  joke.in  Memory limit:  64 Mb  
Output file:  joke.out 
There is a famous jokeriddle for children:
Three turtles are crawling along a road. One turtle says: "There are two turtles ahead of me." The other turtle says: "There are two turtles behind me." The third turtle says: "There are two turtles ahead of me and two turtles behind me." How could this have happened?
The answer is — the third turtle is lying!
Now in this problem you have n turtles crawling along a road. Some of them are crawling in a group, so that they do not see members of their group neither ahead nor behind them. Each turtle makes a statement of the form: "There are a_{i} turtles crawling ahead of me and b_{i} turtles crawling behind me." Your task is to find the minimal number of turtles that must be lying.
Let us formalize this task. Turtle i has x_{i} coordinate. Some turtles may have the same coordinate. Turtle i tells the truth if and only if a_{i} is the number of turtles such that x_{j} > x_{i} and b_{i} is the number of turtles such that x_{j} < x_{i}. Otherwise, turtle i is lying.
No.  Input file (joke.in ) 
Output file (joke.out ) 

1 


2 


Author:  Georgiy Korneev (original idea), Roman Elizarov (text)  Time limit:  2 sec  
Input file:  kingdom.in  Memory limit:  64 Mb  
Output file:  kingdom.out 
Kingdom of Magic has a network of bidirectional magic portals between cities since ancient times. Each portal magically connects a pair of cities and allows fast magical communication and travel between them. Cities that are connected by the magic portal are called neighboring.
Prince Albert and Princess Betty are living in the neighboring cities. Since their childhood Albert and Betty were always in touch with each other using magic communication Orbs, which work via a magic portal between the cities.
Albert and Betty are in love with each other. Their love is so great that they cannot live a minute without each other. They always carry the Orbs with them, so that they can talk to each other at any time. There is something strange about their love — they have never seen each other and they even fear to be in the same city at the same time. People say that the magic of the Orbs have affected them.
Traveling through the Kingdom is a complicated affair for Albert and Betty. They have to travel through magic portals, which is somewhat expensive even for royal families. They can simultaneously use a pair of the portals to move to a different pair of cities, or just one of them can use a portal, while the other one stays where he or she is. At any moment of their travel they have to be in a neighboring cities. They cannot simultaneously move through the same portal.
Write a program that helps Albert and Betty travel from one pair of the cities to another pair. It has to find the cheapest travel plan — with the minimal number of times they have to move though the magic portals. When they move through the portals simultaneously it counts as two moves.
The first line of the input file contains integer numbers n, m, a_{1}, b_{1}, a_{2}, b_{2}. Here n is a number of cities in the Kingdom (cities are numbered from 1 to n); m is a number of magic portals; a_{1}, b_{1} (1 ≤ a_{1}, b_{1} ≤ n, a_{1} <> b_{1}) are the neighboring cities where Albert and Betty correspondingly start their travel from; a_{2}, b_{2} (1 ≤ a_{2}, b_{2} ≤ n, a_{2} <> b_{2}) are the neighboring cities where Albert and Betty correspondingly want to get to (a_{1} <> a_{2} or b_{1} <> b_{2}).
Following m lines describe the portals. Each line contains two numbers p_{i1} and p_{i2} (1 ≤ p_{i1}, p_{i2} ≤ n, p_{i1} <> p_{i2}) — cities that are connected by the portal. There is at most one portal connecting two cities.
On the first line of the output file write two numbers c and k. Here c is the minimal number of moves in the travel plan; k is the number of neighboring city pairs that Albert and Betty visit during their travel including a_{1}, b_{1} at the start and a_{2}, b_{2} at the end.
Then write k lines with two integer numbers a'_{i} and b'_{i} on each line — consecutive different pairs of neighboring cities that Albert and Betty visit during their travel. If there are multiple travel plans with the same number of moves, then write any of them. It is guaranteed that solution exists.
No.  Input file (kingdom.in ) 
Output file (kingdom.out ) 

1 


Author:  Roman Elizarov (original idea, text)  Time limit:  2 sec  
Input file:  lattice.in  Memory limit:  64 Mb  
Output file:  lattice.out 
Lattice animal is a set of connected sites on a lattice. Lattice animals on a square lattice are especially popular subject of study and are also known as polyominoes. Polyomino is usually represented as a set of sidewise connected squares. Polyomino with n squares is called npolyomino.
In this problem you are to find a number of distinct free npolyominoes that fit into rectangle w × h. Free polyominoes can be rotated and flipped over, so that their rotations and mirror images are considered to be the same.
For example, there are 5 different pentominoes (5polyominoes) that fit into 2 × 4 rectangle and 3 different octominoes (8polyominoes) that fit into 3 × 3 rectangle.
No.  Input file (lattice.in ) 
Output file (lattice.out ) 

1 


2 


3 


4 


5 

