Problem A. Avengers and Shawarma ≡

Statement

Avengers defeated alien invaders and decided to eat some shawarma.

Hulk ordered N shawarmas. M shawarmen immediately started to cook his order. Each shawarman can cook his first shawarma in T minutes. Each next shawarma requires S minutes more to cook than the previous one.

HULK SMASHes!!! awaiting his shawarmas.

You should help Avengers to find out the time when all shawarmas ordered by Hulk will be ready and green giant will calm down. Of course, Jarvis could solve this task, but Iron Man's suit is broken and only air conditioner is working right now.

Input format

First line contains two integers N and M — number of shawarmas ordered by Hulk, and number of shawarmen who are going to complete his order.

Second line contains two integers T and S — time needed to cook the first shawarma and the difference of cooking time between two shawarmas in the row.

Output format

Print one integer — time needed to complete Hulk's order.

Constraints

1 ≤ N, M, T ≤ 100

0 ≤ S ≤ 100

Sample tests

5 2
10 5

45

13 4
4 1

22

10 1
5 0

50

Problem B. Breaking digits ≡

Statement

Given an integer number A in decimal notation, your program must divide its digits between two integers B and C so that:

1. Every digit of A is encountered exactly once in either B or C.
2. The sum B + C is maximum possible.

Input file format

Input file contains a single integer A.

Output file format

Output file must contain two integers B and C. If there is more than one solution, output any of them.

Constraints

10 ≤ A ≤ 10⁹

Sample tests

11

1
1

439

94
3

1000

100
0

Problem C. Casino ≡

Statement

Aningaaq and his N brothers went to a casino. Today they are going to play following game. First they agree about their bet. They can't change this bet later. The game consists of several rounds. Each round, every player is going to bet or to pass. Winner is somehow determined and receives some prize (not money).

The oldest brother got the largest amount of money from parents. The second oldest brother got one dollar less than the oldest brother. The third oldest got two dollars less than the oldest brother. And so on. Aningaaq is the youngest brother. He got only M dollars.

Brothers are going to play while somebody has any money. And they are not supposed to give money to each other.

Aningaaq is worried that game can last very long and they are going to be late at home. Help him to find out the minimal possible number of rounds.

Input format

First line contains two integers N and M — number of Aningaaq's brothers and amount of money Aningaaq has.

Output format

Print one integer — minimal possible number of rounds.

Constraints

0 ≤ N ≤ 40

1 ≤ M ≤ 1000

Sample tests explanation

In the first test Aningaaq is alone, so he can bet all his money in the first (and single) round.

In the second test Aningaaq has 1 dollar. His brother has 2 dollars. Brothers can agree that the bet is one dollar. Then, in the first round Aningaaq will spend all his money and his brother will have one more dollar to play another round.

Sample tests

0 2

1

1 1

2

Problem D. Don't understarve ≡

Statement

Wilson got lost in a cave N × M cells. However, he has a map with the following notation keys:

'#' — an impassable cell (an abyss, a wall);

'.' — a free cell;

'X' — a wormhole — Wilson can teleport from this cell to any other wormhole with an equal probability;

'S' — a start cell;

'F' — a target cell — Wilson needs to get to this cell (an exit to the surface).

Movement through a wormhole is a risky process, because it takes a lot of Wilson's mind. When the level of his mind become too low, Wilson can be attacked by monsters.

Wilson's mind will be enough exactly for one teleportation. Therefore he wants to know the probability of him getting out of the cave using no more than one wormhole. Naturally, Wilson moves optimally, trying to maximize this probability.

Wilson can move in four directions: up, down, to the right and to the left.

Note that Wilson cannot step into a cell with a wormhole without using it.

Input format

The first line contains two integers N and M — dimensions of the cave.

It follows by N lines, M characters each — map of the cave.

It is guaranteed that there is one 'S' cell, at least one 'F' cell and at least two 'X' cells on the map.

Output format

Print the answer as an irreducible fraction by two integers (for example: if the answer is 50 / 74, you have to print "25 37").

Constraints

2 ≤ N, M ≤ 1000

Sample tests

2 2
XX
SF

1 1

4 4
#F.X
##X#
X#SX
###F

2 3

2 5
.F#S.
XXXXX

