Задача A. Кубики ≡

Условие

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

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

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

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

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

Ограничения

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

6 2
1 1 2 2 1 1

3 5 6

Задача B. Сломанный арифмометр с нетривиальным принципом работы ≡

Условие

Один из известных коллекционеров недавно приобрел на аукционе старый арифмометр.

Арифмометр состоит из двух циферблатов, набора кнопок, которые можно нажать, и ручек, которые можно крутить. На первом циферблате показывается число от 0000 до 9999. К сожалению, арифмометр длительное время не ремонтировали, поэтому работают только кнопка, увеличивающая значение числа на 1, и ручка, за один поворот которой можно увеличить на 1 группу одинаковых разрядов числа из одного или более штук. Если в числе несколько групп одинаковых разрядов, то имеется возможность выбрать любую. Например, возможна следующая последовательность действий 1234 ↦ 1244 ↦ 2244 ↦ 3344 ↦ 4444 ↦ 4445 ↦ 5555. На втором циферблате отображается набранная сумма с учетом знака. При этом число на втором циферблате меняется согласно следующим правилам:

1. Одно нажатие на кнопку или один поворот ручки считается одним действием.
2. Если число произведенных действий нечетно, то к числу на втором циферблате будет прибавлен результат действия на первом.
3. Если число произведенных действий четно, то от числа на втором циферблате отнимается результат действия на первом.

Например: если A = 1234, то после нажатия кнопки на обоих циферблатах будет установлено число 1235. После еще одного нажатия кнопки на первом циферблате будет 1236, а на втором — −1.

Коллекционер хочет узнать, какое наименьшее число он сможет установить на втором циферблате, произведя ровно K действий.

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

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

Ограничения

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

1130 4

-2220

0023 1

24

1234 0

0

Задача C. Финишные позиции ≡

Условие

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

Требуется написать программу, которая по заданному списку машин определит их финишные позиции.

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

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

Во входном файле содержится число N — количество элементов списка.

Далее следуют N чисел, задающие список.

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

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

Ограничения

1 ≤ N ≤ 10⁶

Номера машин являются целыми неотрицательными числами, не превосходящими 10⁹

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

3
5 1 10

5 1 10

8
4 7 8 7 4 8 7 4

7 4 8

16
17 88 39 88 17 39 88 17 88 17 39 39 17 39 17 222222222

17 39 88 222222222

Задача D. 2-3 Дерево ≡

Условие

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

• корень и каждая внутренняя вершина имеет либо 2 либо 3 ребенка;
• глубина всех листьев одна и та же.

Единственное исключение - это когда дерево содержит ровно одну вершину. В этом случае корень дерева является и листом, и поэтому не имеет детей. Основная суть приведенных свойств в том, что дерево с l листьями имеет высоту O(log l).

Вообще говоря, может существовать несколько 2-3 деревьев с l листьями. Например, на следующем рисунке показаны два возможных дерева с 6 листьями.

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

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

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

Ограничения

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

6 1000000000

2

7 1000000000

3

Задача E. Спички ≡

Условие

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

Напишите программу, которая по количеству квадратов N, которые необходимо составить, находит минимальное необходимое для этого количество спичек.

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

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

Ограничения

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

4

12