Problem A. Advanced drag racing ≡

Statement

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₀ and L₁ 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² 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 format

Input file contains real numbers L₀ L₁ 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 format

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.

Constraints

Sample tests

50 100 1 1 10

2.22863 1.38195

50 100 0.1 1 10

3.015 0

Problem B. Before first zero ≡

Statement

This problem has absolutely no relation to cars and car races.

Consider a sequence B_i defined as follows: First two elements (B₁ and B₂) 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₁ = 11, B₂ = 1111, B₃ = 1100, B₄ = 11, B₅ = 1089, B₆ = 1078, …, B₁₅₁ = 11, B₁₅₂ = 11, B₁₅₃ = 0, ….

Input file format

Input file contains two natural numbers N and M.

Output file format

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.

Constraints

1 ≤ N, M ≤ 10⁶

Sample tests

1 1

1

2 4

11

Problem C. Cup and Championship ≡

Statement

The city of Kislodriftinsk holds two prestigious drifting contests with different rules.

The Kislodriftinsk Drifting Championship consists of head-to-head 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 play-off 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 format

Input file contains integers N T. Following N lines contain N integers each — a matrix of head-to-head matches results. A number in row i and column j is equal 1 if i-th pilot wins against j-th and 0 otherwise. Diagonal contains zeroes. Kesha Tsuchiyev is a pilot number T, numbers start from zero.

Output file format

Output file must contain N integers s_0,i which is a permutation of pilot numbers 0… N − 1 determining a schedule of play-off 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 play-off 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.

Constraints

2 ≤ N ≤ 64, N is a power of 2, 0 ≤ T < N

Sample tests

4 2
0 1 0 0
0 0 0 0
1 1 0 1
1 1 0 0

1 2 0 3

4 2
0 1 0 0
0 0 1 0
1 0 0 1
1 1 0 0

2 3 0 1

Problem D. Diversify start positions ≡

Statement

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₁, p₂, …, 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:

• start position distributions are different for each race;
• it's impossible to increase the number of races x without breaking the first rule;
• each car changes its position after the permutation.

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 format

Input file contains two integers n and x.

Output file format

Output file must contain a feasible permutation. If a feasible permutation doesn't exist, output a single integer  − 1.

Constraints

2 ≤ n ≤ 10³

2 ≤ x ≤ 10⁶

Sample tests

6 3

4 3 6 5 1 2

Problem E. Easy money ≡

Statement

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 format

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 format

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.

Constraints

2 ≤ N, M ≤ 10000;

1 ≤ A_i, B_i ≤ 10000;

1 ≤ p_i, q_i ≤ N, p_i ≠ q_i;

Sample tests

2 2
100 10 1 2
100 10 2 1

90

3 3
200 100 1 2
40 50 2 1
100 1 1 3

0

Problem F. Fortunate ticket ≡

Statement

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 non-overlapping 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 22-2 rather than 2-22.

Input file format

First line of input file contains a single natural number R.

Second line of input file contains ticket number.

Output file format

Output file should contain one line — ticket number with highlighted optimal pattern.

Constraints

1 ≤ R ≤ 9

Number length is between 1 and 5 × 10⁵ digits.

Sample tests

2
936472

9-36-472

2
198065103206510980651098

198-0-651-0-32-0-651-0-98-0-651-0-98

3
198065103206510980651098

198-065-1032-065-1098-065-1098

Problem G. Guaranteed win ≡

Statement

A game company produced new high-profile car racing game for set-top 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 round-robin 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 format

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 format

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.

Constraints

2 ≤ N ≤ 1000, 0 ≤ M ≤ N(N − 1) / 2, 1 ≤ W_i, L_i ≤ N, W_i ≠ L_i

Sample tests

3 2
2 1
2 3

-1

3 2
1 2
2 3

1

4 3
2 3
3 4
4 2

3

Problem H. Hype spreading ≡

Statement

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 format

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 format

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.

Constraints

2 ≤ W, H ≤ 2000

Sample tests

2 2
#.
.#

2 1

5 5
..#.#
..###
#..##
#.##.
#....

2 4

6 4
######
.....#
..##.#
...#.#

3 2

Problem I. Ignition ≡

Statement

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 air-fuel 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:

1. a timing map consisting of N pairs (r_i; d_i), where r_i is an engine speed, d_i — corresponding advance value;
2. a list M of engine speeds t_i.

Input file format

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 format

Output file must contain M integers a_i — calculated advance values.

Constraints

2 ≤ N ≤ 100; 1 ≤ r₁ < …  < r_N ≤ 10000; 1 ≤ d_i ≤ 90;

1 ≤ M ≤ 100; r₁ ≤ t_i ≤ r_N;

Sample tests

2
1000 10  2000 20
1
1200

12

3
500 50 600 60 900 70
4
600 574 579 850

60 57 57 68

Problem J. Judging tires ≡

Statement

According to ISO stadnard Metric tire code, tire dimensions are described by a string of letters and numbers in the following format:

• 3-digit nonzero number: The nominal section width of the tire in millimeters, the widest point from both outer edges.
• /: Slash character for separation.
• 2- or 3-digit nonzero number: The aspect ratio of the sidewall height to the nominal section width of the tire, as a percentage.
• Letter R indicating radial construction of the fabric carcass of the tire.
• 2-digit nonzero number: Diameter in inches of the wheel disk that the tires are designed to fit.

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.

Input file format

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 format

Output file must contain a single string — APPROVED if Vasya's car is approved to the race or DISAPPROVED otherwise.

Constraints

0 ≤ K ≤ 100

Sample tests

2
195/65R15
205/55R15

DISAPPROVED

1
195/65R15
185/070R15

APPROVED