1 2

3 5
.F#S.
.#X#.
X..X#

0 1

Problem E. Edge of the knight ≡

Statement

In a chess, it is useful in some positions if two knight figures cover one another.

Sergey has already placed one knight on an empty chess board. Now he wants to know number of squares where he can place the second knight so that knights would cover each other.

Input file format

First line contains position of the first knight in a format of HW, where H — column (file), W — row (rank).

Output file format

Output a single integer — number of squares for the second knight.

Constraints

H ∈ (a, b, c, d, e, f, g, h)

1 ≤ W ≤ 8

Note on samples

Remember that a knight moves in a shape of letter L. Knight moves for 1 square in one direction (vertically or horizontally), and for 2 squares in another direction.

In the first sample the second knight can be placed on squares c 1, g 1, c 3, g 3, d 4 and f 4.

Sample tests

e2

6

f5

8

Problem F. Dreaming on a train ≡

Statement

Young programmer Vasya goes to work and from work on the train every day.

When returning from work, Vasya is very tired, so he can fall asleep in the train.

On the route from work to Vasya's home there are N stations. Each of them is announced on the radio at the moment when the train is at the previous station. Vasya's station is announced on the N-th station.

If Vasya hears the name of his station, then he will not miss it for sure.

However, every time Vasya listens to the names of the stations, he can fall asleep with a probability of 0.5. In this case, he won't hear the announcement on the next M stations. After sleeping through the announcement of the station, Vasya would never get off the train on it.

Now Vasya thinks whether to give up such a habit of sleeping on the train. For this, he wants to calculate the probability of oversleeping the announcement of his station.

Input file format

The first line of the input file contains integers N, M — total the number of stations and the number of stations that Vasya will sleep.

Output file format

Output a single number — the probability to oversleep the announcement of the station with an accuracy of at least 5 digits after the decimal point.

Constraints

1 ≤ M ≤ N ≤ 1000

Sample tests

2 1

0.5

3 1

0.25

Problem G. Factorio ≡

Statement

Leonid is an astronaut. His spaceship crashed on far unknown planet, full of natural resources. Leonid couldn't repair his spaceship, therefore he stayed on the planet. Many years later he achieved fantastic progress in planet exploration — he built an ore mining and processing mill.

The mill works in several stages:

1. N drills mine the ore. The speed of one drill is U_N kilograms per hour;

2. The ore gets to melting furnaces. The speed of one furnace is U_K kilograms per hour;

3. After furnaces, plates get to M machine-tools. The speed of one machine-tool is U_M kilograms per hour.

Leonid's mill pollutes the planet. This pollution disturbed inhabitants of the planet. Fictional arthropods have broken all furnaces.

Leonid is planning to build new furnaces and to renew manufacture. But at first he wants to calculate an optimal number of furnaces. We will call "surplus" the total quantity of the ore and plates, which is waiting for the processing. The number of furnaces is optimal if the surplus is minimal for the fixed period of time.

Help Leonid to calculate optimal number of furnaces. Obviously, Leonid wants to renew manufacture as fast as possible. Therefore among all possible answers, you should choose the minimal one.

Input format

The first line contains two integers N and M — the number of drills and machine-tools respectively.

The second line contains three integers U_N, U_K and U_M — the speeds of one drill, one furnace and one machine-tool respectively.

Output format

Print an integer — optimal number of furnaces.

If there are several possible answers, choose the minimal one.

Constraints

1 ≤ N, M, U_N, U_K, U_M ≤ 10⁹

Sample tests explanation

Let's consider first test. Let's fix the period of time — T = 10 hours. Amount of produced resources is shown in the table.

Surpluses are equal for three and four furnaces, which means that three furnaces is enough.

Sample tests

10 7
1 3 1

3

6 4
2 5 3

3

13 11
2 6 3

5

Problem H. Hydrocarbons ≡

Statement

A group of scientists studied a sample of vanadium catalyst of new generation. It allows to form different linear hydrocarbons from gaseous mixture of carbon and hydrogen.

Hydrocarbon with a certain structure became the result of each scientists experiment. His formula was recorded by spectral analysis device as a linear line. However, such form of record is short. Therefore, scientists needed to transform this record to the full version.

