Начало
Соревнования
Задачи отборочных командных соревнований школьников 2015
A. Сломанная клавиатура
Техника программирования, моделированиеОлимпиадные задачи на русском языке
| 25/10/2015 | Региональные отборочные командные соревнования для школьников (A) |
Ограничения: время – 1s/1s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Сэм пытается ввести свое имя на старом ноутбуке, но клавиши залипают, и при нажатии на клавишу буква
может напечататься от 1 до 100 раз.
Сэм хочет выбрать из введенного текста подстроку наименьшей длины, содержащей его имя "SAM".
При этом некоторые буквы могут присутвовать в подстроке несколько раз, но каждая буква имени
должна быть в выбранной подстроке как минимум один раз.
Ввод содержит строку длиной от 3 до 300 символов – результат попытки Сэма ввестти свое имя.
В начале строки идет последовательность из букв S, затем последовательность из букв A, а завершает строку
последовательность из букв M. Каждая буква повторяется от 1 до 100 раз.
Выведите два целых числа через пробел – номер начального и конечного символа подстроки
минимальной длины, содержащей имя "SAM".
Пример ввода
SSSSSAAAMMMMMMM
Пример вывода
5 9
B. Атомы
Дерево отрезков, декартово дерево, √-декомпозицияОлимпиадные задачи на русском языке
| 25/10/2015 | Региональные отборочные командные соревнования для школьников (B) |
Ограничения: время – 3s/3s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В лаборатории аномальных материалов антинаучно-исследовательского
комплекса "Black Mesa" проводят эксперименты с недавно разработанным
графитовым наностержнем.
Графитовый наностержень представляет собой `n` последовательно
соединенных атомов углерода, находящихся на одной прямой.
Каждый атом имеет определенный заряд.
Для проведения эксперимента, стержень располагают вертикально.
Пронумеруем атомы от 1 до `n` снизу вверх.
Между двумя атомами образуется сильная связь, если это соседние атомы
и верхний из них имеет заряд ровно на один больше, чем нижний.
Иными словами, атомы `a` и `b` соединены сильной связью, если `a\ =\ b\ +\ 1` и `q_a\ =\ q_b\ +\ 1`,
где `q_i` – заряд `i`-го атома.
Цепочкой атомов назовем несколько последовательных атомов, соединенных сильными связями.
Вчера был проведен очередной эксперимент.
Перед началом эксперимента каждому атому установили определенный заряд:
`i`-му атому установили заряд `q_i`.
Во время эксперимента ученые проводили действия двух типов:
1) у всех атомов с номерами от `l_i` до `r_i`, включительно, заряд изменяли на величину `d_i`;
2) временно разрушали все сильные связи атомов, кроме тех, которые соединяют атомы с номерами от `l_i` до `r_i`, включительно,
и измеряли длину самой длинной цепочки атомов среди оставшихся сильных связей.
Затем восстанавливали все временно разрушенные связи.
Было произведено `m` действий, однако выяснилось, что в результате
побочного эффекта эксперимента запись результатов измерений оказалась утеряна.
Для продолжения работы с графитовым наностержнем необходимо восстановить результаты вчерашних измерений.
К счастью, сохранился план действий, произведенных во время эксперимента.
Помогите ученым продолжить исследования, восстановите результаты измерений.
В первой строке находится одно целое число `n` (`1\ ≤\ n\ ≤\ 100\ 000`) – количество атомов в наностержне.
Во второй строке находятся `n` чисел `q_i` (`|q_i|\ ≤\ 10^9`) – начальный заряд `i`-го атома.
В третьей строке находится одно целое число `m` (`0\ ≤\ m\ ≤\ 100\ 000`) – количество действий в эксперименте.
В следующих `m` строках содержится описание эксперимента.
Если строка начинается с символа +, очередное действие – изменение заряда атомов.
В таком случае, далее в этой строке находятся три целых числа: `l_i`, `r_i` и `d_i` (`1\ ≤\ l_i\ ≤\ r_i\ ≤\ n`, `|d_i|\ ≤\ 10^9`), которые характеризуют это действие.
Если строка начинается с символа ?, очередное действие – второго типа.
В таком случае, далее в этой строке находятся два целых числа: `l_i` и `r_i` (`1\ ≤\ l_i\ ≤\ r_i\ ≤\ n`), которые характеризуют это действие.
Для каждого действия второго типа выведите в новой строке одно число – длину наибольшей цепочки.
Пример ввода
6 2 3 4 3 4 4 5 ? 1 6 + 6 6 1 ? 2 6 + 4 6 2 ? 1 5
Пример вывода
3 3 5
Пунктиром выделены сильные связи, которые разрушаются на время действия второго типа.
Для каждого действия второго типа выделены отрезок запроса и самая длинная цепочка.
Источник: XXIII Командный чемпионат школьников Санкт-Петербурга по программированию, 2015
C. День рождения
Индукция и другие математические методыОлимпиадные задачи на русском языке
| 25/10/2015 | Региональные отборочные командные соревнования для школьников (C) |
Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Ваня сомневается, хочет ли он праздновать свой день рождения.
Он решил сообщить друзьям частичную информацию о дате своего рождения,
и если они вычислят точную дату, то так тому и быть – праздник состоится.
Подруге Ане он личным сообщением в социальной сети сообщил число внутри
месяца, а другу Боре – месяц своего рождения.
Затем он опубликовал на своей странице список дней года, один из которых –
день его рождения, а также фразу о том, что Аня знает число, но не знает месяц,
а Боря – знает месяц, но не число.
Затем в комментариях состоялся следующий диалог:
Аня: Я не знаю точную дату рождения Вани, но я уверена, что и Боря её тоже не знает.
Боря: Я сначала не знал дату Ваниного рождения, но теперь, после твоего комментария, знаю точно!
Аня: Ого! Теперь и я тоже знаю точную дату!
Боря: Я сначала не знал дату Ваниного рождения, но теперь, после твоего комментария, знаю точно!
Аня: Ого! Теперь и я тоже знаю точную дату!
Когда же у Вани день рождения?
В первой строке содержится целое число `n` (`1\ ≤\ n\ ≤\ 366`) – количество возможных дат,
опубликованных Ваней на своей странице.
В каждой из следующих `n` строк содержится описание одной даты: число и номер месяца.
Месяцы пронумерованы от 1 до 12.
Даты приведены в хронологическом порядке внутри года.
Гарантируется, что ситуация корректна, и существует единственная возможная дата рождения Вани,
которая приводит к описанному диалогу.
Выведите дату рождения Вани в таком же формате: сначала число, а затем месяц.
Пример ввода
11 29 2 5 5 16 5 31 5 17 6 18 6 14 7 16 7 5 12 14 12 17 12
Пример вывода
17 6
| Номер месяца | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| Число дней | 31 | 29 | 31 | 30 | 31 | 30 | 31 | 31 | 30 | 31 | 30 | 31 |
D. Шушпанчики и кинотеатр
Быстрая сортировкаСканирование, метод двух указателей
Олимпиадные задачи на русском языке
| 25/10/2015 | Региональные отборочные командные соревнования для школьников (D) |
Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В кинотеатре "Дружба" через неделю пройдет премьера мирового хита
"Осторожный Макс", и шушпанчики обязательно хотят попасть на первый сеанс.
Зал в кинотеатре состоит из `n` рядов по `n` мест в каждом. Ряды пронумерованы
от 1 до `n`, места в каждом ряду также пронумерованы от 1 до `n`. Обозначим
место с номером `c` в ряду `r` как `(r,\ c)`.
Шушпанчики точно знают, что лучшее место в зале – место `(r_b,\ c_b)`. Для любого
места `(r,\ c)` можно посчитать неудачность этого места как `|r-r_b|+|c-c_b|`,
и чем неудачность меньше, тем лучше.
Шушпанчики пойдут на сеанс группой из `k` шушпанчиков. Они хотят сидеть рядом друг с другом, поэтому договорились купить
`k` мест подряд в одном ряду. Таким образом, шушпанчики купят билеты на места
`(r_a,\ c_a),\ (r_a,\ c_a+1),\ …,\ (r_a,\ c_a+k-1)` для некоторых `r_a` и `c_a`.
К сожалению, некоторые места уже забронированы, и их выкупить не получится. Помогите шушпанчикам
выбрать `k` соседних мест на одном ряду так, чтобы суммарная неудачность выбранных ими мест была минимальна.
В первой строке заданы три числа `n`, `m` и `k`
(`1\ ≤\ n\ ≤\ 10^9`, `0\ ≤\ m\ ≤\ min(n^2,\ 10^5)`, `1\ ≤\ k\ ≤\ n`) – размер зала, число проданных мест и число шушпанчиков.
В следующих `m` строках описаны занятые места. Каждое место
описывается двумя числами: `r_i,\ c_i` (`1\ ≤\ r_i,\ c_i\ ≤\ n`, все описанные места различны).
В следующей строке даны два числа `r_b,\ c_b` (`1\ ≤\ r_b,\ c_b\ ≤\ n`) – оптимальное место, как можно ближе к которому хотят
оказаться шушпанчики.
Если все шушпанчики не смогут купить билеты на `k` мест подряд в одном ряду, выведите `-1`.
Иначе, выведите минимальную суммарную неудачность, которую можно получить.
Пример ввода 1
3 1 2 1 2 1 1
Пример вывода 1
3
Пример ввода 2
3 3 2 1 2 2 2 3 2 2 2
Пример вывода 2
-1
E. Доставка футболок
МоделированиеОлимпиадные задачи на русском языке
| 25/10/2015 | Региональные отборочные командные соревнования для школьников (E) |
Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Завершилась Командная Интернет-олимпиада Новой Зеландии по Алгоритмам
(КИНЗА). После олимпиады оргкомитет принял решение отправить
футболки всем призерам олимпиады. Доставка футболок была поручена
компании, в которой работает курьер Билл.
Биллу требуется доставить `n` футболок. Он должен доставлять
посылки в том порядке, в котором они значатся в его обходном листе. При этом,
если посылку доставить не удалось, то в обходном листе ставится отказ, и Билл
едет по следующему адресу.
Билл начинает свой рабочий день в офисе компании в момент 0.
Приезжая к адресату посылки, он ждет не более `k` минут,
и если за это время адресат открывает дверь, то Билл отдает ему посылку,
процесс передачи посылки без учета времени ожидания занимает `t` минут.
Если же в течение `k` минут дверь не открывается и получатель не появляется,
то Билл едет дальше. При этом, если
получатель появился ровно ровно через `k` минут после приезда Билла,
то Билл успевает это заметить,
и посылка оказывается доставлена. Рабочий день Билла заканчивается,
когда он заканчивает передавать последнюю посылку, либо отмечает в обходном
листе отказ от ее получения.
Начальник Билла Джон хочет проверить, насколько добросовестно тот работает.
Джону известно, сколько времени ему потребуется на то, чтобы доехать
от офиса до первого адресата, а также время на переезд от очередного адресата
до следующего. Кроме того, он провел телефонный опрос и знает время, начиная с которого
каждый из получателей футболок будет дома. Теперь Джон хочет узнать, в какой момент
Билл закончит свой рабочий день.
В первой строке входного файла находятся три целых числа `n`, `k`, `t` (`1\ ≤\ n\ ≤\ 50\ 000`, `1\ ≤\ k,\ t\ ≤\ 10^4`).
Во второй строке находятся `n` натуральных чисел `z_0,\ z_1,\ …,\ z_{n-1}`, где `z_0` – это время, которое
требуется Биллу, чтобы доехать от офиса до первого адресата, а `z_i` – это время,
которое требуется Биллу для преодоления пути от `i`-го до `i+1`-го адресата. Все `z_i` не превосходят `10^4`.
В третьей строке находятся `n` неотрицательных целых чисел `s_1,\ s_2,\ …,\ s_n` (`0\ ≤\ s_i\ ≤\ 10^{9}`),
где `s_i` – это момент,
начиная с которого `i`-й адресат готов принять посылку. Билл начинает свой путь в момент времени 0.
Выведите одно число – минимальное время, за которое Билл сможет выполнить свое задание.
Пример ввода
3 3 1 1 5 4 1 11 7
Пример вывода
15
В примере Билл приезжает к первому адресату в момент времени 1 и сразу же передает ему посылку.
В момент времени 2 он выезжает от первого адресата и в момент времени 7 приезжает ко второму.
Он ждет его 3 минуты, до момента времени 10, но тот не появляется, поэтому Билл отправляется
к третьему адресату и приезжает к нему в момент 14. Тот дома и принимает посылку.
Таким образом, Билл освобождается в момент времени 15.
Источник: XXIII Командный чемпионат школьников Санкт-Петербурга по программированию, 2015F. Деление
Разделение на 2 (или более) подзадачиОлимпиадные задачи на русском языке
| 25/10/2015 | Региональные отборочные командные соревнования для школьников (F) |
Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0) 
Сегодня Леша проходил в школе деление столбиком.
На дом ему задали вычислить частное двух больших чисел: `n` и `m`.
Леша уже попробовал решить пример, но, неожиданно для себя, понял, что `n` на `m` не делится.
Он уверен, что учитель задавал пример, в котором результат не имеет остатка, поэтому он предположил,
что допустил ошибку при переписывании примера с доски.
Теперь он хочет исправить несколько цифр в числе `n`, чтобы оно стало делиться на `m`.
При этом, Леша хочет, чтобы новое число отличалось от записанного у
него в минимальном количестве позиций.
Числа, записанные Лешей, не имеют ведущих нулей,
он уверен, что числа, записанные на доске, также не имели ведущих нулей,
поэтому и в новом числе их не должно быть. Само число
0 при этом является допустимым.
Помогите Леше.
В единственной строке входного файла находятся два целых числа
`n`, `m` (`0\ ≤\ n\ ≤\ 10^{11}`, `1\ ≤\ m\ ≤\ 10^{11}`).
В единственной строке выходного файла выведите одно целое число – результат
изменения минимального числа цифр в числе `n`, чтобы полученное число
не имело ведущих нулей и делилось на `m`.
Если ответов несколько, можете вывести любой.
Если ответа не существует, выведите `-1`.
Пример ввода 1
123 10
Пример ввода 1
120
Пример ввода 2
123 141
Пример ввода 2
423
Пример ввода 3
9 123
Пример ввода 3
0
Пример ввода 4
12 123
Пример ввода 4
-1
G. Милый общий делитель
Простые числа, разложение на множителиОлимпиадные задачи на русском языке
| 25/10/2015 | Региональные отборочные командные соревнования для школьников (G) |
| 27/06/2018 | Лето 2018 - 2 (упрощенное) (C) |
| 17/07/2019 | Лето 2019 - 8 (упрощенное) (E) |
| 02/07/2020 | Лето 2020 - 2 (упрощенное) (C) |
Ограничения: время – 500ms/1s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (3)
Вася очень силен в подсчёте ворон за окном на уроках математики.
Сегодня выдался необычный день, ведь ворон было очень много.
К тому же, их было целых два вида: белые и чёрные. К середине урока Вася закончил подсчёт –
за окном оказалось `a` белых и `b` чёрных ворон.
Поскольку до конца урока было невыносимо много времени, Вася решил послушать, что говорит учитель.
Как раз в этот момент учитель рассказывал, что такое наибольший общий делитель двух чисел.
Вася очень талантливый мальчик и сразу понял, что к чему. Он моментально посчитал наибольший общий делитель чисел `a` и `b`.
После этого он придумал новый термин – милый общий делитель.
Милым общим делителем чисел `x` и `y` Вася решил назвать такое положительное целое число `d`,
что `x` делится на `d`, `y` делится на `d`, а сумма цифр числа `d` максимальна.
Помогите Васе найти милый общий делитель чисел `a` и `b`.
В единственной строке входного файла находятся два целых числа `a`, `b` (`1\ ≤\ a,\ b\ ≤\ 10^9`).
В единственной строке выходного файла выведите милый общий делитель чисел `a` и `b`.
Если ответов несколько, можете вывести любой.
Пример ввода
220 440
Пример вывода
55
H. Робот
Жадные алгоритмыПоразрядная сортировка и сортировка подсчетом
Олимпиадные задачи на русском языке
| 25/10/2015 | Региональные отборочные командные соревнования для школьников (H) |
| 30/06/2023 | Лето 2023-3 простые (командное) (C) |
| 28/06/2024 | Лето 2024-3 простые (командное) (C) |
Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Компания "Филипп индастриз" отправила на Марс новый робот-марсоход.
Целью робота является исследование поверхности Марса.
Для исследования Марса робот будет перемещаться по поверхности планеты
на север и на юг вдоль прямой. Программа робота состоит из `n`
команд, каждая из которых описывается целым числом `a_i`.
Каждое число `a_i` задаёт количество шагов, которое необходимо сделать роботу.
Если `a_i\ >\ 0`, то робот совершает `|a_i|` шагов на север, если `a_i\ <\ 0`, то `|a_i|` шагов
на юг. Робот исполняет команды последовательно, начиная с первой.
Однако по пути на Марс робот подвергся космическому излучению и его программа
могла повредиться. Запустив процедуру тестирования памяти, ученые выяснили,
что в программу было внесено от 0 до `k` ошибок следующего вида:
число `a_i` оказалось заменено на `-a_i`. Тем не менее, приземлившись
на Марс, робот выполнил свою, возможно поврежденную, программу.
Теперь для организации спасения робота ученые хотят выяснить, насколько далеко
от точки, в которой он начал выполнение программы, робот мог оказаться в результате.
Помогите им это выяснить.
В первой строке входного файла находятся два числа `n`, `k` (`1\ ≤\ k\ ≤\ n\ ≤\ 10^5`) –
количество чисел в программе робота и максимальное количество ошибок.
Во второй строке входного файла находятся `n` чисел `a_i` (`-10^4\ ≤\ a_i\ ≤\ 10^4`, `a_i\ ≠\ 0`) – программа робота.
В единственной строке выходного файла выведите максимальное расстояние в шагах, на которое мог
удалиться робот, выполнив все команды и совершив не более `k` ошибок.
Пример ввода 1
4 1 1 2 -1 -3
Пример вывода 1
5
Пример ввода 2
7 2 5 -3 7 9 -2 -8 -1
Пример вывода 2
29
Источник: XXIII Командный чемпионат школьников Санкт-Петербурга по программированию, 2015
I. Эстафета
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 25/10/2015 | Региональные отборочные командные соревнования для школьников (I) |
Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Каждый год в честь дня города в Южно-Берляндске проводится открытая эстафета.
В конкурсе участвуют команды из `k` человек, в процессе эстафеты
участники команды должна посетить `n` контрольных пунктов.
Контрольные пункты пронумерованы от 1 до `n`, место старта обозначим как пункт 0.
Соревнование проходит следующим образом: первый участник из команды стартует из пункта 0,
пробегает по некоторым `a_1` ранее не посещенным контрольным пунктам, возвращается в пункт 0 и
передает эстафету второму участнику. После этого второй участник пробегает какие-либо `a_2`
ранее не посещенных контрольных пунктов, возвращается и передает эстафету следующему. Эстафета продолжается,
пока последний участник не посетит `a_k` ранее не посещенных контрольных пунктов и не вернется на старт. Передача
эстафеты происходит мгновенно. Цель команды –
пробежать эстафету как можно быстрее.
Учащиеся Южно-Берляндского бегового училища решили заранее подготовиться к состязанию.
Они раздобыли план соревнования, из которого они узнали числа `a_i`, а также выяснили про каждую пару
пунктов, за какое время можно успеть добежать от одного до другого. Все участники
команды перемещаются с одинаковой скоростью, поэтому это время не зависит от того, кто
побежит между этими пунктами.
Помогите участникам составить маршрут, в котором команда пробежит эстафету как можно быстрее.
В первой строке находятся два целых числа `n` и `k` (`1\ ≤\ n\ ≤\ 18`, `1\ ≤\ k\ ≤\ n`) –
число контрольных пунктов и число участников в команде.
Во второй строке находятся `k` целых чисел `a_i` (`1\ ≤\ a_i\ ≤\ n`, `a_1\ +\ a_2\ +\ …\ +\ a_k\ =\ n`) –
число контрольных пунктов, которые должен пробежать `i`-й участник.
В следующих `n+1` строках находится по `n+1` целому числу `b_{i,j}` (`1\ ≤\ b_{i,\ j}\ ≤\ 10^6`, `b_{i,j}=b_{j,i}`,
`b_{i,i}=0`) – время, за которое можно добежать от `i`-го пункта до `j`-го для `i` и `j` от 0 до `n`.
В единственной строке выведите одно целое число – минимальное время, за которое команда
может пробежать эстафету.
Пример ввода 1
2 2 1 1 0 1 2 1 0 3 2 3 0
Пример вывода 1
6
Пример ввода 2
4 2 2 2 0 1 4 2 5 1 0 2 6 6 4 2 0 6 6 2 6 6 0 2 5 6 6 2 0
Пример вывода 2
16
J. Сапсан
Аналитическое решение уравнений, неравенств, систем уравненийОлимпиадные задачи на русском языке
| 25/10/2015 | Региональные отборочные командные соревнования для школьников (J) |
| 02/12/2023 | Марафон 80 задач, 7 этап (C) |
Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Лера часто ездит по работе из Санкт-Петербурга в Москву и обратно. Так как дела у нее всегда срочные, добирается до
места назначения она всегда на Сапсане. Как известно, в каждом вагоне Сапсана расположено ровно `n` мест, а именно `n/2` рядов
по два места в каждом (`n` четное).
Однажды по пути домой после деловой встречи у Леры не было соседа, и ей стало скучно. Поэтому она задалась вопросом:
сколько максимум человек можно посадить в вагон Сапсана, чтобы ровно у половины людей был сосед. Помогите
Лере ответить на этот сложный вопрос.
В первой и единственной строке входного файла дано число `n` (`2\ ≤\ n\ ≤\ 10^9`) – количество мест в вагоне Сапсана. Гарантируется,
что число `n` четное.
В единственной строке выходного файла выведите максимальное количество человек, которое можно посадить в вагон так, что ровно у половины
из них есть сосед.
Пример ввода
20
Пример вывода
12
Источник: XXIII Командный чемпионат школьников Санкт-Петербурга по программированию, 2015
K. Звезды на погонах
Аналитическое решение уравнений, неравенств, систем уравненийОлимпиадные задачи на русском языке
| 25/10/2015 | Региональные отборочные командные соревнования для школьников (K) |
Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (1)
В батальоне непонятного назначения действует правило, что
у каждого офицера должно быть не менее `a` и не более `b`
звезд на погоне, при этом ни у каких двух офицеров не должно быть
равного числа звезд.
В результате понижения в звании в батальон сослали офицера Й,
у которого на погоне до понижения было `c` звезд.
Теперь командиру батальона положено лишить его части звезд на погоне,
в результате чего число звезд на его погоне должно стать строго меньше `c`.
Командир батальона исследовал вопрос и выяснил, что
минимальное положительное число звезд, которое можно удалить с погона
офицера Й, чтобы правило выполнялось, равно `d`, а
максимальное – `e`. Командир незамедлительно сообщил об этом офицеру Й.
Теперь офицера Й заинтересовал вопрос: какое минимальное и максимальное
количество офицеров могло быть в батальоне до его прибытия? При этом командир
батальона сам офицером батальона не является, и на его погонах изображены
специальные загадочные символы, а не звезды.
В первой строке содержатся пять целых чисел `a`, `b`, `c`, `d`, `e`
(`1\ ≤\ a,\ b,\ c,\ d,\ e\ ≤\ 1000`, `a\ ≤\ b`, `a\ <\ c`, `d\ ≤\ e`).
Гарантируется, что ситуация корректна: офицера Й можно понизить
так, чтобы приведенное в условии правило выполнялось, а утверждение
командира является верным.
Выведите минимальное и максимальное возможное число офицеров в батальоне.
Пример ввода 1
10 18 20 5 8
Пример вывода 1
5 7
Пример ввода 2
2 10 5 1 3
Пример вывода 2
0 7
L. Пробки
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 25/10/2015 | Региональные отборочные командные соревнования для школьников (L) |
Ограничения: время – 2s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Недавно Женя устроился в компанию "Гуглекс", и сегодня его первый рабочий день.
Женя живет на другом берегу реки и для проезда на работу решил воспользоваться паромом.
Неожиданно он обнаружил, что съехать с парома на шоссе – не такая уж простая задача.
Машины на съезде с парома стоят в `n` полос, в `i`-й из которых стоит `c_i` машин,
а непосредственно перед съездом находится светофор. Раз в минуту
он включается зеленым и несколько машин с парома съезжают на берег.
Женя заметил, что за один зеленый сигнал светофоров количество машин, которые могут
успеть проехать со всех полос, суммарно не превосходит `k`.
Понимая, что он не один такой, кому не нравится стоять в пробках,
Женя ввел понятие "злости водителя". Злость водителя в некоторый момент времени
равна количеству машин,которые стоят перед ним в этот момент в той же полосе.
Например, если в полосе стоит 3 машины,
то у водителя, чья машина находится ближе всего к светофору,
злость равна 0, у следующего – 1, а у последнего – 2.
Как настоящий программист, Женя сразу же начал думать, как можно оптимизировать
процесс съезда с парома.
Оптимальным ему показался следующий вариант: в каждой полосе перед съездом поставить шлагбаум, который будет
за один зеленый сигнал светофора пропускать только определенное количество машин.
А именно, `i`-й полосе будет сопоставлено целое число
`k_i` – максимальное количество машин, которые могут съехать за один зеленый сигнал.
Сумма всех `k_i` должна быть равна `k`.
В качестве параметра оптимизации Женя выбрал суммарную злость всех водителей за все время съезда.
Каждую минуту после очередного включения зеленого света просуммируем злость всех еще не покинувших
паром водителей. Просуммируем получившиеся величины за все минуты, пока хотя бы один водитель еще находится
на пароме. Женя хочет подобрать `k_i` таким образом, чтобы получившаяся величина была минимальна.
Пока Женя стоит в пробке, помогите ему написать программу, находящую оптимальные `k_i`, чтобы он смог оправдаться перед
начальством за опоздание в первый же рабочий день.
В первой строке входного файла содержатся два числа `n`, `k` (`1\ ≤\ n\ ≤\ k\ ≤\ 300`) – количество полос на пароме и ограничение на количество
машин, проезжающих за один зеленый сигнал светофора со всех полос.
Во второй строке входного файла находятся `n` чисел `c_i` (`1\ ≤\ c_i\ ≤\ 100\ 000`) – количество машин,
стоящих в `i`-й полосе в начальный момент времени.
В первой строке выходного файла выведите число `a` – минимальную суммарную злость всех водителей за все время движения машин через светофоры.
В следующей строке выведите `n` натуральных чисел `k_i` – ограничения на количество машин, проезжающих за один зеленый сигнал,
для каждой полосы. Сумма чисел должна быть равна `k`. Если оптимальных решений несколько, можно вывести любое.
Пример ввода 1
3 4 1 2 4
Пример вывода 1
1 1 1 2
Пример ввода 2
3 4 1 2 6
Пример вывода 2
7 1 1 2
В первом тестовом примере в оптимальном ответе за первый зеленый сигнал светофоров через первый шлагбаум проедет 1 машина, через второй – 1, через третий – 2.
После этого злость оставшихся водителей будет равна `0+1+0=1` (в первом ряду не осталось машин, во втором ряду осталась одна машина,
злость ее водителя равна 0, в третьем ряду осталось две машины, злость водителей в них равны 1 и 0). За второй зеленый сигнал светофоров проедут
все оставшиеся машины. Получаем, что суммарная злость всех водителей за все время движения машин равна 1.
Во втором тестовом примере оптимальные числа `k_i` такие же, однако суммарная злость водителей другая. После первого зеленого сигнала светофоров
на первой полосе не останется машин, на второй полосе останется одна машина, злость ее водителя будет равна 0, а на третьей полосе останется
4 машины, злость водителей будет равна 3, 2, 1 и 0. После второго зеленого сигнала светофора на первой и второй полосах не останется машин,
а на третьей полосе останется 2 машины, злость их водителей будет равна 1 и 0. После третьего зеленого сигнала машин на пароме не останется.
Итого, суммарная злость водителей за все время равна `0+3+2+1+0+1+0=7`.
Источник: XXIII Командный чемпионат школьников Санкт-Петербурга по программированию, 2015