В новом вагоне для поезда «Ласточка» нумерация мест показана на схеме:
| $$$\fbox{ 1 }$$$ $$$\fbox{ 5 }$$$ | $$$\fbox{13}$$$ $$$\fbox{17}$$$ | $$$\fbox{25}$$$ $$$\fbox{29}$$$ | ... |
| $$$\fbox{ 2 }$$$ $$$\fbox{ 6 }$$$ | $$$\fbox{14}$$$ $$$\fbox{18}$$$ | $$$\fbox{26}$$$ $$$\fbox{30}$$$ | ... |
| $$$\fbox{ 4 }$$$ $$$\fbox{ 8 }$$$ | $$$\fbox{16}$$$ $$$\fbox{20}$$$ | $$$\fbox{28}$$$ $$$\fbox{32}$$$ | ... |
| проход | |||
| $$$\fbox{10}$$$ $$$\fbox{12}$$$ | $$$\fbox{22}$$$ $$$\fbox{24}$$$ | $$$\fbox{34}$$$ $$$\fbox{36}$$$ | ... |
| $$$\fbox{ 9 }$$$ $$$\fbox{11}$$$ | $$$\fbox{21}$$$ $$$\fbox{23}$$$ | $$$\fbox{33}$$$ $$$\fbox{35}$$$ | ... |
Согласно схеме, с одной стороны от прохода располагаются боксы по 6 мест, с другой стороны — боксы по 4 места. Все нечётные места расположены у стен вагона (у окон). При этом некоторых мест не существует — например, нет мест 3, 7, 15, 19 и так далее. Закономерность, по которой нумерация продолжается дальше, можно понять из схемы.
Вася купил билет на место номер $$$x$$$. Перечислите другие места в том же боксе, что и место $$$x$$$, чтобы Петя выбрал себе место по соседству с Васей.
Вводится единственное целое число $$$x$$$ — номер Васиного места ($$$1 \leq x \leq 10^9$$$).
Выведите несколько целых чисел — все другие номера мест, расположенных в том же боксе, что и место $$$x$$$. Номера требуется вывести в возрастающем порядке. Если Вася ошибся, когда сообщал номер Пете, и место с номером $$$x$$$ не существует, то выведите -1.
Решения, работающие при $$$x \le 36$$$, будут оцениваться в 50 баллов.
6
1 2 4 5 8
21
22 23 24
3
-1
Последовательность Фибоначчи начинается с чисел $$$F_1=1$$$, $$$F_2=1$$$. Каждое следующее число равно сумме двух предыдущих. Индексация начинается с единицы.
Нужно построить ряд из $$$n$$$ чисел с одним перезапуском после позиции $$$i$$$: то есть сначала записываются $$$i$$$ первых чисел Фибоначчи ($$$ 2 \leq i \leq n - 2$$$), а затем последовательность начинается заново с $$$F_1$$$ и $$$F_2$$$ и продолжается по тому же правилу, пока в ряду не станет ровно $$$n$$$ чисел.
Выберите значение $$$i$$$ так, чтобы сумма всех $$$n$$$ чисел была наименьшей. Если несколько позиций дают одинаковую сумму, выберите наименьшее $$$i$$$.
Одно целое число $$$n$$$ ($$$6 \le n \le 80$$$).
В первой строке выведите выбранную позицию $$$i$$$. Во второй строке выведите $$$n$$$ чисел полученного ряда через пробел.
Каждый пройденный тест даёт одинаковое количество баллов, полное решение получает 100 баллов.
6
3 1 1 2 1 1 2
7
3 1 1 2 1 1 2 3
Обратите внимание, что ответ может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битный целочисленный тип данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#). В языке Python ничего дополнительно делать не требуется.
Безумный гений доктор Шпунтик собирает армию боевых роботов-ёжиков из старого металлолома. Перед ним лежит огромная железная конструкция: $$$n$$$ круглых деталей-шестерёнок, которые соединены $$$m$$$ стальными прутьями (каждый прут соединяет ровно две детали). Чтобы активировать одного робота-ёжика, доктору нужно выбрать ровно одну деталь и несколько стальных прутьев, приваренных к этой детали (они станут «иголками»). Для того чтобы робот-ёжик считался правильным и готовым к работе, у него должно быть как минимум три иголки.
Шпунтику не нравится однообразная работа, поэтому каждый его робот должен быть уникальным. Два робота-ёжика считаются различными, если для них выбраны разные детали, или если у них отличается хотя бы одна иголка (выбраны разные наборы прутьев, торчащих из детали). Доктор хочет вычислить, сколько всего различных правильных роботов-ёжиков скрыто в его конструкции. Ёжиков настолько много, что без помощи Шпунтику не справиться. Так как количество роботов может быть очень большим, выведите ответ по модулю $$$10^9 + 7$$$.
Формально: вам дан неориентированный граф. Требуется вычислить количество подграфов вида «ёжик»: в них центральная вершина связана рёбрами с несколькими другими количеством не менее трёх, и других рёбер нет. Обратите внимание: в исходном графе вершины – концы «иголок» «ёжика» могут быть связаны рёбрами, просто при выделении подграфа «ёжик» они в него не включаются. «Ёжики» считаются различными, если есть хотя бы одна вершина, присутствующая в одном из них и отсутствующая в другом. Вам требуется вычислить остаток от деления количества «ёжиков» на число $$$10^9 + 7.$$$
В первой строке заданы два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$n - 1 \le m \le 3 \cdot 10^5$$$) — количество деталей и прутьев в конструкции соответственно. В следующих $$$m$$$ строках содержатся описания прутьев. Каждая строка содержит два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — начало и конец прута. Гарантируется, что конструкция связная и описания прутьев не повторяются.
Выведите одно целое число — количество различных роботов-ёжиков в заданной конструкции по модулю $$$10^9 + 7$$$ (то есть остаток от деления на $$$10^9 + 7$$$).
Подзадача 1 (до 20 баллов): $$$n, m \le 15$$$
Подзадача 2 (до 24 баллов): $$$n, m \le 2000$$$
Подзадача 3 (до 56 баллов): $$$n, m \le 3 \cdot 10^5$$$
4 31 21 31 4
1
5 41 21 31 41 5
5
Примечание по языку Python. Два числа, записанных через пробел, можно прочитать так:
n, m = map(int, input().split())
Дана информация о прибыли IT-компании за $$$n$$$ подряд идущих дней. Для красивого отчёта требуется выбрать из них максимальное количество дней так, чтобы выполнялись следующие два условия:
В первой строке входных данных записано целое число $$$n$$$ ($$$1 \le n \le 10^4$$$).
В следующих $$$n$$$ строках записаны целые числа в диапазоне от $$$0$$$ до $$$10^5$$$ — прибыль компании в каждый из $$$n$$$ дней.
Выведите одно целое число — максимальное количество дней в отчёте.
Подзадача 1 (до 50 баллов): $$$n \le 10$$$
Подзадача 2 (до 50 баллов): $$$n \le 5000$$$
74213105
3
3321
1
В первом примере можно выбрать для отчёта дни с номерами 2, 4, 7.
Бабушка хранит варенье в длинной ёмкости, разделённой на $$$N$$$ последовательных секций. В секции с номером $$$i$$$ находится $$$a_i$$$ единиц варенья.
Бабушка выбирает непустой участок из подряд идущих секций — с $$$i$$$-й по $$$j$$$-ю включительно — и сливает из него всё варенье в банки (она выполняет это один раз). Границами участка могут служить перегородки между секциями или края ёмкости.
Объём одной банки равен $$$M$$$. Бабушка заполняет только целые банки, а варенье, которого не хватило на следующую полную банку, выбрасывает.
Найдите минимальное количество варенья, которое придётся выбросить.
В первой строке записаны два целых числа $$$N$$$ и $$$M$$$ ($$$1 \le N \le 2\,000\,000$$$, $$$N \lt M \le 10\,000\,001$$$).
Во второй строке записаны $$$N$$$ целых чисел $$$a_1, a_2, \ldots, a_N$$$ ($$$1 \le a_i \le 10^9$$$).
Выведите одно целое число — минимальное количество выброшенного варенья.
Подзадача 1 (до 30 баллов): $$$N \le 2\,000$$$.
Подзадача 2 (до 30 баллов): $$$N \le 200\,000$$$.
Подзадача 3 (до 40 баллов): без дополнительных ограничений.
3 105 8 6
3
1 22
0
1 100000011000000000
9999901
В задачу были добавлены дополнительные тесты, которых не было во время олимпиады.
Примечание для пишущих на Python. Набор целых чисел, записанных через пробел, можно прочитать так:
a = [int(x) for x in input().split()]
Примечание по быстрому вводу. В последней подзадаче нужно вводить большой объём данных. В некоторых языках для этого нужно использовать специальные способы ускорения ввода.
В языке C++ достаточно добавить в начало функции main следующие строки:
ios_base::sync_with_stdio(false);
cin.tie(0);
В Java используйте 'BufferedInputStream' и считывайте целые числа из байтов. 'Scanner' на большом входе может работать слишком медленно.
В C# используйте 'BufferedStream' поверх 'Console.OpenStandardInput()' и считывайте целые числа из байтов. Чтение всей строки через 'Console.ReadLine().Split()' создаёт много строк и может потребовать слишком много времени и памяти.
Пишущим на языке Python рекомендуется сдавать эту задачу на PyPy.