Municipal stage of the All-Russian School Olympiad 2025, grades 9-11, Programming profile, Vologda and Krasnodar regions
1. Beautiful Time
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Vova likes to notice "beautiful" moments on digital clocks (which display time in the format HH:MM, that is, two digits for hours and two digits for minutes, for example, 07:05). Vova considers the clock readings beautiful when at least one of the following conditions is met:

1) The values of hours and minutes are equal, for example: 21:21.

2) The values of hours and minutes look mirrored, meaning the minute value is a permutation of the hour value's digits in reverse order, for example: 21:12.

3) The values of hours and minutes together form four consecutive digits (that is, each subsequent digit on the display is one more than the previous one), for example: 01:23.

Vova is interested in how many beautiful clock readings will appear on the display from the moment the clock shows $$$h_1$$$ hours and $$$m_1$$$ minutes until the moment the clock shows $$$h_2$$$ hours and $$$m_2$$$ minutes (both readings inclusive; if $$$h_1 = h_2$$$ and $$$m_1 = m_2$$$, then only one clock reading is considered).

Input

The input consists of four integers written sequentially: $$$h_1, m_1, h_2, m_2$$$, each number on a separate line ($$$0 \leq h_1, h_2 \leq 23$$$, $$$0 \leq m_1, m_2 \leq 59$$$).

Output

The output should be a single number— the count of beautiful time readings.

Scoring

Each test is evaluated independently.

Examples
Input
20
0
20
30
Output
2
Input
17
31
17
31
Output
0

2. Sum of Divisors
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Find a natural number in the range from 1 to $$$10^9$$$ that is equal to the sum of some $$$n$$$ of its divisors (the selected divisors must be distinct).

Input

One integer $$$n$$$ is given ($$$1 \le n \le 30$$$).

Output

In the first line of the output, print the sought number $$$m$$$. In the second line, print $$$n$$$ distinct natural numbers — the divisors of the number $$$m$$$, the sum of which equals $$$m$$$. The divisors can be printed in any order. If there are multiple correct answers, print any of them. If there is no solution, print -1.

Scoring

Each test is scored independently.

Example
Input
3
Output
6
3 2 1

3. Advertising
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a certain country, it was decided to start combating the overwhelming amount of advertising on television channels.To this end, a law was passed stipulating that the total amount of advertising time in any given hour should not exceed $$$T$$$ seconds.Write a program that will check for compliance with this law.

Input

The first line of the input contains an integer $$$N$$$ — the number of advertising inserts during the checked period ($$$1 \le N \le 10^5$$$).

The second line contains an integer $$$T$$$ ($$$0 \le T \lt 3600$$$).

Each of the next $$$N$$$ lines contains two integers $$$t_1$$$ and $$$t_2$$$ separated by a space — the start and end times of the next advertising insert ($$$0 \le t_1 \lt t_2 \le 10^9$$$). The times are given in seconds from the start of the check. The times are ordered in ascending order (i.e., in each subsequent line, $$$t_1$$$ is greater than $$$t_2$$$ in the previous line).

Output

If there is such an hour (that is, an interval of time lasting 3600 seconds) in which there was more than $$$T$$$ seconds of advertising, then output a single integer — the start time of such an interval. If there are multiple correct answers, output the smallest non-negative one. If the sought interval does not exist, output -1.

Scoring

Each test is evaluated independently. The tests are divided into groups corresponding to the following subtasks:

SubtaskAdditional ConditionsPoints
$$$1$$$$$$N \le 100$$$, $$$t_2 \le 10^4$$$30
$$$2$$$$$$N \le 10^5$$$, $$$t_2 \le 10^6$$$30
$$$3$$$-40
Examples
Input
3
1000
0 100
5000 5300
6000 7000
Output
3101
Input
1
3599
0 3599
Output
-1
Note

Reminder for those solving in Python: to input two integers separated by a space, you can do it like this: 

t1, t2 = map(int, input().split())

4. Robot Charging
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A robot with the code name MAGD has type $$$n$$$. To recharge, it requires a device with power $$$p$$$, satisfying the conditions:

