Problem A. Appropriate applicant ≡

Statement

Employees of the Research Institute of Advanced Technologies encountered a group of programmers in the forest. It turned out that exactly a percent of them are inexperienced, b percent are volunteers, and c percent are willing to live in a dormitory. Determine the minimum possible number of people in such a group and whether there is guaranteed to be at least one programmer with all three necessary qualities.

Input format

Three lines of input contain three natural numbers: a, b and c.

Output format

Output a single natural number in the first line. In the second line, output Yes or No — answers to the questions of the problem.

Constraints

1 ≤ a, b, c ≤ 99

Explanation of the examples

In the first example, the minimum possible number of people will be 20, for which all the specified percentages will be integers (4, 5, and 6). However, it's possible that different people possess the required qualities.

In the second example, the minimum possible number of people will be 4, and regardless of attempts to distribute the specified qualities among them, there will definitely be at least one person with all three.

Sample tests

20
25
30

20
No

75
75
75

4
Yes

Problem B. Bouncing particles ≡

Statement

Suppose there is a rectangular area divided into N × M square cells. Some of these cells have particles.

In one time step, each particle can either stay in place or move to any of its neighboring cells.

It is required to count the number of possible particle movements, such that after L steps, they all end up in the same cell.

Since the obtained number may be too large, the answer should be the remainder when dividing it by (2³² − 5).

Input format

At the beginning of the input data there is a triplet of numbers N, M и L.

Then, the number K is specified, followed by a set of 2 × K indices of the starting cells: X_i, Y_i.

It is assumed that cell indexing starts from zero.

Output format

The output data should contain the obtained number.

Constraints

1 ≤ N ⋅ M ≤ 2 500, 0 ≤ L ≤ 50, 2 ≤ K ≤ 50, 0 ≤ X_i < N, 0 ≤ Y_i < M.

Sample tests

10 10 2
2
4 5
5 4

256

10 10 2
2
2 3
7 6

0

Problem C. Compound palindrome ≡

Statement

A palindrome refers to a sequence of characters that reads the same in both directions (from left to right and from right to left).

A palindrome is compound if words of arbitrary length are used like characters.

It means that words located symmetrically from its center are the same.

Moreover, the words themselves do not have to be palindromes.

Consider a string, S, composed of digits and lowercase Latin alphabet letters.

The task is to split the original string into the maximum number of words,
ensuring that the resulting set is a compound palindrome.

Input format

The input consists of a single line, S.

Output format

The output should contain a sequence of word lengths, where the right ends of the words are located in the left half of the string.

If such a sequence does not exist, the output should remain empty.

Constraints

1 ≤ |S| ≤ 2 ⋅ 10⁶.

Sample tests

abcdefxyz123412xyzabcdef

6
3
2

ab32cdefxyz12xyzab14cdef

Problem D. Distribution by desks ≡

Statement

To conduct a mathematics Olympiad for grades 8 − 11, several classrooms have been allocated. The first classroom contains n rows of desks, with each row having 3 desks. Each desk accommodates exactly one person.

The organizers aim to seat students at all desks in the first classroom in such a way that in any 2 × 2 square of desks, students from different grades sit pairwise (meaning, in any square, there is one student from each of the 8th, 9th, 10th, and 11th grades).

In the illustration, you can see one of the suitable seating arrangements for n = 2 (in both the red and green squares, students from different grades are seated).

How many different ways exist to arrange the participants, given that the total number of students in any grade is greater than the number of desks in the first classroom?

Input format

The only input line contains a natural number n.

Output format

Output a single natural number — the answer to the problem's question modulo 10⁹ + 7 (since the number can be very large).

Constraints

1 ≤ n ≤ 10¹⁸

Sample tests

1

36

Problem E. Easy banknote thrower ≡

Statement

If you have already read the problem statement H. Hard banknote thrower: the task specification for this problem differs only in the operation performed by the banknote thrower. Namely: addition operation instead of bitwise multiplication operation.

Oleg has been using the services of Moneykoff Bank for a long time. Today, he needs to throw a large sum of money from his card, but he forgot its PIN code. Fortunately for the company, Moneykoff Bank's banknote throwers can provide hints about the PIN code.

Firstly, the banknote thrower reports the result of comparing neighboring digits in the PIN code. For example, for the PIN code 0911, it would be <>=, and for the popular PIN code 1234, it would be <<<.

Secondly, you can attempt to input a PIN code into the banknote thrower. If it proves incorrect, the banknote thrower will perform the operation: addition of the correct and entered PIN codes, and report the result of comparing adjacent digits in the resulting number. Of course, after such an operation, the number of digits may be greater than in the original PIN code. The Moneykoff Bank programmers have anticipated such overflow: if new digits appear, a comparison of neighboring digits will also be performed for them. For user safety, after 10 attempts to enter the wrong PIN code, the card is blocked.

