Задача 5. Три сына ≡

Условие

Во владениях короля Флатландии находится прямая дорога длиной N километров, по одну сторону от которой расположен огромный лесной массив. Король Флатландии проникся идеями защиты природы и решил превратить свой лесной массив в заповедник. Но сыновья стали сопротивляться: ведь им хотелось получить эти земли в наследство.

У короля три сына: младший, средний и старший. Король решил, что в заповедник не войдут участки лесного массива, которые он оставит сыновьям в наследство. При составлении завещания король хочет, чтобы для участков выполнялись следующие условия:

• каждый участок должен иметь форму квадрата, длина стороны которого выражается целым положительным числом. Одна из сторон каждого квадрата должна лежать на дороге. Пусть участки имеют размеры A × A, B × B и C × C;
• стороны квадратов должны полностью покрывать дорогу: величина A + B + C должна быть равна N;
• участок младшего сына должен быть строго меньше участка среднего сына, а участок среднего сына должен, в свою очередь, быть строго меньше участка старшего сына, то есть должно выполняться неравенство A < B < C;
• суммарная площадь участков A² + B² + C² должна быть минимальна.

Требуется написать программу, которая по заданной длине дороги определяет размеры участков, которые следует выделить сыновьям короля.

Формат входного файла

Входной файл содержит одно целое число N.

Формат выходного файла

Выходной файл должен содержать три целых положительных числа, разделенных пробелами: A, B и C — длины сторон участков, которые следует выделить младшему, среднему и старшему сыну, соответственно. Если оптимальных решений несколько, разрешается вывести любое.

Ограничения

6 ≤ N ≤ 10⁹

Пояснение к примеру

Описание подзадач и системы оценивания

В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Подзадача 1 (25 баллов)

N ≤ 50

Подзадача 2 (25 баллов)

N ≤ 2000

Подзадача 3 (25 баллов)

N ≤ 40 000

Подзадача 4 (25 баллов)

N ≤ 10⁹

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

6

1 2 3

Задача 6. Гипершашки ≡

Условие

Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал A баллов, второй — B, а третий C, то говорят, что игра закончилась со счетом A:B:C.

Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в K раз.

После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из N карточек, на которых написаны числа x₁, x₂, …, x_N. Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.

Требуется написать программу, которая по числу K и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.

Формат входного файла

Первая строка входного файла содержит два целых числа: N и K. Вторая строка входного файла содержит N целых чисел x₁, x₂, …, x_N.

Формат выходного файла

Выходной файл должен содержать одно целое число — искомое количество различных вариантов счета.

Ограничения

3 ≤ N ≤ 100 000; 1 ≤ K ≤ 10⁹; 1 ≤ x_i ≤ 10⁹

Пояснение к примеру

В приведенном примере Андрей сможет показать следующие варианты счета: 1:1:2, 1:2:1, 2:1:1, 1:2:2, 2:1:2, 2:2:1, 2:2:3, 2:3:2, 3:2:2. Другие тройки чисел, которые можно составить с использованием имеющихся карточек, не удовлетворяют заданному условию, что баллы любых двух игроков различаются не более чем в k = 2 раза.

Описание подзадач и системы оценивания

В этой задаче четыре подзадачи. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Внимание! Тест из примера не подходит под ограничения для подзадач 1 и 3, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только каких-либо из подзадач 1 и 3.

Подзадача 1 (15 баллов)

3 ≤ N ≤ 100 000; K = 1; 1 ≤ x_i ≤ 100 000

Подзадача 2 (23 балла)

3 ≤ N ≤ 100; 1 ≤ K ≤ 100; 1 ≤ x_i ≤ 100

Подзадача 3 (30 баллов)

3 ≤ N ≤ 100 000; 1 ≤ K ≤ 10⁹; 1 ≤ x_i ≤ 10⁹; все x_i различны

Подзадача 4 (32 балла)

3 ≤ N ≤ 100 000; 1 ≤ K ≤ 10⁹; 1 ≤ x_i ≤ 10⁹

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

5 2
1 1 2 2 3

9

Задача 7. Интересные числа ≡

Условие

Софья считает число интересным, если его цифры идут в неубывающем порядке. Например, числа 123, 1111 или 888999 — интересные.