The full version of any hydrocarbonic chain, received in this experiment, is formed by the following rules:

1. The hydrocarbonic chain is pictured as a linear sequence of carbons (pictured by symbol 'C'). The link between carbons can be single (pictured as '-') or double (pictured as '=').

2. Each carbon is connected with hydrogens by single links, to be tetravalent. This means that each carbon should have 4 links (double link is counted as two links):

 — first and last carbons are connected to form equal angles. Namely, if there are two hydrogens they are connected by diagonal links ('/', '\'). If there are three hydrogens they are connected by up ('|'), down ('|') and side ('-') links.

 — the rest of carbons: single hydrogen is connected by up link and two hydrogens are connected by up and down links.

Short version of hydrocarbonic chain looks like a sequence CHa₁ CHa₂...CHa_N, where a_i (2 ≤ a_i ≤ 4) is a number of hydrogens with i^th carbon. There is no number when it's only one hydrogen. And there is no 'H' symbol when carbon does not have any hydrogens.

Note that short record should have the same orientation as full record. Which means that the leftmost hydrocarbon in short record should match the leftmost hydrocarbon in full record.

Look carefully at sample tests for complete understanding.

Input format

First line contains a string with short version of hydrocarbonic chain.

It is guaranteed that given hydrocarbonic chain is correct.

Output format

Print 5 × (3 + 2 ⋅ N) characters, where N is the number of carbons in given chain.

All spaces not occupied by symbols of links or atoms should be filled with symbol '.'.

Constraints

1 ≤ N ≤ 10000

Sample tests

CH4

..H..
..|..
H-C-H
..|..
..H..

CH2CH2

H.....H
.\.../.
..C=C..
./...\.
H.....H

CH3CH2CH2CH3

..H.H.H.H..
..|.|.|.|..
H-C-C-C-C-H
..|.|.|.|..
..H.H.H.H..

CH3CHCCH2

..H.H.....H
..|.|..../.
H-C-C=C=C..
..|......\.
..H.......H

Problem I. Encrypted phone ≡

Statement

This is an interactive problem.

As a punishment for Aleksey using his cellphone in the classroom, the teacher locked Aleksey's device with a password. This password is a sequence of N unsigned integers X_i, chosen by the teacher. However, the teacher did not want to waste his time for thinking up all numbers of the sequence. Therefore, he used a random number generator.

To unlock his device, Aleksey needs to guess the sequence. He can ask the teacher no more than Q questions: whether X_i is divisible by d. All numbers in the sequence are indexed from 1 to N.

Help Aleksey to regain access to his cellphone. He has already regretted his bad behavior during the class. He'll never do it again.

Input format

The first line contains one integer N — the length of the sequence.

It is guaranteed that the sequence is randomly generated before all Aleksey's questions and cannot be changed after that.

Output format

To give your answer to the teacher you have to print character "!" (without quotes), then print N space-separated guessed numbers X_i. Note that "!" and X₁ should be separated by a space too. Your program should terminate immediately after you gave the answer.

Interaction

Jury has fixed a number Q for each test — the maximum amount of questions, which you can ask the teacher. It is guaranteed that Q questions are enough to solve the problem. Q won't be given to your program as an input. If your solution asks more than Q questions, it will get "Wrong answer" for this test.

To ask a question your program has to print line "? i d" (without quotes), i (1 ≤ i ≤ N) and d (1 ≤ d ≤ 5000) are integers. Jury program gives your solution line "Yes" if X_i is divisible by d or "No" if it's not.

In the end of each question you have to print newline character \n and flush output buffer. To flush the buffer you can use (just after printing):

Constraints

100 ≤ N ≤ 400

1 ≤ X_i ≤ 5000

Q = min(150 ⋅ N, 5 ⋅ 10⁴)

Sample tests explanation

Note that the first test doesn't satisfy the constraints of the problem (N = 2).

It was created only to demonstrate interaction of solution program and jury program.

Q = 2000 for the first test.

Sample tests

2

Yes

No

Yes

No

No

Yes

Yes

Yes

Yes

Okay

? 1 3

? 1 5

? 1 7

? 1 11

? 1 13

? 1 4998

? 2 128

? 2 512

? 2 4096

! 4998 4096