Начало
Соревнования
Задачи 2 тура регионального олимпиады по информатике 2016
5. Три сына
Индукция и другие математические методыОлимпиадные задачи на русском языке
| 01/02/2016 | Региональный этап олимпиады школьников по информатике. II тур. (5) |
| 09/11/2022 | Тренировка (повторение) (проводит BOGAT) (F) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: division.in или стандартный ввод Вывод: division.out или стандартный вывод 
Послать решение 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` – длины сторон участков, которые следует выделить младшему, среднему и старшему сыну, соответственно. Если оптимальных решений несколько, разрешается вывести любое.
Пример ввода
6
Пример вывода
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. Гипершашки
Комбинаторика, теория ПойаСканирование, метод двух указателей
Олимпиадные задачи на русском языке
| 01/02/2016 | Региональный этап олимпиады школьников по информатике. II тур. (6) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: game.in или стандартный ввод Вывод: game.out или стандартный вывод
Послать решение 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
Пример вывода
9
Пояснение к примеру
В приведенном примере Андрей сможет показать следующие варианты счета: 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. Интересные числа
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 01/02/2016 | Региональный этап олимпиады школьников по информатике. II тур. (7) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: numbers.in или стандартный ввод Вывод: numbers.out или стандартный вывод
Послать решение 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
Пример вывода
54
Описание подзадач и системы оценивания
Подзадача 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. Гармоничная последовательность
Поиск экстремума функцииОлимпиадные задачи на русском языке
| 01/02/2016 | Региональный этап олимпиады школьников по информатике. II тур. (8) |
| 10/10/2023 | Занятие 222222 (проводит damir) (A) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: sequence.in или стандартный ввод Вывод: sequence.out или стандартный вывод
Послать решение 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
Пример вывода
2
Пояснение к примеру
В приведенном примере оптимальной является, например, гармоничная последовательность [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/ 