Problem AA. Amazon ≡

Statement

Fantasy chess is a variant of chess composition. Puzzles of this variant contain changes to some of the accepted rules of the game or utilize unusual pieces or boards.

Amazon is a fantasy chess piece which can move as either a queen or a knight. It is usually represented on diagrams as a horse with the crown. You can see all possible moves of this piece on a picture below. Amazon is so strong and independent that it can checkmate the enemy king without the help of another friendly piece.

White amazon and black king are positioned on a normal chess board. Determine whether the king is checkmated.

Input format

First line of input contains two integers separated by space: x₁ and y₁ — coordinates of the white amazon. Second line contains coordinates of the black king x₂ and y₂ in the same format. Piece positions are guaranteed to be different.

Output format

Output Yes or No — answer to the problem's question.

Constraints

1 ≤ x₁, x₂, y₁, y₂ ≤ 8

Notes on the samples

See the picture. In the second sample the king can capture the amazon.

Sample tests

7 6
7 8

Yes

6 7
7 8

No

Problem AB. Bonus points ≡

Statement

Oh, those math lessons! Today, for example was the fourth test on the subject. To those who finished ahead of time the teacher offered an extra task for bonus points.

Two n-digit numbers are written on the blackboard, first composed of only the digit d₁, second — of only the digit d₂. Determine which digit occupies position k in the sum of those numbers. Positions are numbered left to right starting from 1.

You want bonus points, don't you?

Input format

Four lines of input contain four integers: n, d₁, d₂ and k. It is guaranteed that k is correct.

Output format

Output a single decimal digit — answer to the problem.

Constraints

1 ≤ n ≤ 10⁹

1 ≤ k ≤ n + 1

1 ≤ d₁, d₂ ≤ 9

Notes on sample

Sample has n = 2 (adding two-digit numbers), d₁ = 5 (first number is 55), d₂ = 8 (second number is 88). Sum is 55 + 88 = 143. k = 1 (teacher asks the first digit of the result). The digit at first position of the number 143 is 1.

Sample tests

2
5
8
1

1

Problem AC. Clustering of triangles ≡

Statement

Let there be a set of triangles represented by 3-dimensional vertex coordinates.

You must determine all maximal subsets of triangles such that triangles of each set belong to a single plane.

Input format

Input contains integer N, followed by 9 × N integers, representing vertex coordinates:

(X1i, Y1i, Z1i), (X2i, Y2i, Z2i), (X3i, Y3i, Z3i), where i = 0, 1, …, (N − 1).

Output format

Output must contain the number of subsets M, followed by M records of the following structure.

The number of triangles present in the set, followed by their indices in input (indexing starts at 0).

Both sets and triangles may be output in arbitrary order.

Constraints

It is guaranteed that there are no degenerate (zero area) triangles in input.

 − 1000 ≤ (Xki, Yki, Zki) ≤ 1000,

2 ≤ N ≤ 10⁵.

Sample tests

6

 166  -61 -108
-175  122  133
 -81   96   71

-100 -228  246
 -64   58  -68
 -85   12  -27

 131 -140 -101
  37 -114  -39
  72  -35  -46

 137 -186 -113
  84 -127  -70
  66   11  -34

-140 -143  121
 -45  -73   98
  34   31   25

-135 -170 -173
 -86   45 -252
  39  124   31

3

3 3 2 0
2 4 1
1 5

Problem AD. Digital circuit ≡

Statement

Let there be a rectangular ASCII-art image of a digital circuit, composed of logical elements and wires connecting them.

Logical elements are represented as rectangular areas bordered by '#' (ASCII 35) characters.

Each element always contains a description composed of digits and small Latin letters.

Description may be split into several parts, separated by spaces, and span multiple lines.

Wires are represented as sequences of '.' (ASCII 46) characters.

The rest of the circuit is filled with spaces.

Any two elements can not be adjacent to each other (there is always space between them).

Wires can only connect at 90^∘ angle.

Parallel wires can not be adjacent to each other (there is always space between them).

An element is considered connected to a wire if their characters are adjacent either horizontally or vertically.

Wires can not cross area occupied by an element.

Bus is a set of connected wires.

Given the image, determine the set of logical elements and buses connected to them.

Input format

Input contains an ASCII image.

Output format

Output the number of logical elements N,
followed by N lines, with each line containing a description of a single element.
Parts of a description must be separated by spaces.

Order of elements in output must correspond to the order at which elements occur
in the input image when traversing by rows from the top-left corner.

Next, output the number of buses M, followed
by sets of connected elements.

Each set starts with a number of elements in it,
followed by element indices
(starting from zero).

Constraints

Total number of characters in the image does not exceed 10⁶.

Sample tests

           #####        
#######    #abc#        
# xyz #    #123#        
#     #....#####   #####
#######    .       #   #
           .    ...#abc#
............    .  #   #
.               .  #####
. ############  .       
. #  123     #  .       
. #    xyz   #........  
. ############       .  
.         .          .  
...........          .  
          .    #########
          .....#  abc  #
 #######  .    #########
 #xyz  #...             
 #     #  .       ##### 
 # abc #  ........#123# 
 #######   .      ##### 
           #####        
           #xyz#        
           #####        

8
abc 123
xyz
abc
123 xyz
abc
xyz abc
123
xyz

3
6 0 3 4 5 6 7
3 2 3 4
2 0 1

Problem AE. Equidistant strings ≡

Statement

Consider a set of all possible strings of exactly n characters, consisting of digits and small Latin letters.

Hamming distance H(A, B) is equal to the number of positions i from 1 to n where A[i] ≠ B[i].
Let us define P(A, B) as a set of strings of length n equidistant from A and B ({ C: H(A, C) = H(B, C)}).

Determine the number of strings in the set P(A, B).

Since the answer may be too large, output the remainder of it divided by 10⁹.

Input format

Input contains two strings: A и B.

Output format

Output a single integer — the answer.

Constraints

1 ≤ n ≤ 10⁴.

Sample tests

abc
1b3

41688

ab
ab

1296

Problem AF. Fencing the bishop ≡

Statement

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

Chess board is a field of 8 by 8 of alternating white and black cells. Columns are indicated by letters from A to H, rows — by digits from 1 to 8. Cell coordinates are encoded as [column][row], for example E2. The cell A1 in the bottom left is black.

There is a bishop on the chess board at some cell of a given color. Recall that the bishop is a piece which can move over diagonals in any direction for any number of cells. The goal is to determine actual position of the bishop by monitoring some rectangular areas of the board.

Your program must make requests of the form "? A B", where A and B — coordinates of two board cells, bottom left and top right of the rectangle you want to monitor. After every request the bishop makes a move and your will receive a reply communicating which of the monitored rectangles contain the bishop after the move.

Your program must determine the bishop position by making no more than 6 requests. It is guaranteed that bishop moves are predetermined and do not depend on requests.

Input format

First line of input contains string color, with value of either white or black — color of the cell initially occupied by bishop.

Interaction protocol

To make a request, your program must output line "? A B", where A, B — strings of two characters, coordinates of the bottom left and top right of the rectangle you want to monitor.

After setting the monitoring bishop moves and jury program replies to your program with the string S of characters 1 or 0 — with i-th characters equals 1, if bishop is inside the i-th monitored rectangle.

When your program determines the current bishop position X, it must output "! X", where X — string of two characters, bishop cell coordinates. After outputting the answer your program must terminate.

If your program makes incorrect query, it will receive "Presentation error" verdict. If your program exceeds allowed number of queries, it will receive "Wrong answer" verdict.

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

Constraints

"A1"  ≤ A, B, X ≤  "H8"

A ≤ B

Notes on samples

Bishop movements and monitored areas from the first sample are presented on the picture.

Sample tests

white

0

01

000

0000

00000

100100

? B2 E4

? A4 C7

? A7 B8

? E4 F8

? H4 H8

? G1 H2

! E4

black

0

01

? A1 A1

? C3 C3

! C3

Problem AG. Graph minimization ≡

Statement

