Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
During the course on compiler construction, students were assigned a task: implement a parser for expressions with array access according to Pascal programming language syntax. Student Vasya has slacked on this task, and implemented only a very small language subset, consisting of a single integer constant 0 and accesses to a single twodimensional array a. In other words, his "language" has the following grammar:
expr ::= 0  a[expr,expr]
After seeing this sad result, a teacher assigned an additional task to Vasya: suppose an array a is defined as a: array [0..N  1, 0..N  1] of 0..N. Given N and the values of array elements, generate the shortest possible expression in Vasya's language which will have the value of N.
Input file contains an integer N, followed by N^{2} integers — values a_{ij}, in rowbyrow order.
Output file must contain a single string — an expression in Vasya's language. The expression must exactly correspond to the grammar above. If there is no expression with the value of N, output string IMPOSSIBLE. If there are several shortest expressions, output any of them.
1 ≤ N ≤ 22, 0 ≤ a_{ij} ≤ N
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  G. Grenkin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Mathematicians from the Institute of New Year Research developed a mathematical model of the New Year firtree. In this model the fir is supposed to be a sphere with a radius of 1 meter. Modeling of a fir garland is, however, more complicated.
A fir garland is modeled with a curve located on the sphere. The curve begins at the topmost point of the sphere, ends at the bottommost point of the sphere, and makes exactly N turns around it.
Consider spherical coordinates φ (longitude) and θ (latitude). The initial value of longitude equals 0, longitude makes exactly N turns and the final value equals 0 again. The initial value of latitude equals 90°, the final value equals −90°. The increment of latitude is proportional to the increment of longitude.
Your program must, for a given value of N, calculate the length of the curve which models a fir garland.
Input file contains a single integer N.
Output file must contain a single real number — the length of the curve (in meters) with at least 3 correct digits after decimal point.
1 ≤ N ≤ 100
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Many compression algorithms are based on finding frequently repeating substrings in the input data. Since it is often impractical to search the whole input for repetitions, only a limited compression window is considered on each step.
While researching a new compression algorithm, young computer scientist Vasya encountered the following problem.
Given input string of N bits, let the compression window be any substring of M bits. Inside each compression window, find the maximum number of occurrences of any substring of length L (L ≤ M).
In the sample input 1 below, compression window length is equal to string length, so there is only a single window. Most frequent substring of length 2 is 01, which occurs 5 times.
First line of input file contains integers L M. Second line input file contains a string of length N, each character either 0 or 1.
Output file must contain N − M + 1 integers — maximum substring frequencies for each compression window.
1 ≤ M ≤ N ≤ 2 × 10^{5}, 1 ≤ L ≤ 100
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Klenin, I. Tuphanov  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Young builder Vasya was requested to hang wallpaper on the wall. The wall is a rectangle of W meters wide and H meters high, with a rectangular door of w meters wide and h meters high, located at the left side of the wall. Wallpaper is packaged into rolls. Each roll is 1 meter wide and D meters long, which Vasya may have to cut into shorter stripes of equal width.
Vasya has a high standard for work quality, so he must:
Your program must calculate the minimum number of wallpaper rolls required to complete the task.
In the example below it is optimal to cut rolls into stripes of lengths 3+2+1. If different rolls could be cut into different stripe sequences, then a better solution would be to cut one roll into lengths 3+3 and another one into 2+2+2.
The input file contains integers W H w h D. It is guaranteed that the answer exists for given input.
Output must contain a single integer — the minimum number of rolls.
1 ≤ W, H, w, h ≤ 10^{9}; 1 ≤ D ≤ 2 × 10^{9};
h ≤ H; w ≤ W;
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Let's call an integer number elite if it is divisible by every digit of its decimal representation.
Given an integer x, your program must find the smallest elite number greater than or equal to x.
Input file contains the integer x.
Output file must contain a single integer — the smallest elite number.
1 ≤ x ≤ 10^{10}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Once upon a time there was a large country with many provinces and a great government. The government noticed that citizens of the furthest province are unhappy, and decided to do something for them.
After a serious sociological research, the government decided that the main problem of the province is the fact that every citizen has to buy his own watch to measure time. Thus the government decided to build a large tower with a giant analog clock on it, so that citizens could look at the common clock and save money on watches.
Many efforts and resources were spent, and finally the clock has been built and officially started in a grand ceremony. As the ceremony finished, people noticed that the clock has a small problem — it measures time incorrectly.
Since all the money allocated to this project was already spent, it was impossible to fix the clock. Instead, the government introduced a new position of Senior Clock Manager, whose responsibility was to adjust the clock by manually moving its hands.
It was decreed that:
Since the clock hands are very heavy, the Clock Manager's job is not an easy one. To help him, find the period of adjustment minimizing the total distance by which he must move the clock hands throughout the day. The clock has two hands — for minutes and hours. Every minute, the minute hand jumps clockwise by t degrees, and the hour hand jumps by t / 12 degrees. (A correct clock should have t = 6).
An adjustment is made immediately after the jump, and the effort is equal to the sum of angles between the current and the correct positions of both minute and hour hands.
In the first sample, the clock moves twice as fast as it should, so every minute the error is increased by one minute. This requires an adjustment every two minutes.
In the second sample, the clock moves three times as fast as it should, but the acceptable error is much higher. It turns out that every 30 minutes the position of the minute hand coincides with the correct one, so if we choose the interval of 30 minutes, only the hour hand must be moved.
Input file contains floating point number t followed by integer m.
Output file must contain the minimum total effort s in degrees, with an absolute error less than 10^{−2}, and the corresponding adjustment period p, 1 ≤ p ≤ 24 * 60. If there are several answers with the same total effort, output the one with the maximum p.
0 ≤ t ≤ 10^{4}, 1 ≤ m ≤ 10^{4}, t has no more than 3 digits after decimal point.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Popular online game "Attack Of The Moderns 3" is played by two teams of 5 players each. During the match, players run around the map and try to kill members of opposing team by attacking them with various weapons and magic spells. Killed players respawn after a certain period of time.
Players of the first team are numbered from 1 to 5, players of the second team are numbered from 6 to 10. All attacks are recorded by the game for statistics gathering. Each attack is described by values t, a, v, k, where t is a time in seconds since the game start, a — the number of the attacking player, v — the number of the player being attacked, k = 1 if this attack killed the victim and 0 otherwise.
Gank is an event when one or more players attack and kill a single opponent while his teammates are elsewhere and unable to help. Specifically: let G be a set of players who attacked the victim during the last T seconds of the game before the kill. A kill is counted as a gank, if in that period of time:
Your program must, given the value of T and a sequence of N attack descriptions, count the number of ganks each player has participated in.
Input file contains integers N T followed by N quartets of integers t_{i} a_{i} v_{i} k.
Output file must contain 10 integers — the numbers of ganks for each player.
1 ≤ N ≤ 10000, 1 ≤ t_{i} ≤ t_{i+1} ≤ 10^{5}, 1 ≤ T ≤ 10^{5}. Either 1 ≤ a_{i} ≤ 5 < v_{i} ≤ 10 or 1 ≤ v_{i} ≤ 5 < a_{i} ≤ 10. Time between sequential kills of the same victim is greater than T.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


