Интернет-магазин быстрой доставки продуктов представляет новую позицию: можно купить набор из семи бананов разной спелости, что первый банан станет спелым в какой-то из дней, второй — в следующий за ним день, третий — на следующий за вторым бананом день, и так далее. Более формально, в наборе должно быть семь бананов, при этом первый банан станет спелым в день $$$d$$$, второй — в день $$$d + 1$$$, третий — в день $$$d + 2$$$, четвертый — в день $$$d + 3$$$, пятый — в день $$$d + 4$$$, шестой — в день $$$d + 5$$$, и седьмой — в день $$$d + 6$$$.
На склад завезли партию бананов. Судя по накладной, вам известно, что каждый банан станет спелым в один из следующих $$$n$$$ дней, и для каждого дня $$$i$$$ от 1 до $$$n$$$, вам известно, что $$$a_i$$$ из завезенных бананов станут спелыми в день $$$i$$$.
Ваша задача сделать как можно больше наборов бананов. Посчитайте, какое наибольшее число наборов бананов можно сделать, также посчитайте сколько бананов останется без наборов в таком случае.
В первой строке задано целое число $$$n$$$ — число дней из накладной ($$$7 \le n \le 100$$$).
Во второй строке задано $$$n$$$ целых чисел $$$a_i$$$ — число бананов, которые станут спелыми в день $$$i$$$ ($$$0 \le a_i \le 10^9$$$).
Выведите два целых числа: наибольшее возможное число наборов бананов и сколько бананов при этом останется нераспределенными по наборам.
| Подзадача | Баллы | Ограничения |
| 1 | 30 | $$$n = 7$$$; $$$a_i \le 100$$$ |
| 2 | 45 | $$$n \le 100$$$; $$$a_i \le 1000$$$ |
| 3 | 25 | $$$n \le 100$$$; $$$a_i \le 10^9$$$ |
9 4 3 5 4 5 4 4 5 2
4 8
7 2 3 3 3 2 2 3
2 4
В первом примере, например, можно сформировать два набора с $$$d = 1$$$, один набор с $$$d = 2$$$ и один набор с $$$d = 3$$$. Заметим, что для этого примера есть и другие способы сформировать 4 набора.
Во втором примере, можно сформировать два набора с $$$d = 1$$$.
Недавно Маня узнала, что перестановка — это последовательность из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$2,3,1,5,4$$$ — перестановка, но $$$1,2,2$$$ не перестановка ($$$2$$$ встречается дважды) и $$$1,3,4$$$ тоже не перестановка ($$$n=3$$$, но в последовательности встречается $$$4$$$).
Маня начала выписывать случайные перестановки одну под другой. Когда она выписала $$$n-1$$$ перестановку, Маня заметила, что столбцы в получающейся таблице чисел тоже могут оказаться перестановками из $$$n$$$ чисел, когда она выпишет $$$n$$$-ю перестановку. В каждом столбце будет по $$$n$$$ чисел от $$$1$$$ до $$$n$$$, но не все столбцы будут являться корректными перестановками. Тогда Маня решила, что хочет дописать $$$n$$$-ю перестановку так, чтобы количество столбцов-перестановок было как можно больше.
Ваша задача — узнать, какое наибольшее число столбцов может оказаться перестановками после добавления $$$n$$$-й перестановки; и сколько существует перестановок, выписав которые, можно получить наибольшее число столбцов-перестановок.
Первая строка содержит число $$$n$$$ — длину перестановок ($$$2 \le n \le 1000$$$).
Каждая из следующих $$$n-1$$$ строк содержит перестановку длины $$$n$$$ — $$$n$$$ чисел от $$$1$$$ до $$$n$$$.
Выведите два числа через пробел — наибольшее число столбцов, которые могут оказаться перестановками после добавления перестановки, и число перестановок, которые можно добавить для достижения наибольшего числа столбцов-перестановок, по модулю $$$10^9 + 7$$$.
| Подзадача | Баллы | Ограничения |
| 1 | 20 | $$$n \le 7$$$ |
| 2 | 45 | $$$n \le 300$$$ |
| 3 | 35 | $$$n \le 1000$$$ |
4 1 2 3 4 4 1 2 3 3 2 4 1
2 4
4 1 2 3 4 1 2 4 3 2 1 4 3
0 24
В первом примере в первый и четвертый столбцы нужно дописать $$$2$$$, чтобы они стали перестановками. В третий столбец можно дописать $$$1$$$. Тогда, если Маня добавит одну из перестановок:
$$$2,3,1,4$$$;
$$$2,4,1,3$$$;
$$$3,4,1,2$$$;
$$$4,3,1,2$$$;
получится два столбца-перестановки. Получить три столбца-перестановки в этом примере не получится, так как в дописанной перестановке не может быть два числа $$$2$$$.
Во втором примере ни один из столбцов не будет являться перестановкой, какую бы перестановку Маня не дописала. Значит, наибольшее число столбцов-перестановок равно $$$0$$$, и его можно получить добавив любую из $$$24$$$ перестановок.
Азату стало интересно, сколько существует пар целочисленных корней $$$(x_1, x_2)$$$, которые являются корнями уравнения $$$x^2 + bx + c = 0$$$, где сумма коэффициентов $$$b$$$ и $$$c$$$ лежит между $$$l$$$ и $$$r$$$, то есть $$$l \le b + c \le r$$$ ($$$b$$$, $$$c$$$, $$$l$$$, $$$r$$$ — целые числа). Пары корней $$$(x_1, x_2)$$$ и $$$(x_2, x_1)$$$ считаются одинаковыми.
Помогите Азату узнать ответ на его задачку.
В первой строке входных данных находятся два целых числа $$$l$$$, $$$r$$$ ($$$-10^{12} \le l \le r \le 10^{12}$$$; $$$r - l \le 10^6$$$).
Выведите единственное число — количество пар целых корней. Если количество подходящих пар корней бесконечно, выведите -1.
| Подзадача | Баллы | Ограничения |
| $$$1$$$ | $$$8$$$ | $$$l = r$$$ и $$$|l| \le 10^3$$$ |
| $$$2$$$ | $$$9$$$ | $$$r - l \le 2 \cdot 10^3$$$ и $$$|l|, |r| \le 10^3$$$ |
| $$$3$$$ | $$$13$$$ | $$$l = r$$$ и $$$|l| \le 10^6$$$ |
| $$$4$$$ | $$$20$$$ | $$$r - l \le 2 \cdot 10^2$$$ и $$$|l|, |r| \le 10^{8}$$$ |
| $$$5$$$ | $$$16$$$ | $$$l = r$$$ и $$$|l| \le 10^{12}$$$ |
| $$$6$$$ | $$$34$$$ | $$$r - l \le 10^6$$$ и $$$|l|, |r| \le 10^{12}$$$ |
7 7
4
-2 -2
1
-7 -3
13
Когда $$$l = r = 7$$$, подходит четыре пары корней $$$(2, 9), (0, -7), (3, 5), (-1, -3)$$$.
При паре корней 2 и 9 уравнение примет вид $$$x^2 - 11 \cdot x + 18 = 0$$$.
При паре корней 0 и -7 уравнение примет вид $$$x^2 + 7 \cdot x + 0 = 0$$$.
При паре корней 3 и 5 уравнение примет вид $$$x^2 - 8 \cdot x + 15 = 0$$$.
При паре корней $$$-1$$$ и $$$-3$$$ уравнение примет вид $$$x^2 + 4 \cdot x + 3 = 0$$$.
Во всех случаях сумма $$$b$$$ и $$$c$$$ равна $$$7$$$.
Вам дан массив из целых неотрицательных чисел $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$. Найдите количество троек чисел $$$1 \le i \lt j \lt k \le n$$$, таких что $$$(a_i \oplus a_j) \lt (a_j \oplus a_k)$$$, где $$$\oplus$$$ — это операция побитового исключающего ИЛИ (XOR).
В первой строке дано одно целое число $$$n$$$ — количество элементов в массиве ($$$3 \le n \le 200\,000$$$).
Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ — элементы массива ($$$0 \le a_i \le 10^{18}$$$).
Выведите одно целое число — количество искомых троек.
| Подзадача | Баллы | Ограничения |
| $$$1$$$ | $$$17$$$ | $$$n \le 100$$$ |
| $$$2$$$ | $$$19$$$ | $$$n \le 3\,000$$$ |
| $$$3$$$ | $$$18$$$ | $$$n \le 30\,000$$$, $$$a_i \le 50$$$ |
| $$$4$$$ | $$$22$$$ | $$$n \le 30\,000$$$ |
| $$$5$$$ | $$$24$$$ | Без дополнительных ограничений |
3 0 1 2
1
4 0 1 2 3
2
5 6 1 17 3 11
7
10 0 1 2 3 4 5 6 7 8 9
84