Let there be two disjoint sets of nodes of some oriented graph: A and B.
For each node of A, set of all nodes of B reachable from it is also given.
It is known that any node of A should not have incoming edges, and that any node of B should not have outgoing edges.

There can be set of intermediate nodes C in the graph that connected with nodes from A and B.
But any two nodes from C should not be connected to each other.

You are to obtain a graph with minimal number of edges satisfying this description.
If several optimal variants exist, choose a graph with minimal number of nodes.

The answer is the number of nodes and edges in the obtained graph.

Input format

Input contains two integers: N — size of A and M — size of B,
followed by the subsets of nodes of B reachable from every node of A.

Each subset starts with a number of nodes in it (may be zero),
followed by the indices of nodes (indexing starts from zero).

Output format

Output must contain two integers: number of nodes and edges.

Constraints

1 ≤ (N, M) ≤ 1000

Sample tests

5 4

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

10 9

5 4

2 1 0
2 0 2
2 2 3
2 3 0
2 0 1

9 10

Problem AH. Health and light ≡

Statement

The city of N has a happy event! On the single street of the city, new street lamp will be installed and the new pharmacy will open. Help the city governor to find optimal places for these objects.

The street is represented by a segment of coordinate axis, where the leftmost house has coordinate 0. Let's assume house sizes to be negligibly small compared to the street length and represent houses as points on the axis.

The lamp has "brightness" parameter expressing the largest distance from the lamp where the light reaches. For example when brightness is equal to 10, lamp installed at the point x = 25 will light the street on the segment from 15 to 35 inclusive.

The pharmacy has "remoteness" parameter expressing the largest distance from it to the house such that people from that house will still visit. For example when remoteness is equal to 100, pharmacy located at point x = 25, will be visited by people living in houses with coordinates from 0 to 125 inclusive (there are no houses with negative coordinates).

Input format

First line of input contains three integers separated by spaces: n — number of houses, a — brightness и b — remoteness. Next n lines contain two space-separated integers each: x_i, q_i — coordinate of the house and number of people living in it (houses may be empty).

Output format

Output two integers — maximum number of houses illuminated by the lamp and maximum number of people who will visit the pharmacy. Both lamp and pharmacy may be located between the houses as well as at points with the coordinate of some house.

Constraints

1 ≤ n, a, b ≤ 10⁵

0 ≤ x_i, q_i ≤ 10⁹

Notes on sample

Sample contains five houses, lamp brightness 15 and pharmacy remoteness 20. Lamp can be installed at either point 15, or point 25, in both cases 4 houses will be illuminated. Pharmacy may be located at point 20, in which case all city inhabitants will be able to visit.

Sample tests

5 15 20
0 6
10 5
20 0
30 7
40 10

4 28

Problem AI. Identical digits ≡

Statement

Zhenya Slavin is a first human born on Mars. He is yet a little boy and likes to look at the digital clock hanging opposite of his bed. Most of all he likes the moments when all digits on the clock become identical. In those moments he always claps joyfully.

Since the period of rotation of Mars around its axis is different from that of the Earth, Martian colonists decided that:

• a single Martian day will be exactly h Martian hours;
• a single Martian hour will be exactly m Martian minutes;
• a single Martian day minute be exactly s Martian seconds.

Current time on Mars is h_M hours, m_M minutes and s_M seconds. After how many seconds will Zhenya clap? Time on the Martian digital clocks is displayed with leading zeroes in all positions. Extra positions are not used.

Input format

Input contains six integers, one per line: h, m and s — description of Martian day subdivision, followed by h_M, m_M and s_M — current time.

Output format

Output a single integer — number of seconds until the moment when all digits on the clock become identical.

Constraints

0 ≤ h_M < h ≤ 10⁶

0 ≤ m_M < m ≤ 10⁶

0 ≤ s_M < s ≤ 10⁶

Notes on samples

It the first sample Martian days are no different from Earth ones (24 hours of 60 minutes of 60 seconds). Now it is 23 hours 50 minutes exactly (clock displays digits 23:50:00). After 10 minutes (or 600 seconds) the clock will display zeroes in all positions.

It the second sample Martian days contain 627 hours of 5 minutes of 777 seconds. Now it is 49 hours 3 minutes and 2 seconds (clock displays digits 049:3:002). After 61 hours 3 minutes and 109 seconds (or 239425 Martian seconds) the clock will display ones in all positions.

Sample tests

24
60
60
23
50
0

600

627
5
777
49
3
2

239425

Problem AJ. Jolly evening ≡

Statement

Marina Tsvetaeva, Andrej Belyj and Sasha Chernyj are spending the evening playing chess. For each game two of them are playing and the third person is waiting to take the place of the loser. The winner of each game plays next game with white pieces.

After playing n games silver age poets were surprised to find out that white side had been repeatedly winning k times in a row, followed by a black victory every time.

Andrej Belyj likes to play with white pieces, Sasha Chernyj — with black, Marina Tsvetaeva likes either of the colors. Determine the number of games where both players played with the color they like. First game was between Andrej Belyj (played with white) and Sasha Chernyj (played with black). No game was a draw.

Input format

Two lines of input contain two integers n and k.

Output format

Output a single integer — problem answer.

Constraints

1 ≤ n ≤ 10⁹

1 ≤ k ≤ 100

Notes on sample

4 games were played. White player had been winning one game, and then losing the next one.

In the first game Belyj — Chernyj both play the color they like. Andrej wins, playing with white.

In the second game Belyj — Tsvetaeva both play the color they like. Andrej loses, playing with white.

In the third game Tsvetaeva — Chernyj both play the color they like. Marina wins, playing with white.

In the final game Tsvetaeva — Belyj only Marina plays the color she likes. So the answer is 3 games.

Sample tests

4
1

3

Problem AK. Karousel ≡

Statement

Children theme park has opened a new attraction "Karousel" for n persons. According to safety regulations, when the attraction is running, children must be seated so that the center of mass of all riders coincides with the center of carousel and the distances between them alongside the circumference is equal. For example, for n = 6, 2, 3 or 6 children may ride simultaneously, while for n = 5 — only exactly 5. In other words, attraction is allowed to start if it has k children, where k — is a divisor of n and k ≠ 1.

There are d children waiting in the queue for the carousel. After finishing the ride children leave to other attractions. What is the minimum number of runs to let all children ride the carousel once each?

Input format

Two lines of input contain integers n and d.

Output format

Output a single integer — answer to the problem. If it is impossible for all children to get a ride, output -1.

Constraints

1 ≤ (d, n) ≤ 10⁵

Notes on sample

In the first sample n = 16 and d = 14 (16 seats on carousel, 14 children in the queue). It is enough to run carousel 3 times: first time for 8 children, second — for 4, third — for 2.

In the first sample n = 15 and d = 7. It is impossible to let all children ride since according to regulations only 3, 5 or 15 are allowed to ride at a time.

Sample tests

16
14

3

15
7

-1

Задача B0. Олины торты ≡

Условие

Сегодня к Оле в гости придет N одногруппников, из-за чего она решила приготовить N тортов. В ее распоряжении есть M грамм сахара. Поскольку Оля не хочет никого обидеть, в каждом торте должно быть одинаковое количество сахара. Какое максимальное количество сахара может содержать каждый торт?

Формат входных данных

Входные данные содержат числа M и N, каждое на новой строке.

Формат выходных данных

Необходимо вывести единственное число — максимальное количество сахара.

Ограничения

1 < N, M < 10000

Примеры тестов

10
2

5

6
4

1.5

Задача B1. Заплыв ≡

Условие

Оксана любит плавать и готовится к заплыву через Амурский залив. Для подготовки она каждый день приходит в бассейн и проводит там несколько часов, переплывая от одного края бассейна до другого. Длина бассейна, где занимается Оксана — N метров. Она успевает пересечь его за M секунд, и ещё K секунд тратит на разворот. Сколько метров Оксана успеет проплыть за L минут?

Формат входного файла

Первая строка входного файла содержит четыре натуральных числа: N M K L.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество проплытых метров.