Help Oleg determine the PIN code for the card before it is blocked.

Interaction protocol

This is an interactive problem. Your program will interact with a jury program by sending and receiving particular messages.

First, the jury's program sends your program an integer N — the number of digits in the PIN code. Then, on a new line, a string of N − 1 characters <, > and = — comparing neighboring digits in the PIN code.

After that, your program can make queries of the form "? X", where X is an integer, an attempt to enter a PIN code, and can be output without leading zeros. If the PIN code is correct, the jury's program responds to your program with the string "ok", after which your program must terminate. Otherwise, the jury's program responds with a string of at least N − 1 characters <, > and = — comparing neighboring digits in the result of addition of the correct and entered PIN codes.

Your program can only make 9 queries with an incorrect PIN code. If your program exceeds allowed number of queries, it will receive "Wrong answer" verdict.

Every query must be a single line ending with single end-of-line (\n). Output buffers must be flushed after every line:

If your program makes incorrect query, it will receive "Presentation error" verdict.

If your program receives the string "-1" from the jury's program, it must immediately terminate. This is possible if your program violates the interaction protocol. If your program does not terminate, the verdict may differ from those described above (for example, it may be "Runtime error").

Constraints

2 ≤ N ≤ 18

0 ≤ X < 10^N

Sample tests

4
<<>

<<>

<<>

<<>

=<=

==>

><>

><>

><>

><>

ok

? 1001

? 2002

? 3003

? 4004

? 5100

? 6000

? 7000

? 8000

? 9000

? 0451

3
==

>=

>=

><=

ok

? 100

? 200

? 300

? 777

18
====<<<<<<<<<====

ok

? 1234567899999

Problem F. Function with constraints ≡

Statement

Let's consider a function of the following form: F(X, Y) = AB ⋅ X + CD ⋅ Y.

The task is to find integer values for A, B, C and D, such that for a given set of points (X_i, Y_i)
the specified function satisfies pre-determined conditions:
RoundDawn(F(X_i, Y_i)) = Z_i or RoundUp(F(X_i, Y_i)) = Z_i,
where RoundDawn() и RoundUp() — denote rounding down and rounding up, respectively.

Input format

The input begins with the number N, followed by N conditions, each written in the following format.

First, the operation sign is indicated: '>' for RoundDawn or '<' for RoundUp.

Then, three integers follow: X_i, Y_i, Z_i.

Output format

If the problem has a solution, the output contains the number 1,
followed by the found values of A, B, C and D.

If there is more than one solution, any of them can be output.

If there is no solution, the output is the single number 0.

Constraints

All input values are integers.

 − 40 ≤ (X_i, Y_i, Z_i) ≤ 40, 0 < N ≤ 2000

Sample tests

4

> -2 -5 -6
<  3  7  8
> -1  1  1
<  4 -3 -5

1
-16 37
93 74

4

> -3 -1  1
<  5 -3 -6
>  7  4  1
<  2 -1 -3

0

Problem G. Game of Mafia ≡

Statement

Petya and his friends decided to play the popular game Mafia. Each player in this game receives one of the roles: sheriff, mafioso, or civilian. After roles are assigned, the city falls asleep, all players close their eyes, and only the mafiosi open theirs to get to know each other. Other players won't know for sure who is who. The game is divided into rounds, with one round consisting of a day and a night. During the day, players communicate and vote on whom to send to prison. At night, the sheriff searches for the mafia, and the mafia kills someone.

A total of N people gathered for the game. For such a number of players, the optimal distribution of roles is as follows: one sheriff and M mafiosi.

Usually, in Mafia games, those who are killed or sent to prison in the early rounds feel very sad since they haven't had a proper chance to play and must now wait for the game to finish. Petya and his friends are very friendly, so they agreed that in the first few nights, the mafia won't kill anyone, and there won't be a vote for imprisonment. This way, everyone will have a chance to play before the main chaos begins.

After a few rounds, Petya asked each participant to name M other players whom they believe are part of the mafia. During this time, the sheriff managed to check all players, so he knows exactly who the mafia is and will name them. On the other hand, the mafiosi won't help other players, so they won't expose each other.

Help Petya determine if it's possible to unequivocally identify the mafia based on the information received.

Input format

The first line of input contains two integers N and M — the total number of players and the number of mafiosi, respectively.

Next are N lines, where the i-th line contains M distinct integers a_i,j — the i-th player's assumptions about who the mafia is.

It is guaranteed that the input data is correct and corresponds to the situation described in the condition.

Output format

In a single line, output YES or NO — whether it is possible to unambiguously determine the players with the role of mafiosi.

Constraints

