Макс — звезда уличных гонок. Сегодня перед ним длинный прямой проспект, и он хочет проехать по нему как можно дальше за отведённые $$$T$$$ секунд, пока улицы свободны.
Болид Макса описывается двумя числами: прочностью $$$P$$$ и максимальной безопасной скоростью $$$U$$$. Перед стартом болид стоит на месте, его скорость равна $$$0$$$.
Заезд идёт по секундам. В начале каждой секунды Макс делает ровно одно из трёх действий: сохраняет текущую скорость, увеличивает её на $$$1$$$ или уменьшает на $$$1$$$. Скорость не может стать отрицательной, поэтому при нулевой скорости уменьшить её нельзя. После этого в течение секунды болид проезжает столько метров, чему равна его текущая скорость (уже после изменения).
Обозначим текущую скорость через $$$S$$$. Если на этой секунде $$$S \gt U$$$, двигатель идёт вразнос: прочность падает, и значение $$$P$$$ уменьшается на $$$S - U$$$. Если в какой-то момент прочность становится отрицательной, то есть $$$P \lt 0$$$, болид выходит из строя, и заезд проигран. При $$$P = 0$$$ болид ещё держится.
Помогите Максу: какое максимальное суммарное расстояние он может проехать ровно за $$$T$$$ секунд, ни разу не выведя болид из строя?
В единственной строке заданы три целых числа $$$P$$$, $$$U$$$ и $$$T$$$ ($$$0 \le P \le 10^{18}$$$, $$$0 \le U \le 10^9$$$, $$$1 \le T \le 10^9$$$) — прочность болида, максимальная безопасная скорость и длительность заезда.
Выведите одно целое число — максимальное расстояние в метрах, которое Макс может проехать, не выведя болид из строя.
Обратите внимание, что входные данные и ответ могут быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#). Язык Python будет корректно работать и с типом int.
В данной задаче $$$10$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$10$$$ баллов. Решения, корректно работающие при $$$P, U, T \le 1000$$$, наберут не менее $$$50$$$ баллов.
2 2 3
6
3 2 6
14
В первом примере выгодно в начале каждой секунды увеличивать скорость на $$$1$$$. Тогда скорость превысит максимальную безопасную скорость на $$$1$$$ только в начале третьей секунды, от чего прочность уменьшится на $$$1$$$ и станет равной $$$1$$$, что допустимо. В таком случае болид проедет $$$1 + 2 + 3 = 6$$$.
Во втором примере один из вариантов оптимально менять скорость такой:
- В начале первой секунды увеличить скорость на $$$1$$$, она становится равной $$$1$$$.
- В начале второй секунды увеличить скорость на $$$1$$$, она становится равной $$$2$$$.
- В начале третьей секунды увеличить скорость на $$$1$$$, она становится равной $$$3$$$, после этого прочность уменьшается на $$$3 - U = 1$$$ и становится равной $$$2$$$, что допустимо.
- В начале четвертой секунды уменьшить скорость на $$$1$$$, она становится равной $$$2$$$, значит, прочность не уменьшается, так как $$$2 \leq U$$$.
- В начале пятой секунды увеличить скорость на $$$1$$$, она становится равной $$$3$$$, прочность уменьшается на $$$1$$$ и становится равной $$$1$$$, что допустимо.
- В начале шестой секунды оставить скорость прежней, она равна $$$3$$$, значит, прочность уменьшается на $$$1$$$ и становится равной $$$0$$$, что допустимо.
В таком сценарии болид проезжает $$$1 + 2 + 3 + 2 + 3 + 3 = 14$$$.
У Алисы и Боба есть $$$k$$$ массивов длины $$$n$$$. Они играют в следующую игру. Алиса выбирает любой массив, длина которого больше 1, делит его на два массива ненулевой длины и заменяет выбранный массив на два получившихся. Более формально, Алиса выбирает массив $$$[a_{1}, a_{2}, \ldots, a_{s}]$$$ и индекс $$$j$$$ ($$$1 \leq j \lt s$$$) и заменяет массив $$$[a_{1}, a_{2}, \ldots, a_{s}]$$$ на $$$[a_{1}, a_{2}, \ldots, a_{j}]$$$ и $$$[a_{j + 1}, \ldots, a_{s}]$$$. После этого Боб выбирает любой массив из существующих и удаляет его. Игра заканчивается, когда игрок не может сделать очередной ход. В конце игры останутся только массивы размера $$$1$$$, а итоговый счёт игры равен сумме оставшихся элементов. Алиса хочет минимизировать счёт игры, а Боб наоборот хочет максимизировать. Найдите счёт этой игры, если Алиса и Боб играют оптимально.
Первая строка содержит два целых числа $$$k$$$ и $$$n$$$ ($$$1 \leq k, n \leq 200\,000$$$, $$$k \cdot n \leq 200\,000$$$) — количество массивов и длину каждого массива.
Следующие $$$k$$$ строк содержат $$$n$$$ целых чисел $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$0 \leq a_{i,j} \leq 10^{9}$$$) — описание очередного массива.
В единственной строке выведите счёт игры, если Алиса и Боб играют оптимально.
Обратите внимание, что ответ может быть больше, чем возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип long long в C и C++, тип long в Java и C#, тип int64 в языке Pascal). Язык Python будет корректно работать и с типом int.
В данной задаче 25 тестов, каждый из которых оценивается в 4 балла.
Гарантируется, что решения корректно работающие при $$$1 \leq k \cdot n \leq 12$$$, наберут не менее $$$20$$$ баллов.
Гарантируется, что решения корректно работающие при $$$1 \leq k \leq 10$$$, наберут не менее $$$40$$$ баллов.
Гарантируется, что решения корректно работающие при $$$1 \leq n \leq 10$$$, наберут не менее $$$32$$$ баллов.
Обратите внимание, тесты могут удовлетворять сразу нескольким ограничениям выше.
2 21 22 3
5
3 48 5 6 66 2 2 97 6 8 9
26
В первом наборе входных данных Боб может гарантировать счёт $$$5$$$ вне зависимости от ходов Алисы. Если Алиса разделит массив $$$[1, 2]$$$ на $$$[1]$$$ и $$$[2]$$$, то Боб удалит массив $$$[1]$$$, после этого у Алисы будет единственный ход разделить $$$[2, 3]$$$ на $$$[2]$$$ и $$$[3]$$$, тогда Боб удалит любой из массивов $$$[2]$$$, и игра закончится. Если же Алиса своим первым ходом разделит массив $$$[2, 3]$$$, то Боб удалит массив $$$[1, 2]$$$, и игра также закончится со счётом $$$5$$$.
Саша очень любит пить газировку, поэтому у него есть $$$n$$$ бутылок газировки, каждая из которых может вместить любой объем напитка. Изначально в $$$i$$$-й бутылке находится $$$a_i$$$ литров газировки. Саша очень требовательный, поэтому за один глоток он может выпить ровно $$$x$$$ литров из каждой бутылки с произвольного префикса.
Более формально, чтобы сделать один глоток Саша должен выбрать целое число $$$k$$$ ($$$1 \leq k \leq n$$$), а также натуральное число $$$x$$$, такое, что min($$$a_1, \ldots, a_k$$$) $$$\geq x$$$, после чего Саша выпивает по $$$x$$$ литров газировки из первых $$$k$$$ бутылок.
Саша хочет выпить за один глоток хотя бы $$$b$$$ литров. К сожалению, сейчас в бутылках может не хватать газировки для такого глотка, поэтому Саша хочет долить газировку в какие-то бутылки, чтобы он смог сделать глоток хотя бы на $$$b$$$ литров, при этом долив как можно меньше газировки.
Поскольку Саша умеет только лишь пить газировку, он просит вас помочь ему и по данному массиву $$$a$$$ и числу $$$b$$$ посчитать минимальное количество литров, которое нужно долить, чтобы Саша смог сделать глоток на хотя бы $$$b$$$ литров.
В первой строке находятся два натуральных числа $$$n$$$ и $$$b$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq b \leq 10^9$$$) — количество бутылок газировки и количество литров, которое Саша хочет выпить.
Во второй строке находятся $$$n$$$ целых неотрицательных чисел $$$a_i$$$ ($$$0 \leq a_i \leq 10^9$$$) — изначальное количество литров в бутылках.
В единственной строке выведите ответ на задачу — минимальное число литров, которое нужно долить, чтобы Саша смог сделать глоток на хотя бы $$$b$$$ литров.
В данной задаче 20 тестов, помимо тестов из условия, каждый из них оценивается в 5 баллов.
Решения, корректно работающие при $$$n \le 500$$$, наберут не менее 20 баллов.
Дополнительно решения, корректно работающие, когда все числа $$$a_i$$$ равны, наберут не менее 10 баллов.
Дополнительно решения, корректно работающие, когда $$$a_{i} \leq a_{i+1}$$$ для всех $$$i$$$ (массив неубывающий), наберут не менее 10 баллов.
Дополнительно решения, корректно работающие, когда $$$a_{i+1} \leq a_i$$$ для всех $$$i$$$ (массив невозрастающий), наберут не менее 30 баллов.
5 103 5 3 0 1
2
6 43 2 1 5 0 3
0
В первом примере можно долить по одному литру в первую и третью бутылку, после чего массив станет равным $$$[4, 5, 4, 0, 1]$$$. Далее Саша может сделать глоток с префикса размера $$$3$$$ с $$$x = 4$$$, суммарно за глоток он выпьет $$$3 \cdot 4 = 12 \geq b$$$.
Во втором примере можно, не доливая газировки, сделать глоток из префикса размера $$$4$$$ с $$$x = 1$$$. Тогда Саша выпьет $$$4 \cdot 1 = 4 \geq b$$$.
Вам дан строго возрастающий массив $$$a$$$ длины $$$n$$$, состоящий из положительных целых чисел. Также вам дано $$$q$$$ запросов, $$$i$$$-й из которых определяется двумя целыми числами $$$l_i$$$, $$$r_i$$$ ($$$1 \leq l_i \lt r_i \leq n$$$). Ответ на $$$i$$$-й запрос — минимальное значение $$$a_c \bmod a_b$$$ (остаток от деления $$$a_c$$$ на $$$a_b$$$) по всем $$$l_i \leq b \lt c \leq r_i$$$.
В первой строке находится единственное целое число $$$n$$$ ($$$2 \leq n \leq 10^6$$$).
На второй строке находится $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \leq a_i \leq 10^6$$$). Гарантируется, что $$$a_{i+1} \gt a_i$$$, то есть массив строго возрастает.
В третьей строке находится единственное целое число $$$q$$$ ($$$1 \leq q \leq 10^6$$$).
В следующих $$$q$$$ строках даны по два числа, в $$$i$$$-й из которых находятся целые числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \leq l_i \lt r_i \leq n$$$) — описание $$$i$$$-го запроса.
Выведите $$$q$$$ строк, в $$$i$$$-й ответ на $$$i$$$-й запрос.
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, что прохождение тестов из условия не требуется для некоторых групп. Итоговый балл за каждую группу равняется максимальному баллу, полученному за эту группу тестов по всем отправленным посылкам.
| |c|c|} Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | 0 | Примеры из условия | — | полная проверка |
| 1 | 12 | $$$n, q, a_i \leq 500$$$ | 0 | первая ошибка |
| 2 | 17 | $$$n, q, a_i \leq 3000$$$ | 0–1 | первая ошибка |
| 3 | 26 | $$$n, q, a_i \leq 2 \times 10^5$$$ | 0–2 | первая ошибка |
| 4 | 25 | $$$n, q, a_i \leq 625000$$$ | 0–3 | первая ошибка |
| 5 | 9 | $$$l_i = 0$$$ | — | первая ошибка |
| 6 | 11 | Без дополнительных ограничений | 0–5 | первая ошибка |
42 3 5 721 42 3
1 2
83 8 10 11 21 23 25 3071 81 77 82 73 83 61 6
0 0 5 1 0 1 0
Рассмотрим массив $$$a = [2, 3, 5, 7]$$$ ($$$n = 4$$$) и два запроса.
Запрос $$$1$$$: $$$l = 1$$$, $$$r = 4$$$. Разрешены все пары $$$(b, c)$$$, для которых $$$1 \le b \lt c \le 4$$$. Вычислим $$$a_c \bmod a_b$$$ для каждой пары:
- $$$(b, c) = (1, 2)$$$: $$$a_2 \bmod a_1 = 3 \bmod 2 = 1$$$;
- $$$(b, c) = (1, 3)$$$: $$$a_3 \bmod a_1 = 5 \bmod 2 = 1$$$;
- $$$(b, c) = (1, 4)$$$: $$$a_4 \bmod a_1 = 7 \bmod 2 = 1$$$;
- $$$(b, c) = (2, 3)$$$: $$$a_3 \bmod a_2 = 5 \bmod 3 = 2$$$;
- $$$(b, c) = (2, 4)$$$: $$$a_4 \bmod a_2 = 7 \bmod 3 = 1$$$;
- $$$(b, c) = (3, 4)$$$: $$$a_4 \bmod a_3 = 7 \bmod 5 = 2$$$.
Запрос $$$2$$$: $$$l = 2$$$, $$$r = 3$$$. Здесь единственная допустимая пара $$$(b, c) = (2, 3)$$$: $$$a_3 \bmod a_2 = 5 \bmod 3 = 2$$$. Поэтому ответ на второй запрос равен $$$2$$$.