Ограничения

1 ≤ N, M, K, L ≤ 1000

Примеры тестов

25 76 2 45

865

50 50 1 60

3530

Задача B2. Строки в книге ≡

Условие

В книге на одной странице помещается K строк. Таким образом, на 1-й странице печатаются строки с 1-й по K-ю, на второй - с (K + 1)-й по (2 × K)-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

50 1

1 1

20 25

2 5

15 43

3 13

Задача B3. Слон на шахматной доске ≡

Условие

Слон — шахматная фигура, которая может двигаться на любое число клеток по диагонали.

Имеется шахматная доска N на N клеток. В клетке с координатами (X; Y) находится слон. Требуется вывести шахматную доску с изображением слона и всех клеток, в которые он может походить.

Клетки чёрного цвета обозначаются символом '#' (ASCII 35), клетки белого цвета обозначаются символом '.' (точка, ASCII 46), клетка со слоном обозначается символом 'X' (ASCII 88), клетка, в которую может походить слон обозначается символом '*' (ASCII 42).

Ось ординат (OY) направлена вертикально вниз. Верхний левый угол доски имеет чёрный цвет и координаты (1; 1).

Формат входного файла

Входной файл содержит целые числа N X Y.

Формат выходного файла

Выходной файл должен содержать N строчек из N символов каждая — изображение шахматной доски.

Ограничения

2 ≤ N ≤ 100

1 ≤ X, Y ≤ N

Примеры тестов

8
3 5

#.#.#.*.
.#.#.*.#
*.#.*.#.
.*.*.#.#
#.X.#.#.
.*.*.#.#
*.#.*.#.
.#.#.*.#

3 1 2

#*#
X#.
#*#

Задача B4. K-й бит в числе ≡

Условие

Дано целое неотрицательное число x, требуется вернуть значение k-го бита числа x, то есть k-й разряд двоичного представления числа x. Разряды нумеруются с 0 начиная с младшего. Считается что число содержит неограниченное количество лидирующих нулей.

Формат входного файла

Первая строка входного файла содержит два числа x, k.

Формат выходного файла

Входной файл должен содержать одно число  — значение k-го бита числа x.

Ограничения

0 ≤ x ≤ 2 ⋅ 10⁹

0 ≤ k ≤ 300

Примеры тестов

0 10

0

123 0

1

12345 100

0

Задача B5. Стремление к нулю ≡

Условие

Дано число N и массив из S целых чисел A_i.

За одну операцию можно заменять число N на любое из чисел N + A_i, N − A_i, N × A_i, N / A_i.

Второй операнд может быть любым элементом массива A.

Деление выполняется нацело, с округлением вниз.

Необходимо рассчитать минимальное количество операций, необходимых, чтобы получить из числа N число 0.

Формат входных данных

Первая строка входных данных содержит целое число N.

Вторая — целое число S.

Третья — S целых чисел, массив A.

Формат выходных данных

Выходные данные должны содержать одно целое число — минимальное количество операций.

Ограничения

0 ≤ N, A_i ≤ 2 * 10⁹

1 ≤ S ≤ 100

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

100 / 25 = 4 ; 4 - 4 = 0

100 / 11 = 9 ; 9 / 11 = 0

В обоих случаях затрачено 2 операции, что в данном примере является минимально возможным.

Примеры тестов

100
6
4 7 10 5 25 11

2

Задача B6. Два измерения ≡

Условие

Ученые планируют провести важный эксперимент с использованием исследовательского модуля на планете X-2019. В процессе эксперимента будет проведено два измерения: основное и контрольное. Каждое измерение занимает ровно один час и должно начинаться спустя целое число часов после начала работы исследовательского модуля.

Данные эксперимента планируется немедленно передать на орбитальную станцию. Канал связи с орбитальной станцией будет установлен с l-го по r-й час от начала работы исследовательского модуля, включительно. Кроме того, согласно плану эксперимента между измерениями планета должна совершить целое число оборотов вокруг своей оси. Планета X-2019 осуществляет оборот вокруг своей оси за a часов.

Таким образом, если измерения осуществляются на i-м и j-м часу, то должно выполняться неравенство l ≤ i ≤ j ≤ r, а величина (j − i) должна быть кратна~a. Теперь учёным необходимо понять, сколько существует различных способов провести измерения.

Требуется написать программу, которая по заданным границам времени измерений l и r и периоду обращения планеты вокруг своей оси a определяет количество возможных способов провести измерения: количество пар целых чисел i и j, таких что l ≤ i ≤ j ≤ r, и величина (j − i) кратна a.

Формат входных данных

Входные данные содержат три целых числа, по одному на строке: l, r и a.

Формат выходных данных

Выведите одно целое число: количество способов провести измерения.

Ограничения

1 ≤ l ≤ r ≤ 10⁹, 1 ≤ a ≤ 10⁹

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

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

В первом примере можно провести измерения в следующие пары часов: (1, 3), (1, 5), (2, 4), (3, 5).

Во втором примере продолжительности работы канала связи недостаточно, чтобы провести два измерения.

Примеры тестов

1
5
2

4

4
9
6

0

Задача B71. Шифр ≡

Условие

Отряд под командованием лейтенанта О’Денила нашел странный текст, который состоит из n пар целых неотрицательных чисел a, b с одинаковым количеством разрядов. Лейтенант понял, что текст зашифрован и передал его в штаб.

В штабе дешифровщики поняли, что для расшифровки текста необходимо, чтобы пары были отсортированы следующим образом: первые числа a - по возрастанию, а вторые b - по убыванию в случаях, где первые числа соответствующих пар равны т.е. там, где

a_i = a_j, i ≠ j, i, j = 1,2,3,…,n

Помогите дешифровщикам получить зашифрованную последовательность, написав программу-дешифратор, сортирующие пары чисел указанным способом.

Формат входных данных

В первой строке подается единственное целое число n - количество пар чисел в последовательности.

В следующих n строках приводится n пар целых чисел a, b - перечень пар чисел для расшифровки.

Формат выходных данных

Выведите n строк, в каждой из которых записана пара целых чисел a, b - искомую последовательность.

Ограничения

2 ≤ n ≤ 10³

 − 10⁹ ≤ a, b ≤ 10⁹

Примеры тестов

3
1123 1325
6356 3731
6356 3738

1123 1325
6356 3738
6356 3731

Задача B72. Быстрая помощь ≡

Условие

В городе В случилась катастрофа: неожиданно наступила зима. Чтобы облегчить судьбу жителей В, из города М решено направить N самолётов с тёплой одеждой.

Самолёты имеют различную скорость, так что самолёт номер i затратит на полёт в точности a_i минут. Разгрузка любого самолёта в аэропорту В занимает L минут, после чего аэропорт готов к приёму следующего самолёта.

Аэропорт города М большой, и способен оправлять любое необходимое количество самолётов одновременно. Аэропорт города В, напротив, может принимать и разгружать самолёты только по одному.

Самолёты могут взлетать в любом порядке, но не должны обгонять друг друга в воздухе, т. е. если самолёт 1 взлетел раньше самолёта 2, то и приземлиться он должен раньше.

Требуется определить минимальное время в минутах, требуемое на перелёт и разгрузку всех самолётов.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

2 10
8 5

25

Задача B73. Гражданская оборона ≡

Условие

Штаб гражданской обороны Тридесятой области решил обновить план спасения на случай ядерной атаки. Известно, что все n селений Тридесятой области находятся вдоль одной прямой дороги. Вдоль дороги также расположены m бомбоубежищ, в которых жители селений могут укрыться на случай ядерной атаки.

Чтобы спасение в случае ядерной тревоги проходило как можно эффективнее, необходимо для каждого селения определить ближайшее к нему бомбоубежище.

Формат входного файла

Первая строка входного файла содержит число n — количество селений. Вторая строка содержит n различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го селения.

Третья строка входного файла содержит число m — количество бомбоубежищ. Четвертая строка содержит m различных целых чисел, i-е из этих чисел задает расстояние от начала дороги до i-го бомбоубежища.

