Задача A. Полное прохождение 2 ≡

Условие

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

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

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

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

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

Уровни игры представлены на следующем изображении (черным цветом обозначены уровни, на которых можно сохраняться):

Файл с изображениями уровней можно скачать ЗДЕСЬ.

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

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

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

В качестве решения принимается текстовый файл, содержащий ответы к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

На каждый тест должен быть дан ответ (иначе есть риск неверной проверки). Если вы не знаете ответ на какой-то тест, то следует написать в выходном файле "0" (без кавычек).

Баллы начисляются пропорционально количеству правильных ответов в выходном файле.

По запросу сообщается количество набранных баллов.

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

№	Входные данные	Выходные данные
1		11 6

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

В первом примере в первое прохождение можно пройти уровни (1, 3, 6), во второе прохождение — (1, 3, 7), в третье прохождение (1, 2, 4), в четвертое прохождение — (2, 5). Последнее прохождение можно начать со 2-о эпизода, так как он уже был пройден и на нём можно было сохраниться. Всего для полного прохождения пришлось пройти 11 эпизодов.

Задача B. Мытьё посуды 2 ≡

Условие

Во время Войны Бесконечности Доктор Стрэндж стал просматривать варианты возможного будущего. Из четырнадцати миллионов победными оказались лишь Q вариантов, и во всех после победы Мстители устроили большую вечеринку.

В i-м варианте будущего на вечеринку придёт N_i Мстителей. Не волнуйтесь, остальные герои не погибли (это же Марвел), они уже успели отправиться на своё сольное спасение мира. Но новая напасть оказалась не за горами, и, возможно, она пострашнее Таноса — героям необходимо решить, кто пойдёт мыть посуду. К сожалению, перчатка бесконечности была уничтожена, поэтому помыть всю (или хотя бы половину) посуды щелчком пальцев не получится. Сложно только представить, к какой гражданской войне могла привести эта ситуация, если бы только один из героев не вспомнил про народный метод решения подобных проблем — считалочку.

Все герои встали в круг, они пронумерованы от 1 до N_i, 1 и N_i герой стоят рядом. После они начали отсчитывать M_i человек (енотов, деревьев и т.д.) от первого героя. Герой, на котором закончился счет, покидал круг, и счет начинался по новой, от следующего героя в круге. И так до тех пор, пока в круге не остался бы один герой — ему-то и придётся спасать этот мир (или по крайней мере эту вечеринку) от грязной посуды.

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

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

Первая строка содержит одно целое число Q — количество вариантов будущего.

Далее следует Q строк, i-я из которых содержит по два целых числа N_i и M_i — количество героев, которые пришли на вечеринку в i-м варианте будущего, и количество Мстителей, которое будет отсчитываться по кругу.

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

Второй пример соответствует тестам, которые будут оцениваться.

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

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

Ограничения

1 ≤ Q ≤ 15

1 ≤ N ≤ 10²

1 ≤ M ≤ 10²

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

В качестве решения принимается как программа, так и текстовый файл, содержащий ответы к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

На каждый тест должен быть дан ответ (иначе есть риск неверной проверки). Если вы не знаете ответ на какой-то тест, то следует написать в выходном файле "0" (без кавычек).

Баллы начисляются пропорционально количеству правильных ответов в выходном файле.

По запросу сообщается количество набранных баллов.

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

В первом примере в первом варианте будущего герои будут покидать круг в следующем порядке: 3, 1, 5, 2.

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

3
5 3
6 3
100 33

4
1
48

15
5 9
8 8
21 15
25 2
75 25
1 99
4 94
9 6
20 11
98 1
75 25
88 88
90 45
100 11
100 100

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Задача C. Крестьянин и чёрт ≡

Условие

