Компания «Nanosoft» готовится удивить мир принципиально новой игрой для смартфонов «Две башни». Ее ключевая особенность заключается в том, что играть в нее смогут даже самые маленькие дети. Во-первых, для управления используется всего одна кнопка. Во-вторых, проиграть просто невозможно (правда, игроку может надоесть часами нажимать на одну и ту же кнопку).
Игровое поле представляет собой бесконечную горизонтальную ленту, разбитую на ячейки, пронумерованные целыми числами слева направо (см. рис.). Изначально в ячейках с отрицательными номерами расположена армия монстров, у каждого из которых есть некоторое количество единиц здоровья. А именно, в ячейках \(-1, -2, \ldots, -K\) расположены монстры с 1 единицей здоровья, в следующих \(K\) ячейках (с номерами \(-(K+1), \ldots, -2K\)) расположены монстры с 2 единицами здоровья и так далее. Таким образом, для каждого целого положительного числа \(i\) в ячейке с номером \(-i\) изначально находится монстр с \(\left\lceil\frac{i}{K}\right\rceil\) единицами здоровья. Кроме того, на ленте расположены две башни, каждая из которых контролирует некоторый отрезок ленты: первой башне соответствуют все ячейки с \(A\) по \(B\) включительно, а второй - ячейки с \(C\) по \(D\) включительно (\(0 \leqslant A \leqslant B \lt C \leqslant D\)).
Например, при \(K = 3\), \(A = B = 1\), \(C = 3\), \(D = 4\) исходная позиция будет выглядеть следующим образом:
После очередного нажатия на кнопку происходит следующее. Сначала вся армия сдвигается на одну позицию вправо. Затем каждая башня производит выстрел по самому правому монстру, находящемуся в области ее видимости, отнимая у него единицу здоровья. Если у монстра отнимают последнюю единицу здоровья, он немедленно умирает и исчезает.
Игра заканчивается, как только впервые в ячейке с номером \(D + 1\) окажется монстр.
Как вы уже могли заметить, главная проблема игры заключается в том, что для выигрыша может потребоваться слишком много нажатий на кнопку, поэтому для некоторых особо сложных уровней решено ограничить возраст игроков, допускаемых к его прохождению. В связи с этим вам нужно определить, сколько нажатий на кнопку потребуется для победы на данном уровне, который описывается числами \(K\),\(A\), \(B\), \(C\) и \(D\).
В единственной строке входного файла содержатся 5 целых чисел \(K\), \(A\), \(B\), \(C\), \(D\) (\(1 \le K \le 10^9\), \(0 \le A \le B \lt C \le D \le 10^9\)). Соседние числа разделены одним пробелом.
Выведите единственное натуральное число - ответ на задачу.
Пошагово разберем первый тест.
2 0 0 1 1
7
3 1 1 3 4
13
1 2 3 7 11
17
Даны три строки \(A\), \(B\), \(C\). Требуется выбрать строки \(A'\), \(B'\) и \(C'\) (возможно пустые, возможно совпадающие), так чтобы строка \(A\) удовлетворяла шаблону \(*A'*B'*\), строка \(B\) удовлетворяла шаблону \(*C'*A'*\), строка \(C\) удовлетворяла шаблону \(*B'*C'*\) и величина \(|A'| + |B'| + |C'|\) была максимальна.
Первая строка входного файла содержит единственное целое число \(N\) (\(1 \le N \le 2\,000\)) - длину каждой из входных строк. В следующих трех строках содержатся строки \(A\), \(B\) и \(C\), каждая из которых состоит из \(N\) строчных латинских букв.
Выведите единственное целое число - \(|A'| + |B'| + |C'|\). Если не существует строк \(A'\), \(B'\) и \(C'\), из которых можно получить данные три строки \(A\), \(B\) и \(C\), то выведите ноль.
Тесты к этой задаче состоят из четырех групп.2 ac ba cb
3
4 agtb icea tbhc
4
3 abc cde dea
2
Каждое утро капитан Ъ проводит занятия по строевой подготовке в возглавляемой им роте солдат. Всего в роте N солдат, каждый из которых носит форму определенного цвета. Различных цветов формы не более 26, так что для удобства солдаты обозначают цвета строчными латинскими буквами. Таким образом, каждому из \(N\) солдат соответствует буква от 'a' до 'z' — цвет его формы.
За многие месяцы службы солдаты выяснили, что капитан пребывает в наилучшем расположении духа в том случае, когда цвета формы солдат в шеренге образуют определенную последовательность. Недолго думая, они выписали соответствующую строку \(S\) из \(N\) букв на асфальте и договорились, что отныне каждый должен при построении вставать именно на ту букву, которая соответствует цвету его формы.
Но к 23 февраля солдаты решили удивить капитана и поменяться местами так, чтобы \(каждый\) солдат встал не на ту букву, которая соответствует цвету его формы. Так, солдат с цветом формы 'q' может встать на любую букву, кроме буквы 'q', иначе удивление капитана будет недостаточным.
Помогите солдатам организовать праздничное построение: по данной строке \(S\), обозначающей старую последовательность цветов, выведите строку \(T\), являющуюся перестановкой символов строки \(S\) и обозначающую новую последовательность цветов. i-й символ строки T должен отличаться от i-го символа строки \(S\).
В первой строке входного файла содержится единственное целое число \(N\) — количество солдат в роте \((1 \le N \le 100 000)\). Во второй строке содержится строка S, состоящая из \(N\) строчных латинских букв.
Единственная строка выходного файла должна содержать искомую строку \(T\), если задумка солдат осуществима, и «Impossible» в противном случае. Если верных ответов несколько, выведите любой из них.
Тесты к этой задаче состоят из четырех групп. Баллы за каждую группу тестов ставятся только при прохождении всех тестов группы.
0. Тесты 1—2. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 3—21. В тестах этой группы \(N \le 9\). Эта группа оценивается в 30 баллов.
2. Тесты 22—36. В тестах этой группы \(N \le 200\), а строка не может содержать никаких букв, кроме 'a', 'b' и 'c'. Эта группа оценивается в 30 баллов независимо от первой.
3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов.
9 olimpiada
iapdialom
7 baaaaaa
Impossible
Скоро в Берляндии пройдет очередная Олимпиада. В рамках подготовки к этому важному мероприятию Берляндолимпстрой уже возвел N объектов и теперь хочет разобраться с тем, во сколько Берляндии это обошлось.
Стройка длилась \(K + 1\) день со дня номер \(0\) по день номер \(K\), причем стоимость j-го объекта в нулевой день была равна \(a_j\) бурлям. Однако каждый следующий день стоимость каждого объекта увеличивалась согласно следующему правилу: стоимость j-го объекта в i-й день становилась равна сумме стоимостей всех объектов с номерами, меньшими или равными j, в предыдущий день. Иначе говоря, \(S_{i,j}\) = \(\sum_{m=1}^{j} S_{i-1,m}\), где \(S_{i,j}\) — стоимость j-го объекта в i-й день. В итоге на j-й объект было потрачено \(S_{K,j}\) , то есть его стоимость в последний \(K\)-й день. \t{Назовем эту величину итоговой стоимостью j-го объекта.}
Такие увеличения стоимостей проектов для Берляндии не редкость, однако оказалось, что и этих денег не хватило! Выяснилось, что в некоторый день i > 0 стоимость некоторого объекта j дополнительно повысилась на пока не известную следователям сумму X (то есть \(S_{i,j}\) = \(\sum_{m=1}^{j} S_{i-1,m}\) + X), что повлияло на стоимости объектов в последующие дни. Следователи выяснили, что из-за этого сумма итоговых стоимостей всех объектов увеличилась на \(R\) бурлей.
Помогите следователям выяснить минимально возможное значение X.
В первой строке входного файла содержатся три целых числа \(N\), \(K\), \(R\): количество олимпийских объектов (\(1 \le N \le 10^5\) ), количество дней увеличения стоимости объектов (\(1 \le K \le 10^5\) ) и количество бурлей, на которое незаконно возросла итоговая сумма (\(1 \le R \le 10^{18}\)). В следующей строке входного файла содержатся N целых чисел \(a_i\) — стоимости объектов в нулевой день (\(1 \le a_i \le 10^9\)).
Единственная строка выходного файла должна содержать единственное целое число — минимально возможное значение \(X\)
Тесты к этой задаче состоят из четырех групп.
0. Тест 1. Тест из условия, оцениваемый в ноль баллов.
1. Тесты 2—25. В тестах этой группы \(N \le 10, K \le 10, a_i \le 10\), искомое значение \(X\) не превосходит \(10\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
2. Тесты 26—38. В тестах этой группы \(N \le 1 000, K \le 1 000\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов первой группы.
3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Тесты в этой группе оцениваются \t{независимо}
3 3 12 1 3 3
2
Как известно, автобус должен ходить по расписанию. И Иннокентий, используя свои многочисленные связи в магазине плитки, совершил невозможное: по маршруту теперь курсируют целых \(M\) автобусов, и на каждой остановке висит свое расписание, которое представляет собой набор из \(M\) времен. Плиточный магнат является крупным авторитетом в городе, поэтому расписание соблюдается: от каждой остановки ровно в каждое из указанных времен отправляется автобус. Казалось, что проблема общественного транспорта навсегда решена...
Однако, дьявол кроется в деталях. Действительно, автобусы отправляются с остановок в нужные времена, но никто не гарантирует, что между остановками не произойдет обгон, и автобус, который отправился от предыдущей остановки раньше, не отправится со следующей гораздо позже, при этом не нарушая условия, что в каждое из указанных в расписании времен какой-то автобус отправляется.
Иннокентий решил оценить масштабы трагедии. Для этого он попросил каждого из Q своих друзей сообщить маршрут, по которому они добираются до места работы. Каждый маршрут описывается тремя числами \(u_i\), \(v_i\), \(w_i\): \(u_i\) — это номер остановки, ближайшей к дому i-го друга, \(v_i\) — номер остановки, ближайшей к его работе, а \(w_i\) — номер автобуса,на котором i-й друг едет из дома на работу. При этом с точки зрения i-го друга автобусы нумеруются от \(1\) до \(M\) в том порядке, в котором они отправляются с остановки \(u_i\).
Иннокентий просит вас независимо для каждого друга определить, насколько поздно тот может доехать до конечной остановки своего маршрута.
В первой строке входных данных содержатся два целых числа \(N\) и \(M\) — количество остановок и количество автобусов соответственно (\(2 \le N * M \le 150 000\)). В следующей строке содержатся \(N-1\) целых чисел \(travel_1\), . . . , \(travel_{N-1}\), где \(travel_i\) — минимальное время, необходимое для перемещения между остановками i и i + 1 (\(1 \le travel_i \le 10^9\)).
В следующих \(N\) строках содержатся описания расписаний, каждое из которых представляет собой отсортированный по возрастанию список из \(M\) различных целых чисел \(t_i\) — времен, в которые автобусы должны отправляться с соответствующей остановки (\(1 \le t_i \le 10^9\)).
В следующей строке содержится число T — тип теста (1 или 2). Если T = 1, то это — обычный тест. Тогда на следующей строке содержится целое число Q — количество опрошенных друзей Иннокентия (\(1 \le Q \le 150 000 \)). Далее в Q строках содержатся описания маршрутов друзей, каждое из которых состоит из трех целых чисел \(u_i\), \(v_i\) и \(w_i\): номеров остановок, где начинается и заканчивается поездка i-го друга, и номер автобуса в расписании остановки ui, на котором эта поездка совершается (\(1 \le u_i < v_i \le N, 1 \le w_i \le M\)).
\textbf{Обратите внимание} : дальнейшее описание относится только к последней группе тестов. Если T = 2, то это — тест-серия. Тогда на следующей строке содержатся три целых числа — A, B и K (\(1 \le A, B \le 10^3 , 1 \le K \le 150\)).
В \t{тесте-серии} у Иннокентия Q = (N -1)·M ·K друзей. На каждой из N - 1 остановок, кроме последней, проживает ровно M * K друзей, причем для каждого \(w\) от 1 до M есть ровно K друзей, которые уезжают с этой остановки w-м автобусом.
Остановки, до которых едут K друзей, уезжающих с u-й остановки w-м автобусом, определяются следующим образом. Задается последовательность чисел \(q_i\): \(q_1\) = A, \(q_2\) = B, для i > 2 \(q_i\) = u * \(q_{i-1}\) + w * \(q_{i-2}\) + 42. Тогда i-й из этих K друзей будет ехать до остановки с номером \(v_i\) = u + 1 + (\(q_i\) mod (N - u)), где mod обозначает операцию взятия остатка от деления.
Если это обычный тест, то выведите для каждого друга в отдельной строке единственное целое число - искомое максимальное время прибытия на конечную остановку в его маршруте. Если это тест-серия, то выведите единственное целое число — остаток от деления суммы максимальных времен прибытия для всех друзей Иннокентия на \(2^{32}\).
Приведем пояснение ко второму тесту из условия.
Это \textbf{тест-серия}. В нем у Иннокентия 5 · 4 · 2 = 40 друзей. Например, с первой остановки вторым автобусом уезжают ровно пять друзей. Поясним, как в этом тесте для них определить конечные остановки. u = 1, w = 2. Строим последовательность \(q_i\): \(q_1\) = 9, \(q_2\) = 10, \(q_3\) = 1 · 10 + 2 · 9 + 42 = 70, \(q_4\) = 1 · 70 + 2 · 10 + 42 = 132, \(q_5\) = 1 · 132 + 2 · 70 + 42 = 314. По ней восстанавливаются конечные остановки для этих пяти друзей Иннокентия: \(v_1\) = 1 + 1 + (9 mod 4) = 3, \(v_2\) = 1 + 1 + (10 mod 4) = 4, \(v_3\) = 1 + 1 + (70 mod 4) = 4, \(v_4\) = 1 + 1 + (132 mod 4) = 2, \(v_5\) = 1 + 1 + (314 mod 4) = 4.
Тесты к этой задаче состоят из шести групп. Каждая группа, кроме нулевой, оценивается в 20 баллов. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов \textbf{предыдущих групп}, исключая тесты из условия. В группах тестов с первой по четвертую включительно вам предлагаются только обычные тесты.
0. Тесты 1—2. Тесты из условия, оцениваются в ноль баллов.
1. Тесты 3—12. В тестах этой группы \(N = 2, M \le 1 000, Q \le 1 000\).
2. Тесты 13—22. В тестах этой группы \(N = 2, M \le 75 000, Q \le 75 000\).
3. Тесты 23—37. В тестах этой группы \(N * M \le 150 000, N * Q \le 150 000\).
4. В тестах этой группы \(N * M \le 150 000, Q \le 150 000\).
5. В этой группе вам предлагаются только тесты-серии. Другие дополнительные ограничения отсутствуют.
2 3 1 1 10 21 11 21 31 1 3 1 2 1 1 2 2 1 2 3
21 21 31
5 2 2 5 3 4 1 3 3 5 10 11 13 14 18 23 2 9 10 5
667