Формат выходного файла

Выведите в выходной файл n чисел — для каждого селения выведите номер ближайшего к нему бомбоубежища. Бомбоубежища пронумерованы от 1 до m в том порядке, в котором они заданы во входном файле.

Ограничения

1 ≤ n, m ≤ 100000

Все расстояния положительны и не превышают 10⁹. Селение и убежище могут располагаться в одной точке.

Примеры тестов

4
1 2 6 10
2
7 3

2 2 1 1

Задача B74. Большой линейный коллайдер ≡

Условие

Группа ученых работает в международной научной лаборатории, которая занимается исследованиями поведения элементарных частиц в установке для экспериментов "Большой линейный коллайдер" (БЛК). Установка БЛК представляет собой прямую, в некоторых точках которой размещаются частицы, которые могут перемещаться вдоль прямой.

В очередном эксперименте в БЛК размещаются n частиц, каждая из которых представляет собой либо отрицательно заряженную частицу — электрон e⁻, либо положительно заряженную частицу — позитрон e⁺. В эксперименте i-я частица исходно размещается в точке с координатой x_i. После начала эксперимента в результате работы БЛК частицы начнут перемещаться в разные стороны вдоль прямой: e⁻ частицы перемещаются по направлению уменьшения координаты, а e⁺ частицы — по направлению увеличения координаты. Абсолютные величины скоростей всех частиц одинаковы и равны 1.

Если в процессе перемещения частицы e⁻ и e⁺ оказываются в одной точке, то они взаимодействуют и обе исчезают, при этом они не влияют на дальнейшее поведение остальных частиц.

Ученые выбрали m различных моментов времени t₁, t₂, ..., t_m, для каждого из которых их интересует, какое количество частиц находится в БЛК непосредственно после каждого из этих моментов времени. Отсчет времени начинается с момента 0, когда частицы приходят в движение. Частицы, исчезнувшие в результате взаимодействия в момент времени t_j, не должны учитываться при подсчете количества частиц для этого момента времени.

Требуется написать программу, которая по описанию исходного расположения и типов частиц, а также заданным моментам времени, определяет для каждого из моментов количество частиц, которое будет находиться в БЛК непосредственно после этого момента.

Формат входного файла

Первая строка входного файла содержит число n — количество частиц. Последующие n строк описывают частицы следующим образом: каждая строка содержит по два целых числа x_i и v_i — координату i-й частицы и ее тип соответственно (x₁ < x₂ < x₃ < ...  < x_n). Частица e⁻ описывается значением v_i =  − 1, а частица e⁺ описывается значением v_i = 1.

Следующая строка содержит целое число m — количество моментов времени, которые выбрали ученые. Последняя строка содержит m целых чисел: t₁,t₂,...,t_m.

Формат выходного файла

Для каждого момента времени во входном файле требуется вывести одно число: количество частиц в БЛК непосредственно после этого момента.

Ограничения

1 ≤ n, m ≤ 200000

 − 10⁹ ≤ x_i, m ≤ 10⁹

0 ≤ t_i ≤ 10⁹

v_i равно  − 1 или 1

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

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

В приведенном примере в начальный момент в БЛК находятся 4 частицы: частица e⁺ в точке  − 1, частица e⁻ в точке 0, частица e⁺ в точке 1 и частица e⁻ в точке 5.

В момент времени 0.5 первая частица e⁺ и первая частица e⁻ сталкиваются в точке с координатой  − 0.5 и исчезают. В момент времени 1 оставшиеся две частицы находятся в точках с координатами 2 и 4, соответственно. В момент времени 2 они сталкиваются в точке 3 и исчезают. Больше в БЛК частиц нет.

Примеры тестов

4
-1 1
0 -1
1 1
5 -1
4
0 1 2 3

4
2
0
0

Problem B81. Cut the band ≡

Statement

Young programmer Vasya came back home from an internship in a large IT company. As a souvenir, he brought back a band with a sequence of M natural numbers embroiled on it.

Vasya does not care much about numbers, so he wants to gift a band to a friend. However, each one of M Vasya's friends has exactly one number he strongly dislikes, and so would not want a band containing that number as a gift. All numbers disliked by Vasya's friends are different.

In order to still make a gift out of the band, Vasya wants to cut it in such a way, that every piece of the band could be given to at least one of his friends (several pieces may go to the same friend).

Your program must determine minimal number of cuts Vasya must perform to be able to give all pieces as gifts.

Input file format

First line of input file contains integer N — count of numbers on the band.

Second line of input file contains N integers a_i — a sequence of numbers on the band.

Third line of input file contains integer M — number of Vasya's friends.

Fourth line of input file contains M integers b_i — disliked number of i-th friend. All b_i are different.

Output file format

Output file must contain a single integer — minimal number of band cuts.

Constraints

1 ≤ N ≤ 10⁵

2 ≤ M ≤ 10⁵

1 ≤ a_i, b_i ≤ 10⁹

Sample tests

4
1 2 3 4
2
1 2

1

5
3 4 5 1 5
3
3 2 5

0

Задача B82. groupby group ≡

Условие

Необходимо написать программу, которая группирует студентов по их группам.

Формат входного файла

В первой строке входного файла дано число n — количество студентов. Далее следует n строк, в каждой из которых записаны группа и имя студента.

Группа и имя студента разделены символом табуляции.

Формат выходного файла

Выходной файл должен содержать список студентов, сгруппированный по группам. Для каждой группы необходимо вывести имя группы, а затем все имена студентов, которые принадлежат этой группе в алфавитном порядке, каждое в новой строке.

Сами группы следуют также в алфавитном порядке.

Ограничения

1 ≤ n ≤ 10⁵

Примеры тестов

3
M8103	Sidorov Sidor
M8888	Petrov Petr
M8103	Ivanov Ivan

M8103
Ivanov Ivan
Sidorov Sidor
M8888
Petrov Petr

Задача B84. Силовые поля ≡

Условие

В физико-биологической лаборатории исследуют воздействие излучения на растения при облучении через силовые поля.

Экспериментальная установка содержит квадратную платформу размером 10⁹ × 10⁹, заполненную плодородной почвой. Над платформой установлен источник излучения. Между источником излучения и платформой можно включать n силовых полей.

Генератор силовых полей установлен над точкой (0, 0). При этом i-е силовое поле представляет собой прямоугольник со сторонами, параллельными границам платформы и координатами двух противоположных углов (0, 0) и (x_i, y_i).

В эксперименте планируется изучать воздействие излучения на растения при облучении через k силовых полей. Из заданных n полей необходимо выбрать k полей для эксперимента. Ученые хотят выбрать силовые поля таким образом, чтобы площадь участка платформы, над которой находятся все k выбранных силовых полей, была максимальна.

Требуется написать программу, которая по заданным целым числам n, k и описанию n силовых полей определяет, какие k силовых полей необходимо выбрать для эксперимента, чтобы площадь участка, покрытого всеми k силовыми полями, была максимальна, и выводит площадь этого участка.

Формат входного файла

Первая строка входного файла содержит целые числа n и k — общее количество силовых полей и количество силовых полей, которые необходимо выбрать для эксперимента.

Последующие n строк содержат по два целых числа x_i, y_i — координаты дальнего от начала координат угла прямоугольного участка i-го силового поля.

Формат выходного файла

Требуется вывести одно целое число: максимальную площадь искомого участка.

Ограничения

1 ≤ k ≤ n ≤ 200 000, 1 ≤ x_i, y_i ≤ 10⁹

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

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

На рис. 1 показаны пять силовых полей, заданных во входном файле. Оптимальный способ выбрать из них три поля для эксперимента показан на рис. 2.

Рис 1. Силовые поля в примере описания входных данных.

Рис 2. Оптимальный выбор трех из пяти силовых полей в данном примере.

Примеры тестов

5 3
3 5
2 2
2 5
4 4
5 3

9

Задача C. Многократное суммирование ≡

Условие

Дан массив целых чисел a₁, a₂, ..., a_N и дано M команд типа "найти сумму чисел a_i для i от l до r".