6 ≤ N ≤ 500

1 ≤ M ≤ ⌊ N2⌋

1 ≤ a_i,j ≤ N

Notes on samples

In the first example, players 3 and 5 are the mafia.

In the second example, the mafia could be pairs of players 1 and 5, 3 and 7, 4 and 8.

Sample tests

6 2
3 4
4 1
6 2
3 5
2 4
5 2

YES

8 2
3 7
7 5
1 8
7 1
2 7
2 5
4 8
5 1

NO

Problem H. Hard banknote thrower ≡

Statement

If you have already read the problem statement E. Easy banknote thrower: the task specification for this problem differs only in the operation performed by the banknote thrower. Namely: bitwise multiplication operation (see Explanation) instead of addition operation.

Oleg has been using the services of Moneykoff Bank for a long time. Today, he needs to throw a large sum of money from his card, but he forgot its PIN code. Fortunately for the company, Moneykoff Bank's banknote throwers can provide hints about the PIN code.

Firstly, the banknote thrower reports the result of comparing neighboring digits in the PIN code. For example, for the PIN code 0911, it would be <>=, and for the popular PIN code 1234, it would be <<<.

Secondly, you can attempt to input a PIN code into the banknote thrower. If it proves incorrect, the banknote thrower will perform the operation: bitwise multiplication of the correct and entered PIN codes, and report the result of comparing adjacent digits in the resulting number. Of course, after such an operation, the number of digits may be greater than in the original PIN code. The Moneykoff Bank programmers have anticipated such overflow: if new digits appear, a comparison of neighboring digits will also be performed for them. For user safety, after 10 attempts to enter the wrong PIN code, the card is blocked.

Help Oleg determine the PIN code for the card before it is blocked.

Explanation

Bitwise multiplication of two numbers refers to the operation in which the digits at the same positions are multiplied. That is, the digits at the zeroth position, first position, and so on are multiplied. Overflow is carried out to the higher digit following the regular rules of arithmetic.

More formally, bitwise multiplication can be expressed by the formula ∑_i = 0 a_i * b_i * 10ⁱ, where a_i and b_i are the digits at the i-th position.

Examples of bitwise multiplication are presented in the picture.

Interaction protocol

This is an interactive problem. Your program will interact with a jury program by sending and receiving particular messages.

First, the jury's program sends your program an integer N — the number of digits in the PIN code. Then, on a new line, a string of N − 1 characters <, > and = — comparing neighboring digits in the PIN code.

After that, your program can make queries of the form "? X", where X is an integer, an attempt to enter a PIN code, and can be output without leading zeros. If the PIN code is correct, the jury's program responds to your program with the string "ok", after which your program must terminate. Otherwise, the jury's program responds with a string of at least N − 1 characters <, > and = — comparing neighboring digits in the result of bitwise multiplication of the correct and entered PIN codes.

Your program can only make 9 queries with an incorrect PIN code. If your program exceeds allowed number of queries, it will receive "Wrong answer" verdict.

Every query must be a single line ending with single end-of-line (\n). Output buffers must be flushed after every line:

If your program makes incorrect query, it will receive "Presentation error" verdict.

If your program receives the string "-1" from the jury's program, it must immediately terminate. This is possible if your program violates the interaction protocol. If your program does not terminate, the verdict may differ from those described above (for example, it may be "Runtime error").

Constraints

2 ≤ N ≤ 18

0 ≤ X < 10^N

Sample tests

4
<<>

===

=<>

<>=

=<>

=<>

=<>

=<=

<>>

<>>

ok

? 1000

? 0010

? 0020

? 0012

? 0013

? 0014

? 0015

? 0210

? 0150

? 0451

3
==

>=

>=

>=

<>=

ok

? 100

? 200

? 300

? 400

? 333

18
====<<<<<<<<<====

ok

? 1234567899999

Problem I. Improvement of tessitura ≡

Statement

The performer's voice is characterized by the range of notes they can sing. This range is referred to as tessitura. A song is characterized by a single number, h_i — representing its pitch. If h_i falls within the performer's tessitura, the song can be sung.

Paulundra is preparing for a series of c concerts.For each concert, she wants to prepare k songs that have not yet been sung from the n available ones. Initially, Paulundra can sing songs in the range from l to r. After each concert, she improves, and the range expands by d. She decides in which direction and by how much to expand the tessitura (it can be expanded in one direction or in both directions at once, but in total no more than d). Help her determine if she can allocate her efforts correctly and prepare for all concerts successfully.

Input format

The first line of input contains five integers: l, r, d, c, k. The second line contains a single integer n. The third line contains n integers representing h_i.

Output format

Output "YES" if all c concerts will take place and "NO" otherwise.

Constraints

1 ≤ n, k ≤ 10⁵