Встретил крестьянин чёрта, и тот говорит ему: «Видишь мост через эту реку? Стоит тебе только перейти через этот мост — у тебя будет втрое больше денег, чем есть. Перейдёшь назад, опять станет втрое больше, чем было. И так каждый раз, как ты будешь переходить через мост».

 — Ой ли? — говорит крестьянин.

 — Верное слово! — уверяет чёрт. — Только чур, уговор! За то, что я тебе утраиваю деньги, ты, каждый раз перейдя через мост, будешь отдавать мне по X копеек. Иначе не согласен.

 — Ну, что же, это не беда! — говорит крестьянин. — Раз деньги будут утраиваться, так отчего же тебе X копеек каждый раз не дать?

Перешёл крестьянин через мост, посчитал деньги — и вправду, стало втрое больше, чем было. Отсчитал X копеек, бросил чёрту, перешёл снова.. После N-го перехода по мосту отсчитал крестьянин в N-й раз X копеек, бросил чёрту и понял, что не осталось у него ни копейки.

Сколько копеек было у крестьянина изначально?

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

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

В первой строке ввода содержится целое число X — количество копеек, которые крестьянин будет отдавать чёрту.

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

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

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

Ограничения

1 ≤ X ≤ 10⁹

1 ≤ N ≤ 18

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

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

По запросу сообщается количество набранных баллов.

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

В первом примере у крестьянина изначально было 5 копеек. После перехода по мосту копеек стало 15 и крестьянину пришлось их все отдать чёрту.

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

15
1

5

81
4

40

Задача D. Армия дроидов ≡

Условие

Торговая Федерация славится своей не очень эффективной военной силой — армией дроидов.

Армия дроидов состоит из N полков, i-й из которых содержит a_i рот по b_i дроидов в каждой. Для повышения огневой мощи и боевой эффективности (если это вообще возможно) руководство Торговой Федерации решило реорганизовать армию.

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

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

Абсолютной разницей двух целых чисел называется разница, посчитанная по модулю. Например, |5 − 2| = |3| = 3 или |2 − 5| = |−3| = 3.

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

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

Первая строка содержит одно целое число N — количество полков в армии дроидов.

Далее следует N строк, i-я из которых содержит два целых числа a_i и b_i — количество рот в i-м полку и количество дроидов в одной роте этого полка соответственно.

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

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

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

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

Ограничения

2 ≤ N ≤ 10⁵

1 ≤ a_i, b_i ≤ 10³

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

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

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

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

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

В первом примере, после реорганизации, количество дроидов в первом полку составит 16, а во втором полку — 15.

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

2
3 7
2 5

1
4 4
3 5

3
6 5
4 6
3 18

0
6 6
4 9
3 12

Задача E. Покраска забора ≡

Условие

Сегодня Евгений решил заняться покраской забора вокруг своего дома. Забор деревянный и состоит из N досок, причем каждая из них имеет ровно две соседние доски: 1 и N доска являются соседними.

Для того, чтобы покраска не стала рутинным занятием, Евгений решил красить доски не по порядку. За сегодня он планирует покрасить лишь Q досок, i-й из которых будет покрашена a_i доска.

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

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

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

Первая строка содержит два целых числа N и Q — количество досок в заборе и количество досок, которые Евгений собирается покрасить, соответственно.

Вторая строка содержит Q различных целых чисел a_i — номер доски, которую Евгений будет красить i-й по счету.

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

Выведите Q целых чисел через пробел — количество непрерывных непокрашенных участков после покраски i-й доски.

Ограничения

1 ≤ N ≤ 10⁹,

1 ≤ Q ≤ min(N, 10⁵)

1 ≤ a_i ≤ N

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

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

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

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

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

В первом примере после покраски 2 доски получится один непрерывных участок (3, 4, 1), после покраски 4 доски — два участка (1) и (3), после покраски 3 — (1), а после покраски 1 — не покрашенных досок не останется.

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

4 4
2 4 3 1

1 2 1 0

8 6
2 4 7 1 3 8

1 2 3 3 2 1

10 10
2 7 1 9 3 10 5 6 8 4

1 2 2 3 3 2 3 2 1 0