Требуется написать программу, выполняющую данные команды.

Формат входного файла

Входной файл содержит целое число N, за которым следуют N целых чисел a_i.

Далее во входном файле содержится целое число M, за которым следуют M пар целых чисел l_j r_j.

Формат выходного файла

Выходной файл должен содержать M целых чисел — результаты выполнения команд.

Ограничения

1 ≤ N ≤ 1000000

1 ≤ M ≤ 1000000

 − 1000 ≤ a_i ≤ 1000

1 ≤ l_j ≤ r_j ≤ N

Примеры тестов

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

6 14 12

Задача D1. Финальный босс ≡

Условие

Мальчик Коля дошёл в своей любимой игре до финального босса.

С помощью игровой подсказки Коля узнал механику босса.

• Изначально у босса H единиц здоровье.
• Победить босса нужно за M минут или меньше.
• За минуту Коля наносит D урона.
• Каждую минуту (после того как Коля нанёс D урона) здоровье босса увеличивается в 1,1 раза (знаки после запятой убираются) и ещё прибавляется 10 единиц здоровья.

Необходимо узнать какой минимальный урон Коле нужно наносить по финальному боссу, чтоб его одолеть за M минут.

Формат входного файла

Входной файла содержит целые числа H M.

Формат выходного файла

Выходной файл должен содержать единственное целое число — минимальный подходящий урон в минуту.

Ограничения

1 ≤ H ≤ 10⁹; 1 ≤ M ≤ 10⁴

Примеры тестов

100 5

32

30 4

16

Задача D2. Вырубка леса ≡

Условие

Фермер Николай нанял двух лесорубов: Дмитрия и Федора, чтобы вырубить лес, на месте которого должно быть кукурузное поле. В лесу растут X деревьев.

Дмитрий срубает по A деревьев в день, но каждый K-й день он отдыхает и не срубает ни одного дерева. Таким образом, Дмитрий отдыхает в K-й, 2K-й, 3K-й день, и т.д.

Федор срубает по B деревьев в день, но каждый M-й день он отдыхает и не срубает ни одного дерева. Таким образом, Федор отдыхает в M-й, 2M-й, 3M-й день, и т.д.

Лесорубы работают параллельно и, таким образом, в дни, когда никто из них не отдыхает, они срубают A + B деревьев, в дни, когда отдыхает только Федор — A деревьев, а в дни, когда отдыхает только Дмитрий — B деревьев. В дни, когда оба лесоруба отдыхают, ни одно дерево не срубается.

Фермер Николай хочет понять, за сколько дней лесорубы срубят все деревья, и он сможет засеять кукурузное поле.

Требуется написать программу, которая по заданным целым числам A, K, B, M и X определяет, за сколько дней все деревья в лесу будут вырублены.

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

В приведенном примере лесорубы вырубают 25 деревьев за 7 дней следующим образом:

• 1-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 5 деревьев;
• 2-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 10 деревьев;
• 3-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 12 деревьев;
• 4-й день: Дмитрий отдыхает, Федор срубает 3 дерева, итого 15 деревьев;
• 5-й день: Дмитрий срубает 2 дерева, Федор срубает 3 дерева, итого 20 деревьев;
• 6-й день: Дмитрий срубает 2 дерева, Федор отдыхает, итого 22 дерева;
• 7-й день: Дмитрий срубает 2 дерева, Федор срубает оставшееся 1 дерево, итого все 25 деревьев срублены.

Внимание! Тест из примера не подходит под ограничения для подзадач 2 и 3, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест даже, если оно рассчитано на решение только каких-либо из подзадач 2 и 3.

Система оценивания и описание подзадач

Подзадача 1 (32 баллов)

1 ≤ X ≤ 1000, 1 ≤ A, B ≤ 1000, 2 ≤ K, M ≤ 1000.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 2 (10 баллов)

1 ≤ X ≤ 10¹⁸; X < K; X < M.

При решении этой подзадачи можно считать, что лесорубы не отдыхают. Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 3 (10 баллов)

1 ≤ X ≤ 10¹⁸.

Дополнительно к приведенным ограничениям выполняется условие K = M. Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 4 (48 баллов)

1 ≤ X ≤ 10¹⁸, 1 ≤ A, B ≤ 10⁹, 2 ≤ K, M ≤ 10¹⁸.

В этой подзадаче 16 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Формат входного файла

Входной файл содержит пять целых чисел, разделенных пробелами: A, K, B, M и X.

Формат выходного файла

Выходной файл должен содержать одно целое число — искомое количество дней.

Ограничения

1 ≤ A, B ≤ 10⁹, 2 ≤ K, M ≤ 10¹⁸, 1 ≤ X ≤ 10¹⁸

Примеры тестов

2 4 3 3 25

7

Задача D3. Дипломы ≡

Условие

Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось N дипломов, причем, как оказалось, все они имели одинаковые размеры: W — в ширину и H — в высоту.

Сейчас Петя учится в одном из лучших российских университетов и живет в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить ее к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещен строго в прямоугольнике размером W на H. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.

Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.

Система оценивания

Решения, правильно работающие только при W, H, N ≤ 1000, будут оцениваться в 40 баллов.

Формат входного файла

Входной файл содержит три целых числа: W, H, N

Формат выходного файла

В выходной файл необходимо вывести ответ на поставленную задачу.

Ограничения

1 ≤ W, H, N ≤ 10⁹

Примеры тестов

2 3 10

9

Задача E1. Сумма ≡

Условие

Дан массив из N элементов, нужно научиться находить сумму чисел на отрезке.

Формат входного файла

Первая строка содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы

• A i x — присвоить i-му элементу массива значение x (1 ≤ i ≤ n, 0 ≤ x ≤ 10⁹)
• Q l r — найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ n)

Формат выходного файла

На каждый запрос вида Q l r нужно вывести единственное число — сумму на отрезке.

Ограничения

Примеры тестов

5 9
A 2 2
A 3 1
A 4 2
Q 1 1
Q 2 2
Q 3 3
Q 4 4
Q 5 5
Q 1 5

0
2
1
2
0
5

Задача E2. Дипломы 2.0 ≡

Условие

Сегодня в ДВФУ состоится традиционное вручение дипломов выпускникам института математики и компьютерных наук. Каждый год это особенное событие и большой праздник, как для выпускников, так и для сотрудников факультета, своеобразное подведение итогов совместного многолетнего труда.

В этом году из института выпускается n студентов. Еще давным-давно, при поступлении, каждому студенты был выдан порядковый номер, который зависел от их места в конкурсном списке по результатам вступительных испытаний. Те, кто были выше в конкурсном списке, имели более низкий порядковый номер. То есть, если человек сдал вступительные лучше всех, то имел 1-й порядковый номер, кто сдал чуть хуже этого человека, но лучше всех остальных — 2-й, и так далее. Хоть это и было очень давно, эти номера закрепились за ними до конца их учебных дней.

В качестве введения новшества, институт решил распечатать конверты с этими порядковыми номерами и запаковать дипломы выпускников в принадлежащие их номеру конверты. Они сложили все конверты в стеклянный "бокс", расположив их слева направо по возрастанию. Бокс имел два отверстия для того, чтобы доставать дипломы: слева и справа.

Во время начала церемонии декану вручили список, по которому он должен выдавать дипломы. i-й по счету диплом должен быть выдан студенту под порядковым номером a_i. Так как укладывали все дипломы до получения этого списка, расположение их не такое, как должно быть. Они решили действовать по следующей тактике: вытаскивать дипломы по-очереди до того момента, пока не достанут нужный, и складывать все выложенные дипломы в том же порядке, как они и лежали. Т.е. если нужно достать диплом под номером 4, то сначала необходимо выложить дипломы 6 и 5 (или 1, 2 и 3, так как бокс имеет отверстия с двух сторон), а затем сложить их обратно в том же порядке. После того, как диплом выдан, он пропадает из бокса. На каждую операцию взятия и складывания дипломом затрачивается одно действие. Такая тактика, кстати, выбрана не просто так, они хотят ускорить выдачу дипломов и при этом не запутаться.