Author:  A. Klenin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
A game development company has started prototyping a new game, which is played on a field based on a hexagonal grid. The first task is to display a part of the grid in the player's viewport. To speed up the prototyping phase, it was decided to use textbased representation instead of graphics.
The hexagonal grid is composed of nearly perfect hexagons with the side of N characters. In every hexagon, the top and the bottom sides are composed of N "_" characters (ASCII 95), the righttop and the leftbottom sides are composed of N "\" characters (ASCII 92), the lefttop and the rightbottom sides are composed of N "/" characters (ASCII 47). All other characters of the field are "." (ASCII 46).
The grid is assumed to be infinite, with the position (0; 0) corresponding to the leftmost character of the top side of a hexagon. The player's viewport is a rectangle displaying some part of the field.
You program must, given the coordinates x, y of the top left corner of the viewport and w, h — the viewport width and height, output the content of the viewport.
Input file contains integers N x y w h.
Output file must contain h lines of w characters each — the viewport content.
1 ≤ N ≤ 100, 0 ≤ x, y ≤ 10^{9}, 1 ≤ w, h ≤ 100
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


Author:  A. Klenin  Time limit:  2 sec  
Input file:  input.txt  Memory limit:  64 Mb  
Output file:  output.txt 
A certain large organization has an office building with an extensive local area network. Recently said organization has expanded to a new office building, where a new local area network was installed. Unfortunately, the new building is located on a remote island, and the infrastructure there is plagued by all kinds of problems: disconnects, power outages, network packet drops etc.
Engineers of the organization's IT department installed two monitoring servers, one for each building. Each server writes a log, where it stores the type of failure for every problem it detects.
In theory, both logs should be identical. However, it turned out that even the monitoring subsystem itself has issues: some problems are detected only by one server, servers sometimes erroneously report nonexisting problems, and even timestamps are unreliable since server clocks are not synchronized.
Engineers decided to encode each log as a string of L lowercase Latin letters, one letter for each problem. To filter out monitoring errors, they decided to define the real problem history as the longest subsequence of problems recorded in both logs in the same order.
While trying to improve the network, engineers frequently need to compare not only the whole logs, but selected segments of them.
Given two strings a and b representing the two logs, and a sequence of N requests if the form of a_{1}, a_{2}, b_{1}, b_{2}, your program must for each request output the length of the real problem history produced by comparing the segment from position a_{1} to position a_{2} in the first log with the segment from position b_{1} to position b_{2} in the second log.
The first two lines of input file contain strings a and b of the same length L. The third line contains integer N. Following N lines contain 4 integers each — values a_{i,1} a_{i,2} b_{i,1} b_{i,2}.
Output file must contain N integers — the real problem history lengths.
1 ≤ L ≤ 100, 1 ≤ N ≤ 10^{6}, 1 ≤ a_{i,1} ≤ a_{i,2} ≤ L, 1 ≤ b_{i,1} ≤ b_{i,2} ≤ L.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  G. Grenkin  Time limit:  1 sec  
Input file:  input.txt  Memory limit:  256 Mb  
Output file:  output.txt 
Once upon a time Marfa Gennadievna bought a pack of 54 playing cards containing two jokers. She put cards face down and chose N cards of them randomly (with uniform probability distribution).
Your program must calculate the probability that there will be at least one joker among chosen cards.
Input file contains a single integer N.
Output file must contain a single real number — required probability with at least 6 correct digits after decimal point.
2 ≤ N ≤ 54
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 

