Подразделы

Другие разделы

Дата и время

09/04/2025 05:49:57

Авторизация

Задачи 2 тура регионального олимпиады по информатике 2016

5. Три сына

Ограничения: время – 1s/2s, память – 256MiB Ввод: division.in или стандартный ввод Вывод: division.out или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Во владениях короля Флатландии находится прямая дорога длиной

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

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

каждый участок должен иметь форму квадрата, длина стороны которого выражается целым положительным числом. Одна из сторон каждого квадрата должна лежать на дороге. Пусть участки имеют размеры $a times a$ , $b times b$ и $c times c$ ;
стороны квадратов должны полностью покрывать дорогу: величина $a + b + c$ должна быть равна $n$ ;
участок младшего сына должен быть строго меньше участка среднего сына, а участок среднего сына должен, в свою очередь, быть строго меньше участка старшего сына, то есть должно выполняться неравенство $a < b < c$ ;
суммарная площадь участков $a^2 + b^2 + c^2$ должна быть минимальна.

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

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

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

$n$ (

$6 ≤ n ≤ 10^9$ ).

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

Выходной файл должен содержать три целых положительных числа, разделенных пробелами:

$a$ ,

$b$ и

$c$ – длины сторон участков, которые следует выделить младшему, среднему и старшему сыну, соответственно. Если оптимальных решений несколько, разрешается вывести любое.

Пример ввода

Пример вывода

1 2 3

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

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

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

$n ≤ 50$ .

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

$n ≤ 2000$ .

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

$n ≤ 40 000$ .

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

$n ≤ 10^9$ .

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

Источник: региональный этап Всероссийской олимпиады по информатике 2015/2016, http://neerc.ifmo.ru/school/

6. Гипершашки

Ограничения: время – 1s/2s, память – 256MiB Ввод: game.in или стандартный ввод Вывод: game.out или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

$a$ баллов, второй –

$b$ , а третий –

$c$ , то говорят, что игра закончилась со счетом

$a:b:c$ .

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

$k$ раз.

После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из

$n$ карточек, на которых написаны числа

$x_1,\ x_2,\ …,\ x_n$ . Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.

Требуется написать программу, которая по числу

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

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

Первая строка входного файла содержит два целых числа:

$n$ и

$k$ (

$3 ≤ n ≤ 100 000$ ,

$1 ≤ k ≤ 10^9$ ).

Вторая строка входного файла содержит n целых чисел

$x_1,\ x_2,\ …,\ x_n$ (

$1 ≤ x_i ≤ 10^9$ ).

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

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

Пример ввода

5 2
1 1 2 2 3

Пример вывода

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

В приведенном примере Андрей сможет показать следующие варианты счета: 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^9$ ,

$1 ≤ x_i ≤ 10^9$ , все

$x_i$ различны.

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

$3 ≤ n ≤ 100 000$ ,

$1 ≤ k ≤ 10^9$ ,

$1 ≤ x_i ≤ 10^9$

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

Источник: региональный этап Всероссийской олимпиады по информатике 2015/2016, http://neerc.ifmo.ru/school/

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

Ограничения: время – 1s/2s, память – 256MiB Ввод: numbers.in или стандартный ввод Вывод: numbers.out или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

Софья заинтересовалась, сколько существует интересных положительных чисел, лежащих в диапазоне от

$L$ до

$R$ включительно. Это число может оказаться довольно большим для больших

$L$ и

$R$ , поэтому Софья хочет найти остаток от деления этого числа на

$10^9\ +\ 7$ .

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

$L$ и

$R$ определяет количество интересных чисел, лежащих в диапазоне от

$L$ до

$R$ включительно, и выводит остаток от деления этого числа на

$10^9\ +\ 7$ .

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

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

$L$ , вторая строка содержит число

$R$ (

$1 ≤ L ≤ R ≤ 10^{100}$ ).

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

Выходной файл должен одно целое число – остаток от деления количества интересных чисел, лежащих в диапазоне от

$L$ до

$R$ включительно, на

$10^9 + 7$ .

Пример ввода

1
100

Пример вывода

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

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

$L\ =\ 1$ ,

$R ≤ 1000$

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

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

$1 ≤ L ≤ R ≤ 10^{18}$

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

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

$L\ =\ 1$ ,

$R\ =\ 10^k$ для некоторого целого

$k$ ,

$2\ ≤ k ≤ 100$ .

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

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

$1 ≤ L ≤ R ≤ 10^{100}$

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

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

Источник: региональный этап Всероссийской олимпиады по информатике 2015/2016, http://neerc.ifmo.ru/school/

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

Ограничения: время – 1s/2s, память – 256MiB Ввод: sequence.in или стандартный ввод Вывод: sequence.out или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

Профессор называет последовательность целых чисел

$a_1,\ a_2,\ …,\ a_n$ гармоничной, если каждое число, кроме

$a_1$ и

$a_n$ , равно сумме соседних:

$a_2\ =\ a_1\ +\ a_3$ ,

$a_3\ =\ a_2\ +\ a_4$ , …,

$a_{n-1}\ =\ a_{n-2}\ +\ a_n$ . Например, последовательность

$[1,\ 2,\ 1,\ -1]$ является гармоничной, поскольку

$2\ =\ 1\ +\ 1$ , и

$1 = 2\ +\ (-1)$ .

Рассмотрим последовательности равной длины:

$A\ =\ [a_1,\ a_2,\ …,\ a_n]$ и

$B\ =\ [b_1,\ b_2,\ …,\ b_n]$ . Расстоянием между этими последовательностями будем называть величину

$d(A, B) = |a_1\ -\ b_1|\ +\ |a_2\ -\ b_2|\ +\ …\ +\ |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_1,\ b_2,\ …,\ b_n]$ и попросил студентов в качестве домашнего задания найти гармоничную последовательность

$A\ =\ [a_1,\ a_2,\ ..,\ a_n]$ , такую, что

$d(A, B)$ минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние

$d(A,\ B)$ .

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

$B$ определяет, на каком минимальном расстоянии от последовательности B найдется гармоничная последовательность

$A$ .

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

Первая строка входного файла содержит целое число

$n$ - количество элементов в последовательности (

$3 ≤ n ≤ 300 000$ ).

Вторая строка содержит

$n$ целых чисел

$b_1,\ b_2,\ …,\ b_n$ (

$-10^9 ≤ b_i ≤ 10^9$ ).

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

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

Пример ввода

4
1 2 0 0

Пример вывода

Пояснение к примеру В приведенном примере оптимальной является, например, гармоничная последовательность [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^9 ≤ b_i ≤ 10^9$

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

$3 ≤ n ≤ 300 000$ ,

$-10^9 ≤ b_i ≤ 10^9$

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

Источник: региональный этап Всероссийской олимпиады по информатике 2015/2016, http://neerc.ifmo.ru/school/

01/02/2016	Региональный этап олимпиады школьников по информатике. II тур. (8)
10/10/2023	Занятие 222222 (проводит damir) (A)

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Задачи 2 тура регионального олимпиады по информатике 2016

5. Три сына

6. Гипершашки

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

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