$$$ p \ge n + 1 $$$ (otherwise, the robot will not have enough power to recharge)

$$$ p \le n + k $$$ (otherwise, the robot may burn out)

Among all suitable powers $$$p$$$, we need to choose the one for which LCM($$$n$$$, $$$p$$$) is minimized, so that the robot's battery lasts as long as possible. Given $$$n$$$ and $$$k$$$, we need to compute $$$p$$$.

LCM($$$a$$$,$$$b$$$) is the least common multiple of the numbers $$$a$$$ and $$$b$$$, that is, the smallest natural number that is divisible by both $$$a$$$ and $$$b$$$.

Input

Two numbers $$$n$$$ and $$$k$$$ are given, each on a separate line ($$$1 \le n \le 10^{12}$$$, $$$ 1 \le k \le 10^{12}$$$)

Output

You need to output the number $$$p$$$ — the required power of the device.

Scoring

Each test is evaluated independently. The tests are divided into groups corresponding to the following subtasks:

SubtaskAdditional ConditionsPoints
$$$1$$$$$$n \le 100, k \le 100$$$up to 15
$$$2$$$$$$n \le 10^5, k \le 10^5$$$up to 15
$$$3$$$$$$n \le 5 \cdot 10^7$$$up to 30
$$$4$$$—up to 40
Examples
Input
6
4
Output
9
Input
10
12
Output
20
Note

Note that the input data and the answer may exceed the range of possible values for a 32-bit integer variable, so it is necessary to use a 64-bit integer data type (type int64 in Pascal, type long long in C++, type long in Java and C#). In Python, no additional actions are required.

5. Order of Life
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a well-known mathematical game called "Life," the rules of which are very simple. Given a grid with $$$n$$$ rows and $$$m$$$ columns. Each cell can have one of two states: it is either alive or dead. A cell can have a maximum of 8 neighbors (if it is not located on the edges of the grid). Cells constantly compete for existence, and at each step of the game, the following changes occur:

  1. A living cell with two or three living neighbors remains alive. Otherwise, it dies from overpopulation or loneliness.
  2. A dead cell with three living neighbors comes to life.

The game ends when the grid stops changing. We will call this state stabilization.

It is known that a certain initial configuration was launched on the "Life" game simulator, which stabilized after a certain number of steps. The simulator recorded the positions of the cells in $$$k$$$ game states, but it broke and output them in a mixed order.

You need to determine the order in which these configurations of the grid appeared during the game. It is guaranteed that the sought permutation is unique. It is also guaranteed that the game will finish in no more than 2000 moves, starting from the initial position of the sought permutation.

Input

The first line contains a single natural number $$$k$$$ ($$$1 \leq k \leq 100$$$) — the number of recorded configurations of the grid.

The second line contains a single natural number $$$n$$$ — the number of rows in the grid.

The third line contains a single natural number $$$m$$$ — the number of columns. It is guaranteed that $$$1 \leq n \cdot m \leq 5000$$$.

Next, there are $$$k$$$ descriptions of the recorded configurations of the grid. Each configuration is described by $$$n$$$ lines with $$$m$$$ numbers in each, separated by spaces. If a cell is alive, it is encoded by the digit $$$1$$$, otherwise — by the digit $$$0$$$.

Output

You need to output a permutation of natural numbers from $$$1$$$ to $$$k$$$ — in what order the given configurations appeared during the game.

Scoring

Each test is evaluated independently. The tests are divided into groups corresponding to the following subtasks:

SubtaskAdditional ConditionsPoints
$$$1$$$$$$k=2$$$, in one of the configurations all cells are dead5
$$$2$$$$$$k \leq 10; n, m \leq 20$$$35
$$$3$$$-60
Examples
Input
3
3
3
1 0 0
0 1 0
1 0 0
0 0 0
1 1 0
0 0 0
0 0 0
0 0 0
0 0 0
Output
1 2 3
Input
2
2
3
1 0 0
1 1 0
1 0 1
1 1 0
Output
2 1