Начало
Соревнования
Задачи личных соревнований по спортивному программированию 2015
A. Матрица в многомерном пространстве
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 17/10/2015 | Личные соревнования по спортивному программированию (A) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В некотором многомерном подпространстве путешествует невырожденная матрица размера 3x3,
двигаясь только вертикально или горизонтально. Она должна найти путь к выходу из подпространства,
который всегда существует. В случае, если матрица встречает препятствие, которое не может обойти в
полном виде, то она может сжаться до одного единственного собственного значения и продолжить весь оставшийся путь
в таком виде. Матрица сжимается относительно центральной клетки, после сжатия размер матрицы становится 1x1.
В сжатом виде шаги матрицы становятся медленнее в 9 раз. Сжатие матрицы происходит мгновенно, то есть без
затрат времени. Необходимо определить наименьшее время, необходимое для выхода из подпространства.
В первой строке ввода содержится 6 целочисленных значений, разделенных пробелами:
координаты `X`, `Y` начального положения центральной ячейки матрицы, координаты `X`, `Y` выхода из подпространства
(все координаты вычисляют с 0, начало координат находится в левом верхнем углу),
ширина `W` и высота `H` подпространства (`3\ ≤\ H,\ W\ ≤\ 200`).
В следующих `H` строчках описывается карта подпространства: символу '.' соответствует свободная
клетка подпространства, символу '#' соответствует преграда.
В начальной положении препятствий в соседних с центром матрицы клетках нет.
Вывести одно целое число – минимальное время для выхода матрицы из подпространства.
Для выхода из подпространства центр матрицы должен оказаться в клетке, соответствующей выходу.
Один шаг матрицы в несжатом виде занимает 1 единицу времени, один шаг в сжатом виде – 9 единиц времени.
Пример ввода
1 5 10 5 11 11 ###........ ##....#.... #.......... ......##... .....##.... ....##..... .....##.... ......##... #......##.. ##......##. ###......##
Пример вывода
87
На рисунке символами 'X' отмечен путь перемещения центра матрицы в несжатом виде, а символами '*' – путь перемещения матрицы в сжатом виде.
B. Координаты пингвинов
Модулярная арифметикаБыстрая сортировка
Олимпиадные задачи на русском языке
| 17/10/2015 | Личные соревнования по спортивному программированию (B) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Зоолог Том наблюдает для передвижениями пингвинов на плоской площадке с помощью прибора, определяющего
координаты всех пингвинов. Ось `Y` координатной сетки прибора направлена на север, центр координат
соответствует текущему местоположению прибора. Том хочет перейти вместе с прибором в какую-то другую точку площадки,
чтобы как можно больше пингвинов имело целочисленные координаты (по `x` и `y` одновременно). Том хочет минимизировать
расстояние, которое потребуется пройти при этом, так как прибор достаточно тяжелый.
Пингвинов и Тома будем считать точками на плоскости, координаты некоторых пигвинов или координаты
некоторого пингвина и Тома (до либо после перемещения) могут совпадать.
В первой строке содержится целое число `n` (`0\ ≤\ n\ ≤\ 100000`) – количество пингвинов. Каждая из следующих `n` строк
содержит пару вещественных чисел `x_i,\ y_i` (`-100\ ≤\ x_i,\ y_i≤\ 100`) с не более чем пятью знаками
после десятичной точки, разделенных пробелом – координаты пингвинов.
Единственная строка вывода содержит два числа, разделенных пробелом: максимальное количество пингвинов, которые
могут одновременно иметь целые координаты по `x` и `y` и минимальное расстояние, на которое для этого
потребуется передвинуть прибор с точностью `10^{-8}`.
Пример ввода 1
3 0.5 0.2 0.500 0.50000 -0.50000 0.200
Пример вывода 1
2 0.53851648
Пример ввода 2
2 0.0 0.00000 1.00000 1.0
Пример вывода 2
2 0.00000000
C. Иерархия пингвинов
Задачи на построениеОлимпиадные задачи на русском языке
| 17/10/2015 | Личные соревнования по спортивному программированию (C) |
| 26/06/2023 | Лето 2023-1 сложные (D) |
| 24/06/2024 | Лето 2024-1 сложные (D) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Зоолог Том заметил, что в стае пингвинов всегда существует строгая иерархия.
Если в стае `n` пингвинов, то каждому пингвину можно присвоить уникальный ранг от 1 до `n`.
Когда стая отправляется на рыбалку, они инстинктивно выстраиваются цепочкой,
в которой ранг каждого пингвина является делителем суммы рангов пингвинов, идущих впереди него.
Ввод содержит одно целое число `n` (`1\ ≤\ n\ ≤\ 100`).
Вывести перестановку из чисел от 1 до `n` – любой из возможных вариантов походного порядка пингвинов.
Пример ввода
5
Пример вывода
4 1 5 2 3
3 1 4 2 5
4 2 3 1 5
5 1 2 4 3
D. Цепочка пингвинов
Преобразование или подсчет характеристики (например, сумма) заданной или вычисляемой последовательности
Олимпиадные задачи на русском языке
| 17/10/2015 | Личные соревнования по спортивному программированию (D) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Зоолог Том заметил, что в стае пингвинов всегда существует строгая иерархия.
Если в стае `n` пингвинов, то каждому пингвину можно присвоить уникальный ранг от 1 до `n`.
Когда стая отправляется на рыбалку, они инстиктивно выстраиваются цепочкой,
в которой ранг каждого пингвина является делителем суммы рангов пингвинов, идущих впереди него.
Первая строка ввода содержит одно целое число `n` (`1\ ≤\ n\ ≤\ 100`). Вторая строка ввода
содержит перестановку из чисел от 1 до `n` – порядок пингвинов в цепочке.
Вывести сообщение Yes, если пингвины в цепочке перечислены в походном порядке, или
или сообщение No, если походный порядок нарушен.
Пример ввода 1
5 4 1 5 2 3
Пример вывода 1
Yes
Пример ввода 2
5 1 5 2 3 4
Пример вывода 2
No
E. Чехарда пингвинов
Индукция и другие математические методыОлимпиадные задачи на русском языке
| 17/10/2015 | Личные соревнования по спортивному программированию (E) |
| 25/06/2018 | Лето 2018 - 1 (E) |
| 29/06/2020 | Лето 2020 - 1 (E) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Ущелье прорезает полосу торосов между морем и площадкой, на которой живут пингвины.
Ущелье настолько узкое, что пингвинам приходится перепрыгивать друг через друга, чтобы разминуться.
Однажды стая из `n` пингвинов, возвращаясь с рыбалки, встретила в ущелье стаю из `m` пингвинов, которая только
собиралась поужинать. Между стаями оказалось небольшое пространство, на котором мог поместиться только один
пингвин. Между пингвинами в стаях свободного пространства нет.
За одно действие пингвин может либо перейти на свободное пространство перед собой, либо перепрыгнуть
через пингвина впереди себя, если за ним есть свободное пространство.
Пятиться и прыгать назад пингвины не умеют.
Напишите программу, вычисляющую минимальное количество действий, за которое две стаи пингвинов могут
разминуться в ущелье. После выполнения действий между стаями должно быть пустое пространство. Также пингвины не должны выходить за пределы участка ущелья, на котором две стаи встретились, так как там могут находиться другие стаи пингвинов.
Ввод содержит два целых числа `n` и `m` (`1\ ≤\ n,\ m\ ≤\ 100000`) – количество пингвинов в стаях.
Вывести одно целое число – минимальное количество действий.
Пример ввода
2 3
Пример вывода
11
AA.BBB A.ABBB ABA.BB ABAB.B AB.BAB .BABAB B.ABAB BBA.AB BBABA. BBAB.A BB.BAA BBB.AA
F. Подсчет пингвинов
Дерево отрезков, декартово дерево, √-декомпозицияОлимпиадные задачи на русском языке
| 17/10/2015 | Личные соревнования по спортивному программированию (F) |
| 14/07/2016 | Лето 2016 - 9 (C) |
Ограничения: время – 2000ms/4000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Для наблюдения за пингвинами Том установил в ущелье камеры.
Время от времени с камер поступает информация о передвижениях пингвинов,
и иногда Том делает запросы о количестве стай пингвинов на некотором участке ущелья.
Стаей считается последовательность пингвинов без промежутков, отделенная пустым пространством от других стай.
Первая строка ввода содержит два целых числа `n` (длина ущелья) и `m` (`1\ ≤\ n\ ≤\ 100000`,`1\ ≤\ m\ ≤\ 100000`).
Далее следует `m` строк, содержащих хронологически упорядоченную последовательность запросов Тома
и поступлений информации с камер.
Первым символом в строке указывается символ '?', '*' или '.', за
которым через пробел следуют два числа `p_1` и `p_2` (`1\ ≤\ p_1\ ≤\ p_2\ ≤\ n`), задающих участок ущелья.
Cимвол '?' означает запрос Тома о количестве стай пингвинов на участке.
Cимвол '*' означает, что все позиции на заданном участке заполнились пингвинами,
символ '.' означает, что все позиции на заданном участке стали свободными.
Первоначально все позиции в ущелье свободны.
Для каждого запроса Тома вывести на отдельной строке количество стай пингвинов, которые видны полностью
или частично на заданном участке ущелья.
Пример ввода
10 5 * 1 7 . 3 5 ? 2 7 * 4 4 ? 1 10
Пример вывода
2 3
G. Язык пингвинов
Техника программирования, моделированиеОлимпиадные задачи на русском языке
| 17/10/2015 | Личные соревнования по спортивному программированию (G) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Зоолог Том сумел расшифровать язык пингвинов и составил пингвино-английский словарь.
Напишите программу для перевода с языка пингвинов на английский и обратно.
Первая строка ввода содержит два целых числа `n` и `f` (`1\ ≤\ n\ ≤\ 100`, `0\ ≤\ f\ ≤\ 1`) – количество слов и направление перевода.
`f=0` означает перевод с языка пингвинов на английский, а `f=1` – перевод с английского на пингвиний.
Следующие `n` строк содержат по два слова – слово из языка пингвинов и его перевод на английский.
Все слова в словаре уникальны. Длина слов не превышает 20 символов.
Слово на английском языке содержит только строчные латинские буквы,
а слово на пингвиньем языке – любые печатные символы с ASCII кодами в диапазоне от 33 до 126, кроме
строчных латинских букв.
Следующая (последняя) строка ввода содержит последовательность слов на пингвиньем (`f=0`) или на английском (`f=1`) языке.
Последовательность содержит от 1 до 100 слов. Слова разделены одним пробелом.
Вывести перевод последовательности слов на английский (`f=0`) или на пингвиний (`f=1`) язык.
Если какое-то слово отсутствует в словаре, то вывести вместо перевода символ ? (см. примеры вывода).
Пример ввода 1
5 0 ><(> fish ~~~ sea >=[] shark ()@ catch !>> go !>> ~~~ ()@ ><(> ;)
Пример вывода 1
go sea catch fish ?
Пример ввода 2
5 1 ><(> fish ~~~ sea >=[] shark ()@ catch !>> go shark swims in sea
Пример вывода 2
>=[] ? ? ~~~
H. Ограда от пингвинов
Вычислительная геометрияКратчайшие пути между всеми парами вершин
Олимпиадные задачи на русском языке
| 17/10/2015 | Личные соревнования по спортивному программированию (H) |
Ограничения: время – 2000ms/4000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0) 
Селекционер Сэм пытается вырастить новые морозоустойчивые виды яблонь для будущих марсианских поселений.
Для защиты от пингвинов сад окружен оградой в форме выпуклого многоугольника.
Столбы этой ограды расположены в вершинах многоугольника и на его сторонах.
Пингвины научились перепрыгивать через невысокую ограду и разводить костры для обогрева из сломанных веток, поэтому Сэм хочет заменить
эту ограду на более высокую, используя существующие столбы.
При этом все деревья должны оказаться строго внутри новой ограды,
а новая ограда должна представлять собой выпуклый многоугольник с минимальным периметром, вершины которого находятся
на столбах старой ограды.
Первая строка ввода содержит одно целое число `N` (`3\ ≤\ N\ ≤\ 250`) – количество столбов в старой ограде.
Каждая из следующих `N` строк содержит два целых числа – координаты столбов в порядке обхода ограды по часовой стрелке.
Следующая строка содержит одно целое число `K` (`1\ ≤\ K\ ≤\ 10000`) – количество деревьев в саду.
Каждая из следующих `K` строк содержит два целых числа – координаты деревьев.
Гарантируется, что все деревья находятся строго внутри старой ограды.
Все координаты точек различны и не превосходят по абсолютному значению `10^6`.
Вывести одно число – минимальную длину новой ограды с точностью `10^{-4}`.
Пример ввода 1
6 -20 -10 -10 20 10 20 20 10 10 -20 -10 -20 2 0 10 0 -10
Пример вывода 1
120.0000
Пример ввода 2
4 0 4 4 4 4 0 0 0 3 1 3 2 3 1 2
Пример вывода 2
13.6569
I. Генерация пингвинов
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 17/10/2015 | Личные соревнования по спортивному программированию (I) |
| 02/03/2023 | Базовый уровень: динамическое программирование 2 (проводит BOGAT) (B) |
| 12/07/2023 | Лето 2023-8 простые (F) |
| 05/03/2024 | Динамическое программирование 2 (проводит BOGAT) (B) |
| 10/07/2024 | Лето 2024-8 простые (F) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Зоолог Том подсчитал количество пингвинов в очередной стае и в ожидании новой стаи стал
складывать соседние цифры в получившемся числе и записывать их сумму между этими цифрами.
С новым числом он проделал ту же операцию, и так он сделал `n` раз. Например, из числа 47
после первого применения описанной операции генерации получится число 4117, после второго – число 4512187,
после третьего – число 49561323198157.
Напишите программу, которая вычисляет, сколько раз написал Том каждую из цифр от 0 до 9 при
записи числа `A_n`, получившегося в результате применения операции генерации `n` раз к исходному числу `A_0`.
Первая строка ввода содержит два целых числа – исходное число `A_0` (`10\ ≤\ A_0\ <\ 10^6`)
и количество применений операции генерации `n` (`1\ ≤\ n\ ≤\ 50`).
Гарантируется, что количество цифр в числе `A_n` не превышает `2^{63}-1`.
В первой строке вывести 10 целых чисел через пробел – количество цифр 0, 1, …, 9 в числе `A_n`.
Пример ввода
47 3
Пример вывода
0 3 1 2 1 2 1 1 1 2
