Брюс Уэйн гонится за помощником Фальконе по прозвищу Пингвин на бэтмобиле по плоскости.
Из-за взрыва бэтмобиль повреждается и теперь может перемещаться только на один вперед и на один вправо. При этом, движение прямо тратит $$$a$$$ единиц топлива, а вправо — $$$b$$$ единиц топлива.
Сейчас машина супергероя находится в точке $$$(0, 0)$$$ и имеет в баке $$$f$$$ топлива. Когда топливо закончится, бэтмобиль не сможет больше перемещаться и герою придется догонять злодея бегом.
Определите, сколько существует точек с целочисленными координатами, до которых Бэтмен все еще может добраться на своем бэтмобиле.
Как известно, все супергерои обычно существуют в $$$t$$$ параллельных вселенных. Поэтому решите эту задачу для каждой из параллельных вселенных.
В первой строке входных данных дано целое число $$$t$$$ — количество вселенных, в которых необходимо решить задачу ($$$1 \leqslant t \leqslant 500$$$).
Каждая из следующих $$$t$$$ строк ввода описывает одну вселенную. В $$$i$$$-й из них через пробел даны целые числа $$$a_i$$$, $$$b_i$$$ и $$$f_i$$$ — затраты топлива на перемещение на один вперед, затраты топлива на перемещение на один вправо, начальный объем топлива в баке бэтмобиля ($$$1 \leqslant a_i, b_i, f_i \leqslant 10^9$$$).
Выведите ответ на задачу для каждой из вселенных в отдельной строке. Каждый ответ должен состоять из единственного целого числа — количества достижимых на бэтмобиле целочисленных точек.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 15 | $$$t \leqslant 5$$$, $$$a_i, b_i, s_i \leqslant 10$$$ | – | полная |
| 2 | 15 | $$$t \leqslant 100$$$, $$$a_i, b_i, s_i \leqslant 100$$$ для всех $$$i$$$ | 1 | полная |
| 3 | 14 | $$$s_i$$$ делится на $$$a_i$$$ и $$$b_i$$$ для всех $$$i$$$ | – | полная |
| 4 | 20 | $$$a_i \geqslant 10^5$$$ | – | полная |
| 5 | 18 | $$$a_i = 1$$$ для всех $$$i$$$ | – | полная |
| 6 | 18 | нет | 1 – 5 | первая ошибка |
33 2 91 4 171 1 8
12 50 45
48 1 225 5 34 2 31 1 1
45 1 2 3
В первом примере для первого набора входных данных достижимы точки $$$(0, 0)$$$, $$$(1, 0)$$$, $$$(0, 1)$$$, $$$(2, 0)$$$, $$$(1, 1)$$$, $$$(0, 2)$$$, $$$(3, 0)$$$, $$$(2, 1)$$$, $$$(1, 2)$$$, $$$(0, 3)$$$, $$$(1, 3)$$$, $$$(0, 4)$$$.
Водопровод в Готэм-Сити представляет из себя систему из $$$n$$$ подсистем водонапорных башен. Подсистема номер $$$i$$$ состоит из $$$b_i$$$ независимых башен, каждая из которых в данный момент содержит $$$a_i$$$ единиц воды. Каждую секунду уровень воды в каждой башне увеличивается на $$$1$$$. Через ровно $$$t_i$$$ секунд во всех башнях $$$i$$$-й подсистемы включается водосброс в канализацию, то есть уровень воды в каждой из башен становится равен $$$0$$$ и перестает увеличиваться.
Незадолго до поимки Загадочник заминировал все башни в каждой из $$$n$$$ подсистем. После взрыва любой башни вся имевшаяся на тот момент в башне вода выливается на улицы города, а подача новой воды прекращается. Таким образом, если взорвать башню $$$i$$$-й подсистемы в момент времени $$$t \lt t_i$$$, на улицы города выльется $$$a_i + t$$$ воды. При этом, взрыв одной из башен подсистемы не влияет на другие башни этой подсистемы.
У Загадочника есть пульты для дистанционного взрыва каждой башни города. Каждую секунду он может выбрать не более $$$k$$$ (возможно, ноль) водонапорных башен и взорвать их. Злодей хочет выбрать порядок взрывов так, чтобы как можно больше воды вытекло на улицы города (вода, стекшая в результате водосброса, не считается).
Бэтмэн опасается действий своего врага, поэтому хочет узнать, какое максимальное количество воды суммарно может оказаться на улицах города?
В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leqslant n \leqslant 10^5$$$, $$$1 \leqslant k \leqslant 10^9$$$) — количество подсистем водонапорных башен в городе и максимальное количество башен, которые можно взорвать за одну секунду.
В следующих $$$n$$$ строках перечислены описания подсистем, $$$i$$$-я из строк содержит три целых числа, разделенных пробелом — $$$t_i$$$, $$$a_i$$$ и $$$b_i$$$ — секунда, в которую происходит водосброс, изначальный уровень воды в башнях $$$i$$$-й подсистемы и количество башен в подсистеме ($$$1 \leqslant t_i, b_i \leqslant 10^9$$$, $$$1 \leqslant a_i \leqslant 10^4$$$). Гарантируется, что сумма $$$b_i$$$ по всем $$$i$$$ не превосходит $$$10^9$$$.
Выведите единственное целое число — максимальное количество воды, которое может оказаться на улицах города.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 10 | суммарное количество башен $$$\leqslant 5$$$; $$$t_i \leqslant 5$$$ для всех $$$i$$$; $$$k = 1$$$ | – | полная |
| 2 | 15 | $$$k = 1$$$; $$$b_i = 1$$$ для всех $$$i$$$; все $$$t_i$$$ различны | – | полная |
| 3 | 10 | все $$$t_i$$$ равны между собой | – | полная |
| 4 | 20 | $$$b_i = 1$$$ для всех $$$i$$$ | 2 | полная |
| 5 | 20 | $$$t_i \leqslant 10^5$$$ для всех $$$i$$$ | 1 | первая ошибка |
| 6 | 25 | нет | 1 – 5 | первая ошибка |
3 2 10 3 1 2 2 1 4 1 1
19
3 1 10 3 7 2 2 3 4 1 1
69
В первом тестовом примере в каждой подсистеме одна башня. Башню из первой подсистемы можно взорвать на девятой секунде, и получить $$$3 + 9 = 12$$$ воды; башню из второй подсистемы — на первой секунде, и получить $$$2 + 1 = 3$$$ воды; третьей подсистемы — на третьей секунде, и получить $$$1 + 3 = 4$$$. Итого, мы получим $$$12 + 3 + 4 = 19$$$ единиц воды. Заметим, что от каждой башни мы получили максимально возможное количество воды, поэтому ответ максимальный.
Во втором примере одну башню второй подсистемы стоит взорвать на первой секунде, а остальные гарантированно будут сброшены в канализацию. Башню третьей подсистемы можно взорвать на второй или третьей секунде, но за секунды с четвертой по девятую невозможно успеть взорвать все $$$7$$$ башен первой подсистемы. Поэтому, если взрывать башню третьей подсистемы на третьей секунде, то во вторую секунду стоит взорвать одну башню первой подсистемы. В обоих случаях ответ будет одинаковый и равный $$$((2 + 1)) + ((1 + 2)) + ((3 + 3) + (3 + 4) + \ldots + (3 + 9)) = 69$$$.
Загадочник похищает окружного прокурора Джила Колсона.
Чтобы спастись, Колсон должен отгадать три загадки. Бэтмен помогает ему отгадать первые две, но третья загадка оказалась слишком сложной. Сможете ли вы помочь ему с отгадкой?
Загадка устроена следующим образом:
Требуется по данному массиву $$$b$$$ восстановить все возможные величины сдвига $$$x$$$, которые могли привести к получению такого массива $$$b$$$ из какого-то массива $$$a$$$.
В первой строке ввода дано единственное целое число $$$n$$$ — длина исходного массива ($$$1 \leqslant n \leqslant 10^6$$$).
Во второй строке через пробел перечислены $$$n$$$ целых чисел $$$b_1$$$, $$$b_2$$$, ..., $$$b_n$$$ — элементы полученного Загадочником массива $$$b$$$ ($$$|b_i| \leqslant 10^9$$$).
Выведите через пробел $$$n - 1$$$ целое число, $$$i$$$-е из которых равно $$$1$$$, если $$$x = i$$$ могло иметь место, и $$$0$$$ иначе.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 7 | $$$n \leqslant 5$$$, $$$|b_i| \leqslant 10$$$ для всех $$$i$$$ | – | полная |
| 2 | 8 | $$$n \in \mathbb{P}$$$ (простое) | – | полная |
| 3 | 13 | $$$n = 2^k$$$ для некоторого целого $$$k$$$ | – | полная |
| 4 | 14 | количество $$$i$$$, для которых $$$b_i \neq 0$$$, не более десяти | 1 | полная |
| 5 | 15 | $$$n \leqslant 1000$$$ | 1 | полная |
| 6 | 23 | $$$n \leqslant 10^5$$$ | 5 | первая ошибка |
| 7 | 20 | нет | 1 – 6 | первая ошибка |
3 -2 0 2
1 1
6 -1 2 -3 -4 4 2
1 1 0 1 1
7 -1 1 -1 1 -1 1 -1
0 0 0 0 0 0
В первом примере такой массив $$$b$$$ мог быть получен, например, из массива $$$a = [2, 4, 4]$$$ сдвигом на $$$1$$$ влево или из массива $$$a = [2, 2, 4]$$$ сдвигом на $$$2$$$ влево.
В первом примере данный массив $$$b$$$ ни при каком $$$a$$$ не мог быть получен сдвигом на $$$3$$$, а для сдвигов $$$1$$$ или $$$4$$$, например, подошли бы массивы $$$a = [1, 2, 0, 3, 7, 3]$$$ и $$$a = [3, 7, 0, 3, 4, 5]$$$, соответственно.
Для третьего примера можно показать, что такой $$$b$$$ в принципе не мог быть получен описанным в условии образом.
Загадочник придумал новую ловушку для жителей Готэм–сити. По плану злодея, ловушка будет состоять из $$$n$$$ помещений, соединенных переходами так, чтобы из любого помещения $$$u$$$ всегда был единственный способ добраться в помещение $$$v$$$.
Для перемещения между комнатами нужно будет использовать специальный лифт, который может перемещаться по всем переходам ловушки. Одновременно лифт вмещает не больше $$$b$$$ людей, и когда лифт хотя бы с одним человеком внутри переезжает из помещения $$$u_i$$$ в помещение $$$v_i$$$, он теряет $$$w_i$$$ прочности. Лифт не теряет прочность, если в нем нет людей во время перемещения.
Загадочник планирует поделить всех своих жертв на $$$m$$$ групп так, чтобы в группе $$$i$$$ было $$$c_i$$$ человек, которые изначально находятся в комнате $$$x_i$$$, и обязаны добраться до комнаты $$$y_i$$$ (разумеется, используя лифт). При этом людям не запрещается временно высаживаться в произвольных местах пути и ждать перед тем, как продолжить движение.
Супер–злодей хочет выбрать такую прочность лифта, чтобы лифт мог доставить всех людей в нужные комнаты, но гарантированно разрушился (то есть его прочность упала до $$$0$$$) сразу после этого. Для этого он хочет найти минимальные возможные повреждения, которые может получить лифт, перемещая людей. Как опытный злодей, Загадочник справится с этой задачей, а справитесь ли вы?
В первой строке ввода через пробел даны три целых числа $$$n$$$, $$$m$$$ и $$$b$$$ — количество помещений в ловушке, количество групп людей и максимальная вместимость лифта ($$$2 \leqslant n \leqslant 10^5$$$; $$$1 \leqslant m \leqslant 2 \cdot 10^5$$$; $$$1 \leqslant b \leqslant 10^9$$$).
В следующих $$$n - 1$$$ строках дается описание комнат ловушки, между которыми есть переходы. В строчке $$$i$$$ даются три целых числа $$$u_i$$$, $$$v_i$$$ и $$$w_i$$$, означающие, что между комнатами $$$u_i$$$ и $$$v_i$$$ есть переход для лифта, наносящий лифту $$$w_i$$$ повреждений ($$$1 \leqslant u_i, v_i \leqslant n$$$; $$$0 \leqslant w_i \leqslant 10^4$$$). Гарантируется, что от любой комнаты можно добраться по переходам до любой другой.
В следующих $$$m$$$ строках дается описание групп людей. Описание группы номер $$$i$$$ — три целых числа $$$x_i$$$, $$$y_i$$$ и $$$c_i$$$ — номера стартовой и конечной комнат, и количество людей в группе ($$$1 \leqslant x_i, y_i \leqslant n$$$; $$$1 \leqslant c_i \leqslant 10^9$$$).
Выведите единственное число — минимальную величину повреждений, которые получит лифт после того, как все люди сбегут из ловушки Загадочника.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 9 | $$$n, m, b \leqslant 3$$$; $$$c_i \leqslant 3$$$ для всех $$$i$$$ | – | полная |
| 2 | 14 | $$$n, m, b \leqslant 50$$$; $$$c_i \leqslant 50$$$ для всех $$$i$$$ | 1 | полная |
| 3 | 10 | $$$n \leqslant 10^4$$$; $$$c_i \leqslant 10^4$$$ для всех $$$i$$$; $$$b = 10^9$$$ | – | полная |
| 4 | 16 | каждое помещение соединено только с одним или двумя другими | – | полная |
| 5 | 19 | $$$n, m \leqslant 500 $$$ | 2 | полная |
| 6 | 12 | $$$n \leqslant 5000 $$$ | 5 | первая ошибка |
| 7 | 20 | нет | 1 – 6 | первая ошибка |
4 3 5 3 2 3 3 4 0 4 1 2 1 2 9 2 4 7 3 4 12
16
7 3 5 2 1 2 3 1 1 3 4 3 3 5 0 5 6 4 5 7 0 2 4 11 1 7 8 4 5 3
22
В первом примере комнаты связаны по цепочке $$$2 \leftrightarrow 3 \leftrightarrow 4 \leftrightarrow 1$$$. Одна из возможных последовательностей действий выглядит так:
Во втором примере один из оптимальных вариантов выглядит следующим образом: сначала доставить всех людей до комнаты номер $$$3$$$ (при чем люди, двигающиеся из комнаты номер $$$2$$$, должны будут взять себе попутчиков в комнате $$$1$$$), а после развести их по нужным комнатам в максимально возможных группах.