1 ≤ h_i, l, r, d ≤ 10⁹

1 ≤ c ≤ 100

l,r ∈ [h₁, h₂, …, h_n]

All h_i are different.

Sample tests

1 100 200 2 2
5
1 100 200 300 400

YES

7 8 4 3 2
6
5 6 7 8 11 12  

YES

1 5 1 6 1
6
1 2 3 4 5 10

YES

4 6 4 3 2
6
4 6 10 11 12 13 

NO

Problem J. Jump to number ≡

Statement

The task at hand involves finding the k-th sequentially ordered q-ary number (starting from the 1st),
where the sum of its digits equals n, and its length does not exceed l.

Input format

Four integers are provided in the input data: q, n, l and k.

Output format

The output data should contain the resulting number.

If such a number does not exist or if it exceeds the permissible range,
the output data should remain empty.

Constraints

2 ≤ q ≤ 10, 1 ≤ (n, l) ≤ 4000, 1 ≤ k ≤ 10¹⁸

Sample tests

10 100 12 1

199999999999

2 1 1 2

Problem K. Knitting sweaters ≡

Statement

If we trust contemporary sources, the renowned patterns on winter clothing first emerged in the Norwegian town of Setesdal. The popularization of Nordic sweaters was influenced by the film "Serenade of the Sun Valley." The sweater featuring the protagonist's reindeer became a sought-after item, initially in men's and later in women's wardrobes. Nowadays, sweaters with such Christmas patterns are increasingly visible on urban streets.

New Year is just around the corner! Hence, it's the perfect time to contemplate festive attire.

Timofey, a true fashion connoisseur, plans to handcraft a New Year sweater. Naturally, it should depict a reindeer with beautiful, branching antlers.

As a genuine programmer, Timofey decided that the reindeer antlers should represent a binary tree with 2ⁿ leaves and vertically centered lines of length k.

Since Timofey, a true knitter, is currently engrossed in the search for threads, needles, and hooks, assist him in drawing the reindeer antlers with the specified parameters.

Input format

The input file contains two lines with two natural numbers, n and k.

Output format

Output the required image. Utilize the # symbol (ASCII code 35) for forming lines and the . symbol (ASCII code 46) for the background. Your program should avoid outputting unnecessary rows or columns filled only with background symbols.

Constraints

1 ≤ n ≤ 8

2 ≤ k ≤ 10

Sample tests

1
8

#.#
#.#
#.#
#.#
#.#
#.#
#.#
###

3
2

#.#.#.#.#.#.#.#
###.###.###.###
..#...#.#...#..
..#####.#####..
......#.#......
......###......

2
5

#.#.#.#
#.#.#.#
#.#.#.#
#.#.#.#
###.###
..#.#..
..#.#..
..#.#..
..#.#..
..###..

Problem L. Lines and triangles ≡

Statement

Let's consider a configuration of n lines on a plane. The task is to count the maximum number of triangle cells formed as a result of subdivison plane by these lines.

Input format

The input begins with a natural number n, followed by exactly n lines. Each line is defined by a pair of distinct points: (Ax_i, Ay_i), (Bx_i, By_i).

Output format

The output should contain the number of triangles obtained.

Constraints

It is guaranteed that no two lines coincide.

All input values are integers.

 − 10⁴ ≤ (Ax_i, Ay_i, Bx_i, By_i) ≤ 10⁴, 3 ≤ n ≤ 300

Sample tests

5
  0 -20  15 -20
-10  10  35 -35
  0   0   0 -10
-10   0  30   0
-20   0   0  20

3

5
-10   0   0 -20
-20 -10 -10 -30
  0   0  10  24
  0  10  10 -10
-10   0   0  24

0

Problem M. Mountain ≡

Statement

The mountain is represented by a binary heap with n vertices, there is also a number k, which represents the sum of distances between all pairs of vertices. Given the value of k, find n.

In this context, a binary heap is an undirected binary tree that satisfies the following conditions:

• Each vertex has at most three neighbors.
• The depth of all leaves (distance to the root) differs by no more than 1 layer.
• The last layer is filled from left to right without "holes".

For example, a binary heap with 4 vertices:

Input format

The input consists of a single line containing a natural number k.

Output format

Output n.

Constraints

0 ≤ k ≤ 10¹⁸

Пояснение к примеру

The distance between the 1st and 2nd vertices is 1. The distance between the 1st and 3rd vertices is 1. The distance between the 1st and 4th vertices is 2. The distance between the 2nd and 3rd vertices is 2. The distance between the 2nd and 4th vertices is 1. The distance between the 3rd and 4th vertices is 3. The sum of all distances is 1 + 1 + 2 + 2 + 1 + 3 = 10.

Sample tests

10

4