Author:  I. Ludov  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
There is a long discussion about drag racing as a motorsport. Some critics argue that it is too technically conditioned and hence everything there depends on a car preparation and tuning, not on driver skills. Enthusiasts may note that these things are said in such a way, as if they were something bad.
Organizers of one drag racing contest try to make their event interesting to both sides by changing some rules. The main principle is essentially the same: two participants start at the same time along parallel lines and try to pass a given range as fast as their cars allow. But still there is one very notable change. Whereas the standard drag racing track is a 400 meters straight line, this contest is conducted on a track with a single turn, connecting two straight segments of lengths L_{0} and L_{1} meters with an angle A radians between them.
Since the driver must turn, and he cannot do this instantly, he must leave the first straight segment before it ends, turn and arrive into some point of second segment with velocity parallel to this segment. During this process he should not deviate for more than D meters from segments, or else he risks to hit the border of the track. Also, rules of the contest state that there should be only one such turn.
Your car is equipped with an engine so powerful, that available acceleration is limited only by driving wheels traction. This maximum acceleration is G meters / second^{2} and it can push car along a straight line, decelerate car in straight line and turn car's velocity direction, leaving its amplitude unchanged, acting as a centripetal acceleration.
To win the contest you must determine an optimal strategy of passing a track. It is rather obvious, that after the turn you should accelerate as hard as possible. But the question is how to approach turn and when to start turning. Such approach will consist of maximum acceleration which may or may not be followed by maximum braking. So your task is to write a program that will find values of time durations of accelerating and braking which make your car do its best on a given track, i.e. finishes in time that is at most 0.01 seconds more than minimum possible.
Input file contains real numbers L_{0} L_{1} A D G, length of a straight segment before turn point, length of a straight segment after turn point, turn angle in radians, maximum allowed side deviation and maximum car acceleration respectively. All lengths are given in meters.
Output file should contain two real numbers T_{a} T_{b}, duration of acceleration and braking respectively. If braking is not needed, T_{b} should be equal to 0. All durations must be specified in seconds.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Zhuplev  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
This problem has absolutely no relation to cars and car races.
Consider a sequence B_{i} defined as follows: First two elements (B_{1} and B_{2}) are natural numbers whose decimal representations consist of N and M "1" digits correspondingly. Following terms are computed according to the formula: B_{i} = B_{i−2} − B_{i−1}.
Your program should find such an element B_{k} that B_{k+1} = 0 and B_{j} ≠ 0 for all 1 ≤ j ≤ k.
In the second sample B_{1} = 11, B_{2} = 1111, B_{3} = 1100, B_{4} = 11, B_{5} = 1089, B_{6} = 1078, …, B_{151} = 11, B_{152} = 11, B_{153} = 0, ….
Input file contains two natural numbers N and M.
Output file should contain a single integer — B_{k} or 0 if there's no zero term in B series. Note that the value of B_{k} may be very large.
1 ≤ N, M ≤ 10^{6}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  I. Ludov  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
The city of Kislodriftinsk holds two prestigious drifting contests with different rules.
The Kislodriftinsk Drifting Championship consists of headtohead matches between all pairs of pilots. Judging rules exclude draws, so after every match exactly one participant receives one score point. The champion of Kislodriftinsk is determined as the pilot with maximum summary score (i. e. beating maximum number of other participants). Note that there may be several champions with equal scores.
The Kislodriftinsk Drifting Cup is conducted by olympic playoff system (aka single elimination). All participants are divided into pairs and winners of every pair are determined. Winners then make new pairs and the process is repeated until there is only one participant left, who becomes a cup winner.
Rising star of Kislodriftinsk motorsports, Kesha Tsuchiyev, has already became one of Championship winners this year and now wants to also win in the forthcoming Cup. His task is simplified by the fact that both contests have same set of participants and same judge teams. This implies that the result of every match in the Cup will be the same as in the Championship with the same pair of participants. Being one of Championship winners, Kesha will win a significant proportion of possible Cup matches.
However, Kesha suspects that in the case of unfortunate pair composition, he may not even advance to second stage, having lost the very first match. Your program must help him calculate any Cup schedule which leads him to victory, or determine that it is impossible.
Input file contains integers N T. Following N lines contain N integers each — a matrix of headtohead matches results. A number in row i and column j is equal 1 if ith pilot wins against jth and 0 otherwise. Diagonal contains zeroes. Kesha Tsuchiyev is a pilot number T, numbers start from zero.
Output file must contain N integers s_{0,i} which is a permutation of pilot numbers 0… N − 1 determining a schedule of playoff championship as follows: In the first round N / 2 matches are conducted between pairs (s_{0,0} vs s_{0,1}), (s_{0,2} vs s_{0,3}), etc. Winners of these matches form a sequence s_{1,i}. Then the process is repeated, i.e. N / 4 matches are conducted between pairs (s_{1,0} vs s_{1,1}), (s_{1,2} vs s_{1,3}) etc. The winner of playoff cup is the only number left in the sequence s_{k,i} for some k, and this number must be equal to T. If there is no solution, output file must contain a single integer −1.
2 ≤ N ≤ 64, N is a power of 2, 0 ≤ T < N
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  I. Tuphanov  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
New Vasuki Challenge (NVC) is a race developed to make New Vasuki a new racing capital of the world. An outstanding feature of NVC is the distribution of start positions.
Let n be the number of cars taking place in NVC during the whole season. Each car has its id — integer number in range from 1 to n. A season consists of x races. Before a race each car takes a start position. There are n start positions, numbered from 1 to n.
In the beginning of a new season NVC director declares a permutation P = (p_{1}, p_{2}, …, p_{n}). Before the first race car number i takes start position number i for each i from 1 to n. Before each next race start positions are permuted according to P: car which was on start position p_{i} in the last race now goes to start position i.
Say, n = 6, x = 3, P = (4, 3, 6, 5, 1, 2). So, there will be three races and cars will stand in positions (1, 2, 3, 4, 5, 6) before the first race, (4, 3, 6, 5, 1, 2) before the second race, and (5, 6, 2, 1, 4, 3) before the third race.
A permutation P of size n is called feasible for given x iff:
For the example given above, (4, 3, 6, 5, 1, 2) is feasible because all three start position distributions are different, and if there were a forth race the distribution would be (1, 2, 3, 4, 5, 6) which already met in the first race.
Your task is to find a feasible permutation P for given n and x. If there are multiple solutions, output any of them.
Input file contains two integers n and x.
Output file must contain a feasible permutation. If a feasible permutation doesn't exist, output a single integer −1.
2 ≤ n ≤ 10^{3}
2 ≤ x ≤ 10^{6}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Young programmer Vasya was not at all interested in car races, but many of his friends were. One day, friends persuaded Vasya to come with them to a sports bar to drink beer and watch some very important race involving N cars — they told Vasya the name of the race, but he immediately forgot it.
At first Vasya was not keen to go, but the perspective of a good beer won him over.
After an hour at the bar, Vasya understood that that the endless images of the cars driving around and around were just as boring with beer as without it. His friends, however, got quite excited and started to place bets on race results. Due to the amount of beer consumed, the bets were wild and some of them did not reflect actual chances at all. In total, M bets were suggested.
Since Vasya was unable to have fun, he decided at least to make some profit. All bets are of the form "I bet A roubles versus B roubles that car p will come ahead of car q". That means betting person agrees to pay A roubles if he was wrong (i.e. q will come ahead of car p), and requires the other side to pay him B roubles if he was right.
By betting on the same cars with different friends, Vasya would in some cases guarantee himself a net win, even if he loses some of the bets. So as not to alienate too many of his friends, Vasya decided to accept only two bets.
Find two bets for Vasya which will guarantee him the largest profit in the worst case.
Input file contains integers N M followed by M bet descriptions.
Each bet description contains integers A_{i} B_{i} p_{i} q_{i}.
Output file must contain a single integer — the maximum amount of guaranteed profit. If there is no way to select two bets to be always profitable, output must contain 0.
2 ≤ N, M ≤ 10000;
1 ≤ A_{i}, B_{i} ≤ 10000;
1 ≤ p_{i}, q_{i} ≤ N, p_{i} ≠ q_{i};
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Zhuplev  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
There are many special competitions and entertainments for fans during a typical racing weekend. In order to improve attractiveness of circuit racing it was decided to introduce Fortunate ticket lottery as new kind of entertainment. Lottery participants may buy tickets, each ticket numbered with a unique sequence of digits. Additionally, a small integer constant R is randomly selected by lottery organizers and published before the start of the lottery.
Let F(R) denote the maximum number of nonoverlapping occurrences of any pattern with length R. The Ticket fortune value T is defined as max{F(i) × i  1 ≤ i ≤ R}. For instance, if R = 2 and ticket number is 1234125634123412 then F(2) = 4, (because 12 pattern occurs 4 times), F(1) = 4 , so T = 2 × 4 = 8. Let's call the pattern which gives the maximum value of F optimal pattern.
The lottery jackpot is divided between all tickets with the maximum fortune value. To claim the prize, participant must go to the lottery office and show his ticket. Unfortunately, ticket numbers are very long, so to prove that his ticked does indeed have the winning value, he must highlight the optimal pattern in the number.
You program must, given R and a ticket number, find the optimal pattern, and output the number, separating every occurrence of the optimal pattern from the surrounding digits by minus signs (ASCII 45).
If there is more than one optimal pattern, select lexicographically smallest one. If there is more than one way to separate optimal pattern, select one with the leftmost first occurrence, i.e. if number is 222 and optimal pattern is 22, then the answer is 222 rather than 222.
First line of input file contains a single natural number R.
Second line of input file contains ticket number.
Output file should contain one line — ticket number with highlighted optimal pattern.
1 ≤ R ≤ 9
Number length is between 1 and 5 × 10^{5} digits.
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
A game company produced new highprofile car racing game for settop boxes. To promote the game, company organized a tournament with a big cash prize.
A game is designed for two players racing each other — each game ends in one of players winning and the other one losing. The tournament is organized as a roundrobin between all N players (i. e. each player plays versus each other exactly once). After every game, winner gets one point towards his score. When all games are played, players are sorted by the descending score. If exactly one player gets the top score, he is declared an absolute champion and takes all the prize money. Otherwise, money is divided between all players with the same top score.
Young gamer Vasya participates in the tournament. In the middle of the tournament, when M games were already finished, he decided to find out: can he still become an absolute champion based on current results, and, if so, how many more games he must win to ensure absolute championship regardless of other players' results and, if he can afford to lose some of his unplayed games, regardless of which players he will win or lose against.
Input file contains integers N M followed by M pairs W_{i} L_{i}, meaning that player number W_{i} won against player number L_{i}. Vasya is player number 1.
Output file must contain a single integer — number of games to be won. If there is no chance left for Vasya to win whole prize, output −1.
2 ≤ N ≤ 1000, 0 ≤ M ≤ N(N − 1) / 2, 1 ≤ W_{i}, L_{i} ≤ N, W_{i} ≠ L_{i}
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
One famous car race takes place on a stadium with a racetrack. Spectators watching the race sit on a stand consisting of H rows with W seats each. During the race, some seats are occupied by spectators, and others are empty.
Marketing research demonstrated that if one spectator will loudly shout out a nicely rhymed slogan, spectators on seats located immediately to the left, right, above and below him will repeat it. Their neighbors, in turn, will catch up, and the slogan will spread throughout the stand.
An advertisement company invented a new slogan and wants it to spread among as many spectators as possible. To simulate "spontaneous" appearance of the slogan the company hired an agent who will move to one of the unoccupied seats and shout the slogan from there.
You program must determine the position of the agent which will result in maximum slogan penetration.
Input file contains integers W H in the first line, followed by H lines of W characters each.
Each character is either a '.' (ASCII 46) or '#' (ASCII 35), denoting free and occupied seat correspondingly.
There is at least one free seat.
Output file must contain two integers — x y, denoting seat number and row number for the agent to take. Rows are numbered starting from 1, top to bottom. Seats are numbered starting from 1, left to right. If there are several optimal solutions, output any of them.
2 ≤ W, H ≤ 2000
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


