Bruce Wayne is chasing his assistant, known as the Penguin, on the Batmobile on a plane.
Due to an explosion, the Batmobile is damaged and can now only move one step forward and one step to the right. Moving straight consumes $$$a$$$ units of fuel, while moving to the right consumes $$$b$$$ units of fuel.
Currently, the superhero's car is located at point $$$(0, 0)$$$ and has $$$f$$$ units of fuel in the tank. When the fuel runs out, the Batmobile will no longer be able to move and the hero will have to chase the villain on foot.
Determine how many points with integer coordinates the Batman can still reach on his Batmobile.
As it is known, all superheroes usually exist in $$$t$$$ parallel universes. Therefore, solve this problem for each of the parallel universes.
The first line of input contains an integer $$$t$$$ - the number of universes in which the problem needs to be solved ($$$1 \leqslant t \leqslant 500$$$).
Each of the following $$$t$$$ input lines describes one universe. The $$$i$$$-th line contains three integers $$$a_i$$$, $$$b_i$$$, and $$$f_i$$$ separated by a space - the fuel consumption for moving one step forward, the fuel consumption for moving one step to the right, and the initial fuel volume in the Batmobile's tank ($$$1 \leqslant a_i, b_i, f_i \leqslant 10^9$$$).
Output the answer to the problem for each universe on a separate line. Each answer should consist of a single integer - the number of reachable points with the Batmobile.
Points for each subtask are awarded only if all tests of this subtask and the necessary subtasks, as well as the tests from the statement, are passed successfully.
| Subtask | Points | Additional Constraints | Necessary Subtasks | Checking Information |
| 1 | 15 | $$$t \leqslant 5$$$, $$$a_i, b_i, s_i \leqslant 10$$$ | – | full |
| 2 | 15 | $$$t \leqslant 100$$$, $$$a_i, b_i, s_i \leqslant 100$$$ for all $$$i$$$ | 1 | full |
| 3 | 14 | $$$s_i$$$ is divisible by $$$a_i$$$ and $$$b_i$$$ for all $$$i$$$ | – | full |
| 4 | 20 | $$$a_i \geqslant 10^5$$$ | – | full |
| 5 | 18 | $$$a_i = 1$$$ for all $$$i$$$ | – | full |
| 6 | 18 | none | 1 – 5 | first error |
33 2 91 4 171 1 8
12 50 45
48 1 225 5 34 2 31 1 1
45 1 2 3
In the first example, for the first set of input data, the reachable points are $$$(0, 0)$$$, $$$(1, 0)$$$, $$$(0, 1)$$$, $$$(2, 0)$$$, $$$(1, 1)$$$, $$$(0, 2)$$$, $$$(3, 0)$$$, $$$(2, 1)$$$, $$$(1, 2)$$$, $$$(0, 3)$$$, $$$(1, 3)$$$, $$$(0, 4)$$$.
The water supply system in Gotham City consists of a system of $$$n$$$ subsystems of water towers. Subsystem number $$$i$$$ consists of $$$b_i$$$ independent towers, each of which currently contains $$$a_i$$$ units of water. The water level in each tower increases by $$$1$$$ unit every second. After exactly $$$t_i$$$ seconds, a water discharge into the sewer system occurs in all towers of subsystem $$$i$$$, meaning that the water level in each tower becomes $$$0$$$ and stops increasing.
Shortly before the capture of the Riddler, he booby-trapped all the towers in each of the $$$n$$$ subsystems. After an explosion of any tower, all the water that was in the tower at that moment spills onto the city streets, and the supply of new water stops. Thus, if tower $$$i$$$ of subsystem $$$i$$$ is exploded at time $$$t \lt t_i$$$, $$$a_i + t$$$ units of water will spill onto the streets of the city. However, the explosion of one tower in a subsystem does not affect the other towers in that subsystem.
The Riddler has remote control devices to detonate each tower in the city. Every second, he can choose to detonate no more than $$$k$$$ (possibly zero) water towers. The villain wants to choose the order of detonations in such a way that the maximum amount of water flows onto the city streets (the water that flows as a result of the water discharge does not count).
Batman is concerned about the actions of his enemy, so he wants to know the maximum total amount of water that can end up on the city streets.
The first line of input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leqslant n \leqslant 10^5$$$, $$$1 \leqslant k \leqslant 10^9$$$) separated by a space - the number of subsystems of water towers in the city and the maximum number of towers that can be exploded in one second.
The next $$$n$$$ lines list the descriptions of the subsystems, the $$$i$$$-th line contains three integers separated by a space - $$$t_i$$$, $$$a_i$$$, and $$$b_i$$$ - the second when the water is discharged, the initial water level in the towers of the $$$i$$$-th subsystem, and the number of towers in the subsystem ($$$1 \leqslant t_i, b_i \leqslant 10^9$$$, $$$1 \leqslant a_i \leqslant 10^4$$$). It is guaranteed that the sum of $$$b_i$$$ for all $$$i$$$ does not exceed $$$10^9$$$.
Output a single integer - the maximum amount of water that can be on the streets of the city.
Points for each subtask are awarded only if all tests of this subtask and the necessary subtasks, as well as the tests from the statement, are passed successfully.
| Subtask | Points | Additional Constraints | Required Subtasks | Verification Information |
| 1 | 10 | the total number of towers $$$\leqslant 5$$$; $$$t_i \leqslant 5$$$ for all $$$i$$$; $$$k = 1$$$ | – | full |
| 2 | 15 | $$$k = 1$$$; $$$b_i = 1$$$ for all $$$i$$$; all $$$t_i$$$ are different | – | full |
| 3 | 10 | all $$$t_i$$$ are equal | – | full |
| 4 | 20 | $$$b_i = 1$$$ for all $$$i$$$ | 2 | full |
| 5 | 20 | $$$t_i \leqslant 10^5$$$ for all $$$i$$$ | 1 | first error |
| 6 | 25 | No additional constraints | 1 – 5 | first error |
3 2 10 3 1 2 2 1 4 1 1
19
3 1 10 3 7 2 2 3 4 1 1
69
In the first test case, there is one tower in each subsystem. The tower from the first subsystem can be detonated at the ninth second, yielding $$$3 + 9 = 12$$$ units of water; the tower from the second subsystem can be detonated at the first second, yielding $$$2 + 1 = 3$$$ units of water; the tower from the third subsystem can be detonated at the third second, yielding $$$1 + 3 = 4$$$ units of water. In total, we will obtain $$$12 + 3 + 4 = 19$$$ units of water. Note that we have obtained the maximum possible amount of water from each tower, so the answer is maximum.
In the second example, one tower from the second subsystem should be detonated at the first second, and the rest will be guaranteed to be flushed down the drain. The tower from the third subsystem can be detonated at the second or third second, but it is impossible to detonate all 7 towers from the first subsystem between the fourth and ninth seconds. Therefore, if we detonate the tower from the third subsystem at the third second, we should detonate one tower from the first subsystem at the second second. In both cases, the answer will be the same and equal to $$$((2 + 1)) + ((1 + 2)) + ((3 + 3) + (3 + 4) + \ldots + (3 + 9)) = 69$$$.
Загадочник похищает окружного прокурора Джила Колсона.
Чтобы спастись, Колсон должен отгадать три загадки. Бэтмен помогает ему отгадать первые две, но третья загадка оказалась слишком сложной. Сможете ли вы помочь ему с отгадкой?
Загадка устроена следующим образом:
- Загадочник записал и спрятал массив целых чисел $$$a$$$ длины $$$n$$$.
- Затем он циклически сдвинул его на какую-то величину $$$x$$$ влево, после чего полученный сдвиг поэлементно вычел из исходного массива.
- Полученный в результате массив $$$$$$b = [a_1 - a_{x+1}, a_2 - a_{x+2}, \ldots, a_{n} - a_{x}]$$$$$$ (иными словами, массив, в котором $$$b_i = a_i - a_{(i + x) \bmod n}$$$ для всех $$$i$$$), Загадочник сообщил Колсону.
Требуется по данному массиву $$$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$$$. Одна из возможных последовательностей действий выглядит так:
- отвезти $$$5$$$ людей из второй комнаты в четвертую (потратив $$$3$$$ прочности);
- вернуться во вторую, забрать $$$2$$$ человека из второй комнаты, и по пути в четвертую — подобрать еще $$$3$$$ человека в третьей (потратив $$$3$$$ прочности);
- дальше доехать до первой, отвезти $$$5$$$ людей из нее во вторую (за $$$5$$$ прочности), и на обратном пути в первую подвести $$$5$$$ людей из третьей в четвертую (за $$$0$$$ прочности);
- повторить последний шаг для оставшихся $$$4$$$ людей вместо $$$5$$$ (еще $$$5$$$ прочности).
Во втором примере один из оптимальных вариантов выглядит следующим образом: сначала доставить всех людей до комнаты номер $$$3$$$ (при чем люди, двигающиеся из комнаты номер $$$2$$$, должны будут взять себе попутчиков в комнате $$$1$$$), а после развести их по нужным комнатам в максимально возможных группах.