Вам дан список порядка выдачи дипломов. Определите, за какое наименьшее количество действий возможно выдать все дипломы, следуя данной тактике.

Формат входных данных

В первой строке входных данных записано натуральное число n — количество студентов.

Во второй строке записано n натуральных чисел a_i — порядок выдачи дипломов студентам по их порядковым номерам. Гарантируется, что каждое a_i уникальное.

Формат выходных данных

Выведите минимально возможное количество действий, за которое можно выдать все дипломы, следуя данной тактике.

Ограничения

1 ≤ n ≤ 2 ⋅ 10⁵

1 ≤ a_i ≤ n

Примеры тестов

6
4 3 5 2 1 6

18

2
2 1

2

5
1 2 3 4 5

5

6
5 3 6 2 4 1

14

Задача E3. RMQ ≡

Условие

• «max l r». Найти максимум в массиве a от l-ой ячейки до r-ой включительно.
• «add l r v». Прибавить значение v к каждой ячейке a[] от l-ой до r-ой включительно.

Формат входного файла

Первая строка содержит два целых числа n и q (1 ≤ n, q ≤ 10⁵) — длина массива и число запросов соответственно.

Вторая строка содержит n целых чисел a₁, …, a_n (|a_i| ≤ 10⁵), задающих соответствующие значения массива.

Следующие q строк содержат запросы.

В зависимости от типа запрос может иметь вид либо «max l r», либо «add l r v».

1 ≤ l ≤ r ≤ n, |v| ≤ 10⁵.

Формат выходного файла

Для каждого запроса вида «max l r» требуется в отдельной строке выдать значение соответствующего максимума.

Ограничения

Примеры тестов

5 3
1 2 3 4 -5
max 1 3
add 1 2 5
max 1 3

3
7

Задача E4. Сумма+присвоение на отрезке ≡

Условие

Формат входного файла

Первая строка входного файла содержит два целых числа N и K — число чисел в массиве и количество запросов. (1 ≤ N ≤ 100 000), (0 ≤ K ≤ 100 000). Следующие K строк содержат запросы:

• A l r x

   — присвоить элементам массива с позициями от l до r значение x (1 ≤ l ≤ r ≤ N, 0 ≤ x ≤ 10⁹)

• Q l r

   — найти сумму чисел в массиве на позициях от l до r. (1 ≤ l ≤ r ≤ N)

Изначально массив заполнен нулями.

Формат выходного файла

На каждый запрос вида

Q l r

Ограничения

Примеры тестов

5 9
A 2 3 2
A 3 5 1
A 4 5 2
Q 1 3
Q 2 2
Q 3 4
Q 4 5
Q 5 5
Q 1 5

3
2
3
4
2
7

Задача E5. Плакаты ≡

Условие

Друзья готовятся встретить национальную команду, возвращающуюся с международной олимпиады по информатике. Для этого они подготовили множество красочных плакатов. Осталось только продумать детали поздравления.

Для того, чтобы приветствовать команду, n друзей встанут в круг. Пронумеруем их от 1 до n в порядке их расположения по кругу. Таким образом, для всех i от 1 до n − 1 друзья с номерами i и i + 1 стоят рядом, также рядом стоят друзья с номерами n и 1. У каждого из друзей есть плакат. Каждый плакат характеризуется своей красочностью — целым неотрицательным числом. Плакат у друга с номером i имеет красочность a_i.

Когда поздравление начнётся, некоторые из друзей поднимут свои плакаты и будут показывать их команде. Для того, чтобы члены команды не растерялись и смогли рассмотреть все плакаты, не должно быть четырёх или более стоящих подряд друзей с поднятым плакатом.

Друзья планируют изменять плакаты в процессе встречи. Всего будет внесено q изменений в плакаты. После i-го из них плакат друга с номером p_i будет иметь красочность v_i. После каждого из изменений друзья хотят определить, какую максимальную суммарную красочность могут иметь поднятые плакаты, если нельзя нарушать установленное ограничение.

Требуется написать программу, которая по заданной начальной красочности плакатов и последовательности их изменений определяет в начале, а также после каждого изменения, какой максимальной суммарной красочности поднятых плакатов можно добиться, не нарушая условие, что поднято не более трёх плакатов подряд.

Формат входных данных

Первая строка ввода содержит целое число n (4 ≤ n ≤ 40 000) — количество друзей.

Вторая строка содержит n целых чисел a_i (0 ≤ a_i ≤ 10⁹) — исходные значения красочности плакатов у друзей.

Третья строка содержит одно целое число q (0 ≤ q ≤ 40 000) — количество изменений плакатов, которые вносили друзья.

Каждая из следующих q строк содержит два целых числа p_i и v_i (1 ≤ p_i ≤ n; 0 ≤ v_i ≤ 10⁹) — номер друга, плакат которого изменился, и новая красочность этого плаката.

Формат выходных данных

Выведите q + 1 число. Перед первым изменением, а также после каждого изменения плакатов выведите одно целое число — максимальное суммарное значение красочности поднятых плакатов, если нельзя поднимать больше трёх плакатов подряд.

Ограничения

4 ≤ n ≤ 40 000

0 ≤ a_i ≤ 10⁹

0 ≤ q ≤ 40 000

1 ≤ p_i ≤ n; 0 ≤ v_i ≤ 10⁹

Система оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Пояснения

Перед первым изменением плакаты следует поднять друзьям с номерами 2, 4, 5, 6. Суммарная красочность поднятых плакатов будет равняться 17.

После первого изменения плакат друга с номером 6 имеет красочность 0. Теперь плакаты следует поднять друзьям с номерами 1, 3, 4, 5. Суммарная красочность будет равняться 13.

После второго изменения плакат друга с номером 2 имеет красочность 5. Плакаты следует поднять друзьям с номерами 1, 2, 4, 5. Суммарная красочность будет равняться 15.

Примеры тестов

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

17
13
15

Задача F1. Питание программистов ≡

Условие

Оргкомитет сборов по программированию знает, что важно организовать правильное питание участников. Еда должна быть вкусной, а блюда — разнообразными. Поэтому разработку меню доверили повару тёте Вале.

Тётя Валя умеет готовить несколько разных блюд. Она использует для их обозначения маленькие английские буквы. Всего в течение сборов будет n приёмов пищи. Тётя Валя составила черновик меню — строку s, состоящую из n маленьких английских букв. Символ s_i обозначает блюдо, которое она запланировала для i-го приёма пищи.

Черновик меню полностью сбалансирован по всем питательным компонентам, но тётя Валя не особо заботилась о разнообразии.

Помогите тёте Вале сделать меню наиболее разнообразным. Для этого нужно переставить блюда в меню таким образом, чтобы минимальное расстояние между одинаковыми блюдами было как можно больше.

Если существует несколько решений, выведите любое из них.

Формат входного файла

Входной файл содержит строку s, состоящую из маленьких букв английского алфавита — черновик меню.

Формат выходного файла

Выходной файл должен содержать единственную строку — окончательный вариант меню.

Ограничения

1 ≤ n ≤ 100000;

Примеры тестов

olmkoo

moloko

Задача F2. Хоттаб-share/2 ≡

Условие

Прожив 1000 лет, Гассан Абдуррахман ибн Хоттаб узнал, что из интернета можно скачивать файлы. Решив помочь другим пользователям, он сотворил собственный сервер с файлами. Поскольку сервер Хоттаба волшебный, любой файл скачивается с него мгновенно. Однако, после скачивания файла размером S мегабайт скачавший его компьютер отключается от сервера на S секунд.

В распоряжении шушанчиков имеется один компьютер, подключённый к интернету. Им требуется скачать N файлов, i-й файл размером s_i мегабайт. Шушанчики просят Вас рассчитать минимальное время, за которое можно скачать эти файлы с сервера Хоттабыча.

Формат входного файла

Во входном файле содержится число N — количество файлов, за которым следуют N чисел s_i — размеры файлов в мегабайтах.