Софья заинтересовалась, сколько существует интересных положительных чисел, лежащих в диапазоне от L до R включительно. Это число может оказаться довольно большим для больших L и R, поэтому Софья хочет найти остаток от деления этого числа на 10⁹ + 7.

Требуется написать программу, которая по заданным L и R определяет количество интересных чисел, лежащих в диапазоне от L до R включительно, и выводит остаток от деления этого числа на 10⁹ + 7.

Формат входного файла

Входной файл содержит две строки. Первая строка содержит число L, вторая строка содержит число R.

Формат выходного файла

Выходной файл должен одно целое число — остаток от деления количества интересных чисел, лежащих в диапазоне от L до R включительно, на 10⁹ + 7.

Ограничения

1 ≤ L ≤ R ≤ 10¹⁰⁰

Описание подзадач и системы оценивания

Подзадача 1 (21 балл)

L = 1, R ≤ 1000.

Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

Подзадача 2 (22 балла)

1 ≤ L ≤ R ≤ 10¹⁸.

В этой подзадаче 11 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.

Подзадача 3 (24 балла)

L = 1, R = 10^k для некоторого целого k, 2 ≤ k ≤ 100.

В этой подзадаче 8 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Подзадача 4 (33 балла)

1 ≤ L ≤ R ≤ 10¹⁰⁰.

В этой подзадаче 11 тестов, каждый тест оценивается в 3 балла. Баллы за каждый тест начисляются независимо.

Получение информации о результатах окончательной проверки

По запросу сообщается результат окончательной проверки на каждом тесте.

Примеры тестов

1
100

54

Задача 8. Гармоническая последовательность ≡

Условие

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел a₁, a₂, …, a_N гармоничной, если каждое число, кроме a₁ и a_N, равно сумме соседних: a₂ = a₁ + a₃, a₃ = a₂ + a₄, …, a_N − 1 = a_N − 2 + a_N. Например, последовательность [1, 2, 1, −1] является гармоничной, поскольку 2 = 1 + 1, и 1 = 2 + (−1).

Рассмотрим последовательности равной длины: A = [a₁, a₂, …, a_N] и B = [b₁, b₂, …, b_N]. Расстоянием между этими последовательностями будем называть величину N(A, B) = |a₁ − b₁| + |a₂ − b₂| + ⋯ + |a_N − b_N|. Например, d([1, 2, 1, −1], [1, 2, 0, 0]) = |1 − 1| + |2 − 2| + |1 − 0| + |−1 − 0| = 0 + 0 + 1 + 1 = 2.

В конце лекции профессор написал на доске последовательность из N целых чисел B = [b₁, b₂, …, b_N] и попросил студентов в качестве домашнего задания найти гармоничную последовательность A = [a₁, a₂, …, a_N], такую, что d(A, B) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние d(A, B).

Требуется написать программу, которая по заданной последовательности B определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность A.

Формат входного файла

Первая строка входного файла содержит целое число N — количество элементов в последовательности.

Вторая строка содержит n целых чисел b₁, b₂, …, b_N.

Формат выходного файла

Выходной файл должна содержать одно целое число: минимальное возможное расстояние от последовательности во входном файле до гармоничной последовательности.

Ограничения

3 ≤ N ≤ 300 000; −10⁹ ≤ b_i ≤ 10⁹

Пояснения к примеру

В приведенном примере оптимальной является, например, гармоничная последовательность [1, 2, 1, −1].

Описание подзадач и системы оценивания

В этой задаче пять подзадач. Баллы за подзадачу начисляются только в случае, если все тесты для данной подзадачи пройдены.

Внимание! Тест из примера не подходит под ограничения для подзадачи 1, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только подзадачи 1.

Подзадача 1 (14 баллов)

N = 3, −10 ≤ b_i ≤ 10

Подзадача 2 (14 баллов)

3 ≤ N ≤ 500, −100 ≤ b_i ≤ 100

Подзадача 3 (16 баллов)

3 ≤ N ≤ 100 000, −100 ≤ b_i ≤ 100

Подзадача 4 (16 баллов)

3 ≤ N ≤ 1000, −10⁹ ≤ b_i ≤ 10⁹

Подзадача 5 (40 баллов)

3 ≤ N ≤ 300 000, −10⁹ ≤ b_i ≤ 10⁹

Получение информации о результатах окончательной проверки

По запросу сообщается баллы за каждую подзадачу.

Примеры тестов

4
1 2 0 0

2