Начало
Соревнования
Задачи командных соревнований PRIME TIME 2015
1. Определитель
Индукция и другие математические методыОлимпиадные задачи на русском языке
| 29/03/2015 | Открытые командные соревнования по спортивному программированию ( 1) |
| 31/03/2015 | Занятие 19 (дорешивание соревнований PRIME TIME) ( 1) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Тим разрабатывает модули для QA-системы iNdium-Beta, позволяющей выполнять различные математические расчеты.
Тим хочет проверить работу модуля, вычисляющего с помощью распараллеливания определитель матрицы. Для тестирования
он решил использовать матрицу `A`, элементы которой вычисляются следующим образом.
`A_{i,j}=B_{i+j-1}`
где `B_k` – первое число в `k`-й строке числового треугольника, построенного следующим образом. `k`-я строка
треугольника содержит `k` чисел. Первая строка содержит число 1. Следующая строка треугольника
начинается с последнего числа в предыдущей строке, а следующие числа в строке получаются
как сумма предыдущего числа в строке и числа над ним.
1 1 2 2 3 5 5 7 10 15 15 20 27 37 52 52 67 87 ... ...
Например, матрица `3\ times\ 3` будет выглядеть так:
1 1 2 1 2 5 2 5 15
Чтобы убедиться, что его модуль работает правильно, Тиму нужно знать значение определителя для матрицы `A` заданного
размера.
Формат ввода
Первая строка ввода одно целое число `N` (`1\ ≤\ N\ ≤\ 1000`) – размер матрицы `A`.
Формат вывода
В первой строке вывести одно целое число — определитель матрицы по модулю `10^9+9`.
Пример ввода
3
Пример вывода
2
2. Straggler
Вывод формулыОлимпиадные задачи на английском языке
| 29/03/2015 | Открытые командные соревнования по спортивному программированию ( 2) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Tim develops the news site iMoto about motorsports.
In motorsports it is very common that the leader pilot in a race, at a certain moment, overtakes the last pilot.
The leader, at this moment, is one lap ahead of the last pilot, who then becomes a straggler.
For article about race results, Tim has to calculate in which lap the slowest pilot will become a straggler,
if known the time it takes for the fastest pilot, and for the slowest pilot, to complete one lap.
Shall consider that, at the beginning, they are side by side at the start line of the circuit,
both at the start of lap number 1 (the first lap of the race); and that a new lap always begins right
after the leader crosses the start line.
Input
First line contains two integers `X` and `Y` (`1\ ≤\ X\ <\ Y\ ≤\ 10000`), the times, in seconds, that it
takes for the fastest and the slowest pilot, respectively, to complete one lap.
Output
Program should output line, containing one integer: the lap in which the slowest pilot will become a straggler.
Sample Input #1
1 10
Sample Output #1
2
Sample Input #2
4 8
Sample Output #2
2
Sample Input #3
5 7
Sample Output #3
4
3. Заговор программ
Преобразование или подсчет характеристики (например, сумма) заданной или вычисляемой последовательности
Олимпиадные задачи на русском языке
| 29/03/2015 | Открытые командные соревнования по спортивному программированию ( 3) |
| 31/03/2015 | Занятие 19 (дорешивание соревнований PRIME TIME) ( 3) |
| 28/06/2017 | Лето 2017 (1 курс) - 1 (B) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Тим случайно обнаружил, что некоторые программы, такие как
шахматный гроссмейстер Deep Black, медицинский эксперт Dr. Chaos, военный стратег CloudNet,
проявляют странную активность и посещают некий закрытый чат. Проникнуть в сам чат Тиму не удалось, но
он смог получить логи подключений программ к этому чату за один день. Программы в этом логе
идентифицируются числами от 1 до `10^7`, и возможно одновременное присутствие нескольких программ с одинаковым идентификатором. Тим предположил, что это клоны одной программы.
Напишите программу, которая по логам чата определяет номера программ и количество их клонов, принимающих участие в заговоре.
Формат ввода
Первая строка ввода содержит одно число `N` (`1\ ≤\ N\ ≤\ 10^5`) – количество записей в логе.
Далее следует `N` строк, содержащих номер программы, перед которым стоит символ '+', если программа (клон)
подключилась к чату, или символ '-', если программа (клон) отключилась от чата.
Формат вывода
Вывести в отдельных строках номера программ, участвующих в заговоре, в порядке возрастания. После каждого номера вывести минимально возможное количество клонов этой программы, которое не противоречит логу.
Пример ввода
6 +10 -7 +4 -7 +7 -4
Пример вывода
4 1 7 2 10 1
4. Сайт знакомств
Максимальный поток минимальной стоимостиОлимпиадные задачи на русском языке
| 29/03/2015 | Открытые командные соревнования по спортивному программированию ( 4) |
| 20/07/2020 | Летние сборы - 10 (E) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Тиму необходима программа, которая выбирает пары для проведения
виртуальных свиданий на сайте знакомств iDate. Виртуальное свидание будет наиболее продуктивным,
если пара живет в одном и том же или близких часовых поясах. Программа должна создать
как можно больше пар для свиданий среди `N` мужчин и `M` женщин, зарегистрированных на сайте, при
этом сумма значений выражений `min(|T_i\ –\ T_j|\ mod\ 24,\ 24\ -\ (|T_i\ -\ T_j|\ mod\ 24))` по всем выбранным парам
должна быть как можно меньше. Здесь `T_i` – часовой пояс мужчины, а `T_j` – часовой пояс женщины,
если программа для свидания выбрала пару из `i`-го мужчины и `j`-й женщины. Каждый человек может быть
назначен программой не более чем в одну пару.
Формат ввода
Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 1000`) – количество мужчин и женщин.
Вторая строка содержит часовые пояса `N` мужчин, а третья – часовые пояса `M` женщин.
Часовой пояс задается как разница со всемирным координированным временем (UTC) и может принимать
значение от `-11` до `+14`,
после целого количества часов опционально может быть указано время в минутах 30 или 45.
Формат вывода
Вывести `min(N,M)` строк. В каждой строке вывести номера мужчины и женщины
в выбранной для виртуального свидания паре. Если существует несколько вариантов
с минимальной суммой, то можно вывести любой из них.
Пример ввода
3 4 -7 -11 +5 -9 -8 +5:30 +13
Пример вывода
2 4 1 2 3 3
5. Sexy primes
Простые числа, разложение на множителиОлимпиадные задачи на английском языке
| 29/03/2015 | Открытые командные соревнования по спортивному программированию ( 5) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
As all good math students know, twin primes are pairs of prime numbers that have a
positive difference of 2, whereas cousin primes are pairs of prime numbers that differ by four.
Sexy primes are prime numbers that differ from each other by six.
The term "sexy primes" stems from the Latin word for six: sex.
You should write the program to find a sexy prime for given prime number.
Input
Input contains one prime number `N` (`2\ ≤\ N\ <\ 10^6`).
Output
Print sexy prime for `N`. If several variants exist, print any of them. If no sexy prime exist, print 0 instead.
Sample Input
29
Sample Output
23
6. Вики-разметка
АвтоматыОлимпиадные задачи на русском языке
| 29/03/2015 | Открытые командные соревнования по спортивному программированию ( 6) |
| 31/03/2015 | Занятие 19 (дорешивание соревнований PRIME TIME) ( 6) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Для ввода информации на сайте Тим использует упрощенный вариант вики-разметки, в котором тегами
служат пары символов (см. таблицу). При первом (нечетном) появлении тег означает включение режима,
а при втором (четном) — выключение. В вики-разметке не требуется корректность вложенности тегов и
отсутствует необходимость в каких-либо закрывающих тегах — при переводе в HTML все
незакрытые режимы в конце абзаца текста нужно автоматически закрыть.
В HTML-разметке для включения и выключения режима используются разные теги,
отличающиеся символом /, кроме того должна соблюдаться
вложенность тегов (пары из открывающего и закрывающего тега HTML являются разновидностью скобок).
| Тег вики-разметки | Значение | Теги HTML-разметки |
| ** | Жирный шрифт | <b> </b> |
| // | Курсив | <i> </i> |
| -- | Вычеркнутый | <s> </s> |
| __ | Подчеркнутый | <u> </u> |
Напишите программу, которая для каждого абзаца текста с вики-разметкой формирует строку с HTML-разметкой.
При формировании строки нельзя выводить пару из открывающего и закрывающего HTML-тегов, если
между ними пустая строка (см. пример).
Формат ввода
Ввод содержит не более 10 непустых строк. Каждая строка содержит один абзац текста с вики-разметкой
длиной от 1 до 1000 символов. Строки могут содержать только прописные латинские буквы и
символы '*', '/', '-', '_'. Парные символы интерпретируются
как теги вики-разметки, символы без пары – как обычные символы.
Формат вывода
Для каждой строки из входного файла вывести строку с соответствующей HTML-разметкой.
Строка должна быть заключена в теги <p></p>, даже если она пустая. Можно вывести любой
вариант строки, строка может не иметь минимальную длину, но она должна быть корректной
с точки зрения вложенности тегов, в ней не должно быть избыточных пар тегов вида <x></x> или </x><x> и
она должна соответствовать входной строке.
Пример ввода
AA**BB//CC**DD ----__***__A__B
Пример вывода
<p>AA<b>BB<i>CC</i></b><i>DD</i></p> <p><b><u>*</u>A<u>B</u></b></p>
7. Ввод текста
МоделированиеОлимпиадные задачи на русском языке
| 29/03/2015 | Открытые командные соревнования по спортивному программированию ( 7) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Тиму приходится вводить много информации с клавиатуры, но он до сих пор печатает текст двумя
указательными пальцами. Тиму захотелось узнать, какая часть работы по вводу текста проделана каждым пальцем.
Для ввода Тим использует компактную клавиатуру с тремя рядами клавиш, в каждом ряде 10 квадратных клавиш (см. рис).
Перед вводом левый палец Тима находится над центром клавиши с буквой F, а правый – над клавишей с буквой J.
Для ввода очередного символа текста Тим использует палец, который расположен ближе к этой клавише.
Расстояние вычисляется как Евклидова дистанция между центрами двух клавиш: клавишей, над которой расположен
в данный момент палец, и клавишей с очередным символом текста. Если оба пальца
находятся на одинаковом расстоянии от клавиши с очередным символом, Тим использует палец левой руки.
После ввода символа палец остается над клавишей с введенным символом.
Формат ввода
Ввод содержит непустую строку длиной до 1000 символов, состоящую только из прописных латинских букв и
символов '*', '/', '-', '_'.
Формат вывода
Вывести два целых числа – сколько символов текста Тим наберёт левым и правым пальцем.
Пример ввода 1
PRIME_TIME
Пример вывода 1
4 6
Пример ввода 2
PROGRAMMING_CONTEST
Пример вывода 2
10 9
8. Космические кораллы
Быстрая сортировкаДеревья (map, set), хэш-таблицы
Олимпиадные задачи на русском языке
| 29/03/2015 | Открытые командные соревнования по спортивному программированию ( 8) |
| 31/03/2015 | Занятие 19 (дорешивание соревнований PRIME TIME) ( 8) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В далеком космосе были обнаружены месторождения минералов, которые получили
название "космический коралл". Ценными для производства украшений считаются только 3 или более отростка
минерала, которые срослись одной общей вершиной, а другие вершины отростков свободны. При
этом не должно быть отростков одинаковой длины.
Каждая доставленная партия минерала для выявления ценных кораллов проверяется на специальном сканере – сегментографе,
результатом работы которого является сегментограмма – набор отрезков, каждый отрезок соответствует
отростку коралла. Конструкция сегментографа гарантирует, что отрезки имеют общую вершину, только
если отростки срослись в ней. Если пересечение отрезков на сегментограмме происходит
не в общей вершине, то физически соответствующие отростки никак не соединяются, так как
сегментограмма является двумерной проекцией трехмерной структуры коралла. Аналогично для наложения отрезков.
Необходимо разработать программное обеспечение для сегментографа, позволяющее для каждой партии
определять количество ценных кораллов в ней.
Формат ввода
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 300\ 000`) – количество отрезков.
Далее следует `N` строк, каждая строка содержит четыре целых числа `x_1,\ y_1,\ x_2,\ y_2`
(`-10^8\ ≤\ x_1,\ y_1,\ x_2,\ y_2\ ≤\ 10^8`) – координаты концов отрезков. Все отрезки ненулевой длины.
Формат вывода
Вывести одно целое число – количество ценных космических кораллов.
Пример ввода
10 3 3 2 2 3 3 1 5 4 5 3 3 5 1 4 2 5 1 6 2 5 1 5 2 5 5 4 6 5 5 5 4 5 4 4 3 5 4 3 5
Пример вывода
1
9. Разбиение на квадраты
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 29/03/2015 | Открытые командные соревнования по спортивному программированию ( 9) |
| 31/03/2015 | Занятие 19 (дорешивание соревнований PRIME TIME) ( 9) |
| 10/07/2019 | Лето 2019 - 5 (E) |
| 12/11/2021 | Контест №4* Базовая подготовка (проводит BOGAT) (D) |
| 07/02/2022 | Тренировка (динамическое программирование) (проводит BOGAT) (D) |
| 02/03/2023 | Базовый уровень: динамическое программирование 2 (проводит BOGAT) (E) |
| 05/03/2024 | Динамическое программирование 2 (проводит BOGAT) (E) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
При создании макета сайта Тим предпочитает разбивать страницу на квадратные области.
Определите, на какое наименьшее количество квадратных областей с целыми размерами можно разбить страницу
заданного размера, если необходимо, чтобы для найденного разбиения выполнялось свойство разделяемости.
Разбиение части или всей страница обладает свойством разделяемости, если выполняется одно из двух условий:
- часть (или вся) страница имеет форму квадрата и соответствует одной квадратной области;
- существует горизонтальная или вертикальная линия, проходящая полностью по границам областей, расположенных в этой части (или всей) страницы, которая делит её на две части, разбиение которых также обладает свойством разделяемости.
Макет сайта, обладающего свойство разделяемости, можно определить, задавая только размеры, выравнивание и вложенность частей страницы, т. е. более простым образом, чем макет сайта, не обладающего таким свойством.
Формат ввода
Ввод содержит два целых числа `W` и `H` (`1\ ≤\ W,\ H\ ≤\ 400`) – размеры страницы.
Формат вывода
Вывести одно целое число – наименьшее количество квадратных областей.
Пример ввода
12 10
Пример вывода
5
10. Робин Гуд
Бинарный поискБыстрая сортировка
Олимпиадные задачи на русском языке
| 29/03/2015 | Открытые командные соревнования по спортивному программированию (10) |
| 31/03/2015 | Занятие 19 (дорешивание соревнований PRIME TIME) (10) |
| 30/06/2023 | Лето 2023-3 сложные (командное) (E) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Тим взломал сервер социальной сети iLike и теперь хочет компенсировать этот дурной поступок
хорошим — отнять часть лайков у популярных пользователей этой сети и отдать их бедным таким образом,
чтобы максимальная разница в количестве лайков у пользователей этой сети не превышала некоторого `K`.
Напишите программу, определяющую, какое наименьшее количество лайков должен перераспределить Тим,
чтобы добиться желаемого.
Формат ввода
Первая строка ввода содержит два целых число `N` и `K` (`1\ ≤\ N\ ≤100 000`, `1\ ≤\ K\ ≤\ 10^6`) – количество
пользователей и ограничение на минимальную разницу. Во второй строке `N` целых чисел от 0 до `10^{12}` – распределение
лайков по пользователям сети.
Формат вывода
Вывести одно целое число – минимальное количество лайков, которое нужно перераспределить.
Пример ввода
4 2 5 6 2 0
Пример вывода
3
11. Последний штурм
Полный переборОлимпиадные задачи на русском языке
| 29/03/2015 | Открытые командные соревнования по спортивному программированию (11) |
| 31/03/2015 | Занятие 19 (дорешивание соревнований PRIME TIME) (11) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Тим разрабатывает казуальную RPG для магазина веб-игр iPlay. Чтобы игра не была слишком простой,
Тиму нужно определить, насколько сильную армию может собрать игрок для штурма замка главного злодея.
Игрок может набрать несколько отрядов, при этом в каждом отряде должны быть войска одного вида, и не может быть
более одного отряда с этим видом войск. Максимальное количество отрядов в армии зависит от выбранного
в начале игры класса героя (бард, волшебник, паладин и т. д.), а величина отряда – от харизмы героя, максимальная
величина которой зависит от действий игрока в процессе игры и класса героя. Виды войск кроме того разделены
на 3 типа: регулярные войска (ополченцы, лучники, конница и т. д., которых можно найти в замках),
наемники (разбойники, эльфы, кентавры и т. д., которых можно нанять в тавернах) и
нежить (привидения, упыри, вампиры и т. д., которых можно найти на кладбищах). Если в
армии героя несколько отрядов регулярных войск, то их боевой дух и сила атаки возрастает, но если в
армии присутствуют отряды нежити, то сила атаки регулярных войск падает.
Количество отрядов наемников не влияет на силу атаки регулярных войск. Для вычисления силы атаки
отряда регулярных войск используется формула:
`max(1,\ p*(a+d*(L-N-1)))`,
где `p` – количество юнитов в отряде, `a` – сила атаки одного юнита, `d` – коэффициент влияния боевого духа
на атаку, `L` – количество отрядов регулярных войск в армии героя, `N` – количество отрядов нежити в армии героя.
Сила атаки наемников и нежити не зависит от состава других отрядов и вычисляется по формуле: `p*a`.
Максимальное количество юнитов в отряде вычисляется как `|__\ H/u\ __|`, где `H` – харизма героя, а `u` – коэффициент,
зависящий от вида войск.
Напишите программу, которая определит максимальную суммарную силу атаки армии.
Формат ввода
Первая строка ввода содержит три целых числа: максимальное
количество отрядов `K` (`3\ ≤\ K\ ≤\ 10`), харизма героя `H` (`100\ ≤\ H\ ≤\ 10^4`) и количество видов
войск `W` (`K\ ≤\ W\ ≤\ 100`). Далее следует `W` строк, каждая строка содержит три целых числа `u_i`, `a_i`
и `d_i` – параметры `i`-го вида войск (`1\ ≤\ u_i\ ≤\ 100`, `1\ ≤\ a_i\ ≤\ 1000`, `-1\ ≤\ d_i\ ≤\ a_i`, для
регулярных войск `d_i\ >\ 0`, для наемников `d_i\ =\ 0`, для нежити `d_i\ =\ -1`).
Формат вывода
В первой строке вывести одно целое число – максимальную суммарную силу атаки армии.
Пример ввода
3 100 5 10 10 1 12 20 0 20 20 -1 4 1 1 5 2 -1
Пример вывода
350
`|__100/10__|*(10+1*(1-1-1))+|__100/12__|*20+|__100/20__|*20=350`.