Формат выходного файла

В выходном файле должно содержаться единственное число — минимальное время скачивания всех файлов в секундах.

Ограничения

1 ≤ N ≤ 1000

1 ≤ s_i ≤ 1000

Все числа во входном файле целые

Примеры тестов

2
13 17

13

5
13 19 17 14 19

63

Задача F3. Текст ≡

Условие

Давным-давно, в далекой-далекой галактике учились в одной школе два закадычных друга — Вася и Петя. Они были верными товарищами, не раз выручавшими друг друга в трудную минуту из самых безвыходных ситуаций. Однако речь сейчас пойдет не об этом, а о редчайшем случае — ссоре между двумя героями нашего повествования.

В конце седьмого класса Вася увлекся программированием и написал свой текстовый редактор. Естественно, Петя тут же захотел его испытать. Несложно представить насколько велико было его разочарование, когда обнаружилось, что Васина программа корректно работает только при использовании экрана с тем же разрешением, как и у него дома. Вася оправдывал это тем, что оптимальный вывод текста на экран — штука сложная, поэтому универсальным образом сделать это невозможно. Петя же заявил, что хоть программист он и никудышный, но легко решит эту задачу.

К сожалению, программирует Петя действительно из рук вон плохо, поэтому он просит вас помочь ему в написании решения.

На вход дан текст. Назовем словом последовательность символов, ограниченную пробелами, началом или концом текста. Обратите внимание, что в данной задаче знаки препинания считаются частью слова. Требуется разбить текст на строки так, чтобы длина каждой из них была не более k символов, при этом их общее количество было минимальным. Порядок слов и сами слова менять запрещено.

Формат входного файла

Первая строка входного файла содержит натуральное число k — максимально допустимая длина строки.

Вторая строка входного файла содержит текст, который необходимо вывести. Текст состоит из латинских букв, цифр, пробелов и символов "," (запятая), "." (точка), "!" (восклицательный знак) и "?" (вопросительный знак).

Формат выходного файла

Выведите заданный во входном файле текст так, чтобы длина каждой строки была не более k символов, а количество строк было минимально возможным. Гарантируется, что задача имеет решение. В случае если решение не единственно, выведите любое из них. Слова в выходном файле должны быть отделены друг от друга пробелами и/или переводами строк.

Ограничения

1 ≤ k ≤ 100. Размер входного файла не превышает 50000 байтов.

Примеры тестов

22
This     is a sample text!

This is a sample text!

12
This     is a sample text!

This is a
sample text!

Задача F4. Арифметическая прогрессия ≡

Условие

Петя очень любит арифметические прогрессии. Однажды он написал на бумаге числовую последовательность, но, к сожалению, эта последовательность не оказалась арифметической прогрессией.

Чтобы исправить эту ситуацию, Петя решил вычеркнуть некоторые числа, чтобы полученная в результате вычёркивания последовательность оказалась арифметической прогрессией. При этом Петя хочет вычеркнуть как можно меньше чисел.

Напишите программу, принимающую на вход последовательность чисел и вычисляющую, какое наименьшее количество чисел нужно из неё вычеркнуть, чтобы оставшаяся последовательность оказалась арифметической прогрессией.

Формат входного файла

Входной файл содержит целое число N — количество чисел, за которым следуют N целых чисел a_i.

Формат выходного файла

Выходной файл должен содержать целое число M — количество чисел, которые останутся после вычёркивания (при этом количество вычеркнутых чисел должно быть минимальным).

Далее должны следовать M целых чисел — номера чисел, которые останутся после вычёркивания, перечисленные в порядке возрастания.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 100

1 ≤ a_i ≤ 10⁶

Примеры тестов

7
1 3 4 2 7 8 10

4
1 3 5 7

Задача F5. Мёд и справедливость ≡

Условие

Две пчелы собирают пыльцу с N цветков, расположенных в ряд. Цветок номер i содержит a_i микрограмм пыльцы.

Пчёлы договорились, что первая пчела будет собирать пыльцу с цветков на участке от L до M включительно, а вторая  — от M + 1 до R включительно (L ≤ M < R). Чтобы ни одной из пчёл не было обидно, сумма запасов пыльцы на первом и втором участках пчёл должны совпадать.

Требуется написать программу, которая найдёт подходящие участки с наибольшим возможным количеством пыльцы.

Формат входных данных

Входные данные содержат целое число N, за которым следует N чисел a_i.

Формат выходных данных

Выходные данные должны содержать целые числа L M R — границы участков. Если оптимальных решений несколько, выведите решение с наименьшим значением L. Если решения не существует, выведите единственное число  − 1.

Ограничения

2 ≤ N ≤ 10000

1 ≤ a_i ≤ 10⁵

Примеры тестов

3
1 1 2

1 2 3

2
2 5

-1

Задача G1. Длинный дом ≡

Условие

Две подруги, Нина и Марина, живут квартирах n и m в одном подъезде самого длинного дома в мире. Каким может быть наибольший номер этого подъезда? Количество квартир в каждом подъезде одинаково.

Формат входных данных

Две строки входных данных содержит два натуральных числа n и m.

Формат выходных данных

Выведите одно натуральное число — ответ на вопрос задачи.

Ограничения

1 ≤ m < n ≤ 10⁹

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

В примере дано n = 52 и m = 41. Эти квартиры могут находиться в первом подъезде (если в одном подъезде квартир не меньше, чем 52).

Эти квартиры могут находиться во втором подъезде (если в одном подъезде квартир не меньше, чем 26 и не больше, чем 40).

Эти квартиры могут находиться в третьем подъезде (если в одном подъезде квартир не меньше, чем 18 и не больше, чем 20).

Эти квартиры могут находиться в четвертом подъезде (если в одном подъезде ровно 13 квартир).

Эти квартиры не могут находиться в подъезде с номером большим, чем 4. Ответ на вопрос задачи — 4.

Примеры тестов

52
41

4

Problem G2. Emitting light ≡

Statement

Young physicist Masha studies lasers. Masha wants to create a simplest 2-dimensional waveguide, consisting of two very long parallel mirrors, one coinciding with the Ox axis, and another located h millimeters above the first.

Masha's laser is located at coordinates (0, y) and emits light in direction (1,  − 1). Masha wants to hit a target located at coordinates (x_t, y_t) by choosing a good value for h. All coordinates are in millimeters.

Note that laser itself must fit into the waveguide, so h ≥ y. Both mirrors and laser are perfect, so light is always fully reflected at 45 degrees angle.

Input file format

Input file contains three integers y x_t y_t — coordinates of laser and target.

Output file format

Output file must contain a single integer — value of h. If there are several solutions, output the smallest one. If there are no solutions, output  − 1.

Constraints

1 ≤ y, x_t, y_t ≤ 10⁹

Sample tests

5 2 2

-1

5 6 1

5

2 16 2

2

Задача G3. Загадочное уравнение ≡

Условие

Маленький Вася очень любит уравнения. Однажды ему на глаза попалось уравнение x + y + xy = n. Вася захотел узнать количество пар целых неотрицательных чисел x и y, которые являются решениями этого уравнения.

Так как Вася еще маленький, то он попросил вас посчитать это количество.

Формат входного файла

В единственной строке входного файла дано число n (0 ≤ n ≤ 10⁹).

Формат выходного файла

В единственную строку выходного файла выведите ответ на задачу.

Примеры тестов

5

4

8

3

Задача G4. Потерянное число ≡

Условие

Игорь изучал арифметическую прогрессию и чтобы лучше запомнить как она выглядит, распечатал на листочках бумаги числа и разложил из них на полу арифметическую прогрессию. Поднялся ветер и все листы бумаги улетели в разные стороны. Когда Игорь собрал их, оказалось, что не хватает одного листа и выразить из них арифметическую прогрессию не получается. Необходимо найти число, которые было написано на пропавшем листе.

Гарантируется, что пропавшее целое число не было первым или последним в арифметической прогрессии Игоря.

Формат входного файла

