Встретил крестьянин чёрта, и тот говорит ему: «Видишь мост через эту реку?
Стоит тебе только перейти через этот мост~-- у тебя будет втрое больше денег,
чем есть. Перейдёшь назад, опять станет втрое больше, чем было. И так каждый раз,
как ты будешь переходить через мост».
~-- Ой ли?~-- говорит крестьянин.
~-- Верное слово!~-- уверяет чёрт.~-- Только чур, уговор! За то,
что я тебе утраиваю деньги, ты, каждый раз перейдя через мост, будешь отдавать
мне по X копеек. Иначе не согласен.
~-- Ну, что же, это не беда!~-- говорит крестьянин.~-- Раз деньги будут утраиваться,
так отчего же тебе X копеек каждый раз не дать?
Перешёл крестьянин через мост, посчитал деньги~-- и вправду, стало втрое больше, чем
было. Отсчитал X копеек, бросил чёрту, перешёл снова.. После N-го перехода по мосту
отсчитал крестьянин в N-й раз X копеек, бросил чёрту и понял, что не осталось
у него ни копейки.
Сколько копеек было у крестьянина изначально?
Требуется написать программу, которая по количеству копеек, взятых чёртом за один переход по мосту,
и количеству переходов определит изначальное количество копеек у крестьянина.
Формат входных данных
В первой строке ввода содержится целое число X~-- количество копеек,
которые крестьянин будет отдавать чёрту.
Во второй строке содержится целое число N~-- сколько раз крестьянин смог
пройти по мосту, прежде чем у него закончились копейки.
Формат выходных данных
Выведите единственное целое число K~-- изначальное количество копеек у крестьянина.
Ограничения
1 ≤ X ≤ 109
1 ≤ N ≤ 18
Описание системы оценивания
Баллы начисляются пропорционально количеству пройденных тестов.
По запросу сообщается количество набранных баллов.
Пояснения к примерам
В первом примере у крестьянина изначально было 5 копеек.
После перехода по мосту копеек стало 15 и крестьянину пришлось их все отдать чёрту.
Торговая Федерация славится своей не очень эффективной военной силой~-- армией дроидов.
Армия дроидов состоит из N полков, i-й из которых содержит ai рот по bi дроидов в каждой.
Для повышения огневой мощи и боевой эффективности (если это вообще возможно)
руководство Торговой Федерации решило реорганизовать армию.
Основное требование реорганизации~-- минимизация абсолютной разницы количества дроидов между двумя любыми полками.
В ходе реорганизации разрешено изменять количество рот в любом полку и количество дроидов в ротах этого полка,
но в рамках одного полка количество дроидов в каждой роте должно быть одинаковым.
Общее количество дроидов также должно остаться неизменным.
Генерал Гривус хочет определить минимально возможную абсолютную разницу между полками,
а также предложить новый план распределения дроидов.
Абсолютной разницей двух целых чисел называется разница, посчитанная по модулю.
Например, |5 − 2| = |3| = 3 или |2 − 5| = |−3| = 3.
Требуется написать программу, которая по текущим данным об армии дроидов определит наилучший вариант реорганизации.
Формат входных данных
Первая строка содержит одно целое число N~-- количество полков в армии дроидов.
Далее следует N строк, i-я из которых содержит два целых числа ai и bi~--
количество рот в i-м полку и количество дроидов в одной роте этого полка соответственно.
Формат выходных данных
Первая строка должна содержать одно целое число~-- минимально возможную абсолютную разницу количества дроидов между полками.
Далее должно быть выведено N строк, i-я из которых содержит два целых положительных числа~--
новое количество рот в i-м полку и новое количество дроидов в одной роте этого полка соответственно.
Если ответов несколько, разрешается вывести любой из них.
Ограничения
2 ≤ N ≤ 105
1 ≤ ai, bi ≤ 103
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае,
если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
N
1
66
2 ≤ N ≤ 102
2
34
2 ≤ N ≤ 105
1
Пояснения к примерам
В первом примере, после реорганизации, количество дроидов в первом полку составит 16, а во втором полку~-- 15.
Сегодня Евгений решил заняться покраской забора вокруг своего дома.
Забор деревянный и состоит из N досок, причем каждая из них имеет ровно две соседние доски:
1 и N доска являются соседними.
Для того, чтобы покраска не стала рутинным занятием, Евгений решил красить доски не по порядку.
За сегодня он планирует покрасить лишь Q досок, i-й из которых будет покрашена ai доска.
После покраски очередной доски Евгений хочет определять количество непрерывных участков, состоящих только из непокрашенных досок.
Причем, если две непокрашенных доски являются соседними, то они обязательно относятся к одному участку.
Требуется написать программу, которая по действиям Евгения определит количество непокрашенных участков после покраски очередной доски.
Формат входных данных
Первая строка содержит два целых числа N и Q~-- количество досок в заборе и
количество досок, которые Евгений собирается покрасить, соответственно.
Вторая строка содержит Q различных целых чисел ai~-- номер доски,
которую Евгений будет красить i-й по счету.
Формат выходных данных
Выведите Q целых чисел через пробел~--
количество непрерывных непокрашенных участков после покраски i-й доски.
Ограничения
1 ≤ N ≤ 109,
1 ≤ Q ≤ min(N, 105)
1 ≤ ai ≤ N
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае,
если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
N
Q
1
21
1 ≤ N ≤ 102
1 ≤ Q ≤ min(N, 102)
2
25
1 ≤ N ≤ 105
1 ≤ Q ≤ min(N, 103)
1
3
31
1 ≤ N ≤ 105
1 ≤ Q ≤ min(N, 105)
1-2
4
23
1 ≤ N ≤ 109
1 ≤ Q ≤ min(N, 105)
1-3
Пояснения к примерам
В первом примере после покраски 2 доски получится один непрерывных участок (3, 4, 1),
после покраски 4 доски~-- два участка (1) и (3), после покраски 3~-- (1),
а после покраски 1~-- не покрашенных досок не останется.
Этим летом у Анастасии было много свободного времени, и она решила пройти все уровни своей любимой компьютерной игры.
Для полного прохождения одного уровня требуется пройти все его эпизоды.
Сегодня Анастасия будет проходить уровень, состоящий из N эпизодов.
Некоторые из эпизодов можно пройти на разную концовку, из-за которой определяется следующий эпизод в уровне.
При этом некоторые эпизоды являются конечными~-- у таких нет следующего эпизода.
На каждый эпизод, кроме первого~-- начального, можно попасть ровно из одного другого эпизода.
Более формально иерархию эпизодов можно описать подвешенным деревом из N вершин.
После прохождения некоторых эпизодов, на них можно будет сохраниться,
и в следующий раз продолжить прохождения с начала этих эпизодов.
Всего есть M эпизодов с возможностью сохранения, причем в первом эпизоде точно можно сохраняться.
Анастасии стало интересно, какое минимальное количество эпизодов ей надо пройти для полного прохождения этого уровня.
Требуется написать программу, которая по описанию уровня определит минимально возможное количество эпизодов,
которые нужно пройти для полного прохождения этого уровня.
Формат входных данных
Первая строка содержит два целых числа N и M~-- количество эпизодов в уровне и количество эпизодов,
на которых можно сохраняться, соответственно.
Вторая строка содержит M различных целых чисел ai~--
номера эпизодов в игре, на которых действует сохранение.
Далее следует N−1 строк, i из которых содержит два целых числа ui и vi~-- эпизод,
который нужно пройти, и эпизод, на который можно попасть после этого, соответственно.
Гарантируется, что иерархия эпизодов описывает подвешенное дерево.
Гарантируется, что на 1 уровне можно сохраняться.
Формат выходных данных
В единственной строке выведите ответ на задачу.
Ограничения
1 ≤ M ≤ N ≤ 105
1 ≤ ai, ui, vi ≤ N
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае,
если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
N
M
1
16
1 ≤ N ≤ 102
1 ≤ M ≤ N
2
15
1 ≤ N ≤ 104
1 ≤ M ≤ N
1
3
23
1 ≤ N ≤ 105
M = 1
4
22
1 ≤ N ≤ 105
M = N
5
24
1 ≤ N ≤ 105
1 ≤ M ≤ N
1-4
Пояснения к примерам
В первом примере в первое прохождение можно пройти уровни (1, 3, 6), во второе прохождение~-- (1, 3, 7),
в третье прохождение (1, 2, 4), в четвертое прохождение~-- (2, 5).
Последнее прохождение можно начать со 2-о уровня, так как он уже был пройден и на нём можно было сохраниться.
Всего для полного прохождения пришлось пройти 11 уровней.
Во время Войны Бесконечности Доктор Стрэндж стал просматривать варианты возможного будущего.
Из четырнадцати миллионов победным оказался лишь один, а после победы Мстители устроили большую вечеринку.
Всего на вечеринку придёт N Мстителей.
Не волнуйтесь, остальные герои не погибли (это же Марвел), они уже успели отправиться на своё сольное спасение мира.
Но новая напасть оказалась не за горами, и, возможно, она пострашнее Таноса~-- героям необходимо решить, кто пойдёт мыть посуду.
К сожалению, перчатка бесконечности была уничтожена, поэтому помыть всю (или хотя бы половину) посуды щелчком пальцев не получится.
Сложно только представить, к какой гражданской войне могла привести эта ситуация,
если бы только один из героев не вспомнил про народный метод решения подобных проблем~-- считалочку.
Все герои встали в круг, они пронумерованы от 1 до N, 1 и N герой стоят рядом.
После они начали отсчитывать M человек (енотов, деревьев и т.д.) от первого героя.
Герой, на котором закончился счет, покидал круг, и счет начинался по новой, от следующего героя в круге.
И так до тех пор, пока в круге не остался бы один герой~-- ему-то и придётся спасать этот мир
(или по крайней мере эту вечеринку) от грязной посуды.
Требуется написать программу, которая по количеству Мстителей на вечеринке и числу M определит, кому придётся мыть посуду.
Формат входных данных
Первая строка содержит два целых числа N и M~-- количество Мстителей на вечеринке и
количество героев, которое будет отсчитываться по кругу, соответственно.
Формат выходных данных
В единственной строке выведите ответ на задачу.
Ограничения
1 ≤ N ≤ 3 ⋅ 105
1 ≤ M ≤ 109
Описание подзадач и системы оценивания
Баллы за каждую подзадачу начисляются только в случае,
если все тесты этой подзадачи и необходимых подзадач успешно пройдены.
Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.
По запросу сообщается результат окончательной проверки на каждом тесте.
Подзадача
Баллы
Дополнительные ограничения
Необходимые подзадачи
N
M
1
7
1 ≤ N ≤ 102
1 ≤ M ≤ 102
2
11
1 ≤ N ≤ 104
1 ≤ M ≤ 104
1
3
8
1 ≤ N ≤ 104
1 ≤ M ≤ 109
1-2
4
11
1 ≤ N ≤ 3 ⋅ 104
1 ≤ M ≤ 109
1-3
5
9
1 ≤ N ≤ 4 ⋅ 104
1 ≤ M ≤ 109
1-4
6
12
1 ≤ N ≤ 6 ⋅ 104
1 ≤ M ≤ 109
1-5
7
9
1 ≤ N ≤ 7 ⋅ 104
1 ≤ M ≤ 109
1-6
8
12
1 ≤ N ≤ 105
1 ≤ M ≤ 109
1-7
9
21
1 ≤ N ≤ 3 ⋅ 105
1 ≤ M ≤ 109
1-8
Пояснения к примерам
В первом примере герои будут покидать круг в следующем порядке: 3, 1, 5, 2.