3 


Author:  A. Klenin  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
Ignition timing, in a spark ignition internal combustion engine, is the process of setting the angle relative to piston position that a spark will occur in the combustion chamber near the end of the compression stroke. The need for timing the spark is because fuel does not completely burn the instant the spark fires, the combustion gasses take a period of time to expand, and the angular or rotational speed of the engine can lengthen or shorten the time frame in which the burning and expansion should occur. The angle is described as a certain angle advanced before top dead center (BTDC), measured in degrees. Advancing the spark BTDC means that the spark is energized prior to the point where the combustion chamber reaches its minimum size, since the purpose of the power stroke in the engine is to force the combustion chamber to expand. The ignition timing will need to become increasingly advanced as the engine speed increases so that the airfuel mixture has the correct amount of time to fully burn.
Newer engines typically use computerized ignition systems. The computer has a timing map (lookup table) with spark advance values for various engine speeds, measured in rotations per minute (RPM). The computer will send a signal to the ignition coil at the indicated time in the timing map in order to fire the spark plug.
Since embedded computers used in ignition systems have limited memory, timing maps store advance values only for some engine speeds. Missing values are calculated by linear interpolation between two nearest stored values.
Your program is given:
Input file contains integer N followed by N pairs of integers r_{i} d_{i} and then by integer M and M integers t_{i}.
Output file must contain M integers a_{i} — calculated advance values.
2 ≤ N ≤ 100; 1 ≤ r_{1} < … < r_{N} ≤ 10000; 1 ≤ d_{i} ≤ 90;
1 ≤ M ≤ 100; r_{1} ≤ t_{i} ≤ r_{N};
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 


Author:  A. Zhuplev  
Input file:  input.txt  Time limit:  1 sec  
Output file:  output.txt  Memory limit:  256 Mb 
According to ISO stadnard Metric tire code, tire dimensions are described by a string of letters and numbers in the following format:
Rules of ACM (Any Car Modification) race specify a fixed tire dimensions for all participating cars. Young racer Vasya has not been able to find this type of tire. However, his car will still be approved for the race by judges only if radius of the wheel (wheel disk radius plus sidewall height) differs by at most K percent from that of the specified tire.
Note: 1 inch = 25.4 millimeters. Number a differs from b by at most c percent when 100 × a − b / b ≤ c.
First line of input file contains integer K.
Second and third lines contain Metric tire codes of specified tire and Vasya's tire respectively. Tire codes contain only digits, R and slash (ASCII 47) characters.
Output file must contain a single string — APPROVED if Vasya's car is approved to the race or DISAPPROVED otherwise.
0 ≤ K ≤ 100
No.  Input file (input.txt ) 
Output file (output.txt ) 

1 


2 