В первой строке входные данные содержат число N - количество листков с числами, которое собрал Игорь.

В следующей строке содержатся N чисел a_i разделенные пробелами

Формат выходного файла

Выходные данные должны содержать одно целое число.

Ограничения

2 ≤ N ≤ 10⁶

0 ≤ a_i ≤ 10⁷

Примеры тестов

4
4 6 10 2

8

Problem G5. Fractional multiplication ≡

Statement

There is a set of N rational fractions, each is represented by corresponding numerator A_i and denominator B_i.

You must write a program that outputs:

• 0 — if the product of all fractions is either 1 or a prime;
• 1 — if it is integer non-prime;
• 2 — if it is a fractional number.

Input format

Input contains integer N, followed by N pairs of integers (A_i, B_i).

Output format

Output must contain a single integer — answer to the problem.

Constraints

1 ≤ N ≤ 200, 1 ≤ (A_i, B_i) < 2³²

Sample tests

1
35880 17940

0

1
76824 12804

1

1
94803 11573

2

Задача G6. Полные квадраты ≡

Условие

С целью поиска закономерностей иногда полезно сгенерировать длинную последовательность по определенным правилам. Известно, например, что последовательность 0, 0 + 1, 0 + 1 + 3, 0 + 1 + 3 + 5, …, 0 + 1 + 3 + …  + (2n − 1), …, составленная из сумм нескольких первых нечетных натуральных чисел, состоит из квадратов целых чисел: 0, 1, 4, 9, …, n²,….

Обобщим эту последовательность следующим образом: будем использовать вместо начального значения не ноль, а число k. Получим последовательность: k, k + 1, k + 1 + 3, k + 1 + 3 + 5, …, k + 1 + 3 + …  + (2n − 1), …. В отличие от случая k = 0, в этой последовательности могут встречаться не только полные квадраты. Необходимо найти минимальное целое неотрицательное число, квадрат которого встречается в этой последовательности.

Требуется написать программу, которая по заданному целому числу k определяет, квадрат какого минимального неотрицательного целого числа встречается в описанной последовательности, либо выясняет, что в ней вообще не встречается полных квадратов.

Формат входных данных

В единственной строке содержится целое число k — начальное число в последовательности. Обратите внимание, что для считывания и хранения такого большого числа необходимо использовать 64-битный тип данных.

Формат выходных данных

Выведите минимальное неотрицательное целое число, квадрат которого встречается в описанной последовательности. Если в последовательности не встречается квадратов целых чисел, выведите none.

Ограничения

 − 10¹² ≤ k ≤ 10¹²

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

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

В первом примере каждое число последовательности является полным квадратом. Минимальный из них — 0, 0² = 0.

Во втором примере последовательность начинается так:  − 5,  − 4,  − 1, 4, 11, 20,…. Минимальное неотрицательное целое число, квадрат которого встречается в последовательности — 2, 2² = 4.

В третьем примере последовательность начинается так: 2, 3, 6, 11, 18, …. В ней нет квадратов целых чисел.

Примеры тестов

0

0

-5

2

2

none

Задача G7. Большая распродажа ≡

Условие

В магазине "Программист-спортсмен" большая распродажа! В преддверии поступления товаров нового сезона, нужно срочно освободить полки и витрины, продавая прошлогодние коллекции по бросовым ценам. К сожалению, установить произвольную цену на товар нельзя, в соответствии с антимонопольным законом на распродажу распространяются следующие условия:

1) На товар можно установить любую скидку (от 1 до 99 процентов) по сравнению с ценой товара в предыдущий день.

2) И скидка, и новая стоимость товара должны являться натуральными числами.

Например, если товар стоит 20 рублей, на него можно установить скидку 25% и на следующий день этот товар будет продаваться по 15 рублей. А вот скидку в 30% установить нельзя — новая цена будет выражаться дробным числом рублей.

Молодой программист Тимофей каждый день после работы заходит в магазин и скупает все товары, которые сегодня стоят 1 рубль. Как скоро хозяину магазина удастся снизить стоимость товара с n рублей до 1 рубля?

Формат входных данных

Единственная строка входных данных содержит натуральное число n — начальная стоимость товара в рублях. Гарантируется, что это значение таково, что существует последовательность корректных скидок, снижающих стоимость товара до 1 рубля.

Формат выходных данных

Выведите одно натуральное число — наименьшее количество дней, необходимых для максимального снижения стоимости товара.

Ограничения

2 ≤ n ≤ 10¹⁸

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

В примере дана начальная стоимость товара 125 рублей. В первый день на него устанавливается скидка 96% и товар продается по цене 5 рублей. Во второй день скидка составит 80% и вечером товар будет куплен Тимофеем за 1 рубль.

Примеры тестов

125

2

Problem G8. Current year problem ≡

Statement

Find the smallest positive integer which is divisible by n and starts from digits 2021 in decimal notation.

Input format

Input contains a single integer n — the divisor of the required number.

Output format

Output a single integer — the answer.

Constraints

1 ≤ n ≤ 10¹²

Sample tests

2022

20211912

Problem G9. Arithmetic pairs ≡

Statement

Your program must calculate total number of such pairs of integers (p, n) that p ≥ 1, n > 1 и A ≤ pⁿ ≤ B.

Input file format

Input file contains two integers A and B.

Output file format

Output file must contain a single integer — number of pairs.

Constraints

2 ≤ A ≤ B < 2⁶³

Sample tests

10 100

13

37 48

0

Задача H1. Марфа Геннадьевна в столовой ≡

Условие

Однажды Марфа Геннадьевна пришла в столовую. В меню было N блюд. Блюдо с номером i стоит c_i рублей. Для каждого блюда известен также коэффициент сытости блюда — a_i.

Марфа Геннадьевна знает, что для того, чтобы наесться, нужно, чтобы сумма коэффициентов сытости съеденных блюд была не меньше A.

Какие блюда нужно взять в столовой, чтобы наесться и потратить как можно меньше денег? Обратите внимание, что Марфа Геннадьевна может взять более одной порции блюда (любое целое неотрицательное число порций).

Формат входного файла

Входной файл содержит целые числа N A.

Далее следуют N пар целых чисел c_i a_i.

Формат выходного файла

Выходной файл должен содержать минимальную сумму денег, которую нужно потратить, чтобы наесться.

Ограничения

1 ≤ N ≤ 100

1 ≤ A ≤ 1000

1 ≤ c_i ≤ 500

1 ≤ a_i ≤ 100

Примеры тестов

3 10
2 1
5 4
6 6

11

4 32
1 8
2 4
3 2
4 1

4

Problem H2. Hall of water life ≡

Statement

The main hall of the Nearsea Institute of Unspecified Underwater Studies has a shape of a long corridor. Along the corridor, there are N aquariums exhibiting various sea creatures. Aquariums are located at distances x₁, …, x_N from the hall entrance (x_i < x_i + 1).

The institute has recently got a new director, who decided that the aquarium maintenance is too costly, and issued an order to remove M (0 ≤ M ≤ N − 2) aquariums.

To minimize the disruption to the looks of the hall, it was decided that:

1. the first and the last aquariums should be left in their places;
2. the maximum distance between the adjacent aquariums must be as small as possible.

Your program must select aquariums for removal in such a way that the above conditions are satisfied.

Input file format

Input file contains integers N M followed by N integers x_i.

Output file format

Output file should contain a single integer — the smallest possible maximum distance.

Constraints

Sample tests

5 2
1 2 3 4 5

2

4 1
10 21 30 40

19

Задача H3. Рассадка пассажиров ≡

Условие

Илон Маск закончил создание транспорта будущего — Hyperloop. Hyperloop — расположенный на опорах надземный трубопровод, внутри которого с высокой скоростью в одном направлении перемещаются одиночные транспортные капсулы. Пассажирский вариант предполагает n рядов по одному сиденью. Однако из-за конструктивных недостатков люди не могут сидеть на двух подряд идущих рядах. Поэтому, когда продаётся билет с номером места a_i из продажи исчезает сам этот билет, и два соседних с ним билета.