Задачи муниципального этапа олимпиады школьников по информатике 2021
1. Упаковка (все классы)
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Полу нужно упаковать четыре прибора, имеющих кубическую форму, с размерами стороны (длина ребра куба) `A`, `B`, `C`, `D` соответственно.
Для транспортировки Пол использует кубические коробки с размером стороны `E`. Он может
поместить несколько приборов в одну коробку, заполнив оставшееся место гранулами полистирола.
Определите минимальное количество коробок, необходимых для упаковки.
Ввод содержит пять целых чисел `A`, `B`, `C`, `D`, `E` (`1 <= A <= B <= C <= D <= E <= 1000`), по одному числу в строке -- размеры приборов в неубывающем порядке и
размеры коробки для упаковки.
Вывести одно целое число -- вычисленный ответ.
```sample Пример ввода 1
1
2
3
4
7
```
```sample Пример вывода 1
1
```
```sample Пример ввода 2
2
2
2
2
2
```
```sample Пример вывода 2
4
```
Пояснение к примеру 1: все приборы можно упаковать в одну коробку.
Пояснение к примеру 2: для каждого прибора потребуется отдельная коробка.
*Система оценки*
В этой задаче 10 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
2. Алгоритм (7-9 класс)
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Реализуйте на одном из языков программирования алгоритм, представленный на схеме.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 1000000`).
Вывести одно целое число — вычисленный ответ.
```sample Пример ввода
99
```
```sample Пример вывода
4
```
*Система оценки*
В этой задаче 5 тестов, каждый тест оценивается в 20 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
2. Парный танец (10-11 класс)
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Чани готовит танцевальный номер к празднику Воды.
Для танца "Ручеек" участников номера нужно разделить на пары из мальчика и девочки.
Чани хочет разбить детей на пары так,
чтобы суммарная разница в росте по всем парам была минимальна.
Напишите программу, которая определит, какую минимальную суммарную разницу может получить Чани.
Первая строка ввода содержит одно целое число `N` (`2 <= N <= 100`) -- количество пар в танцевальном номере.
Вторая строка ввода содержит `N` целых чисел в диапазоне от 1000 до 1800 -- рост мальчиков в мм.
Третья строка ввода содержит `N` целых чисел в диапазоне от 1000 до 1800 -- рост девочек в мм.
Вывести одно целое число -- минимальную суммарную разницу в росте по всем парам.
```sample Пример ввода
3
1500 1600 1505
1490 1501 1610
```
```sample Пример вывода
24
```
Пояснение к примеру: минимальная суммарная разница получится, если составить пары так: (1500,1490), (1505,1501), (1600,1610).
Сумма будет равна `|1500-1490| + |1505-1501| + |1600-1610| = 10 + 4 + 10 = 24`.
*Система оценки*
В этой задаче 10 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
3. Обратный порядок (7-8 класс)
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Напишите программу для робота, который движется по области из 12 разноцветных клеток и может перекрашивать их в различные цвета.
Первоначально робот всегда находится на клетке с номером 1.
Ваша задача -- написать программу для управления роботом, которая поменяет порядок цветов на обратный.
Для управления роботом вы можете использовать следующие команды:
Первые две команды позволяют роботу перемещаться в соответствующем направлении.
Если выполнение команды движения невозможно, то она игнорируется.
Третья команда позволяет покрасить текущую клетку в указанный цвет. Значение цвета можно взять из переменной.
Четвертая команда позволяет узнать цвет текущей клетки, а пятая -- её номер.
Шестая и седьмая команды используются для арифметических вычислений.
Восьмая команда используется для получения значения переменной, а девятая -- для установки нового значения.
Добавить новую переменную можно в в разделе "Переменные", щелкнув по кнопке "Создать переменную" и введя её имя. В переменных можно хранить числовые значения и цвета.
Последняя команда используется для повторения некоторой последовательности действий указанное количество раз.
Например, чтобы покрасить клетку 8 в цвет, как у клетки 1, можно использовать следующую программу:
*Система оценки и описание подзадач*
||.u|Подзадача 1 (20 баллов)||
В этой подзадаче 1 тест, показанный на рисунке.
После выполнения программы цвета должны поменять порядок на обратный, как показано на рисунке:
||.u|Подзадача 2 (80 баллов)||
В этой подзадаче 4 теста.
Необходимые подзадачи: 1.
Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
---
Для написания программы для робота используется [специальная версия среды Blockly](blockly/2592.html).
Вы можете использовать полную среду Blockly при решении других задач этого соревнования, выбрав пункт Blockly
в информационном меню задачи.
Для проверки работы используйте кнопки:
Первая кнопка позволяет отправить ваше решение для проверки в проверяющую систему соревнований, вторая кнопка выполняет запуск программу локально, третья –
пошаговое выполнение или временная остановка программы, четвертая -- завершение выполнения программы, после которой программа будет выполняться сначала.
Щелкая мышкой по клеткам начального состояния, можно задать начальную раскраску клеток для тестирования программы.
3. Фуршет (9-11 класс)
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Владимир пригласил гостей на фуршет по поводу своей победы.
На праздничном столе расставлен ряд из `N` блюд `T_1, T_2, ... T_N`, где `T_i` обозначает тип `i`-го блюда.
Перед приходом гостей Владимир решил немного перекусить, для этого он выбрал один тип блюда и стал есть блюда только этого типа.
Так как отсутствие нескольких блюд подряд на столе будет слишком заметно, Владимир ест только блюда,
между которыми не менее `K` других блюд.
Определите, какой тип блюд должен выбрать Владимир, чтобы съесть как можно больше блюд.
Первая строка ввода содержит два целых числа -- количество блюд `N` (`1 <= N <= 100000`) и минимальное
пропускаемых количество блюд `K` (`1 <= K <= 100`).
Вторая строка содержит `N` целых чисел `T_i` -- номера типов блюд.
Вывести два целых числа -- номер типа блюда и количество съеденных блюд.
Если несколько типов блюд обеспечивают максимум количества блюд, то выведите минимальный номер типа из них.
```sample Пример ввода 1
5 1
1 2 2 1 2
```
```sample Пример вывода 1
1 2
```
```sample Пример ввода 2
5 1
1 1 1 1 1
```
```sample Пример вывода 2
1 3
```
Пояснение к примеру 1: Владимир может съесть блюда с №№1,4 (тип 1) или блюда с №№2,5 (тип 2) или блюда с №№3,5 (тип 2).
Так как количество блюд во всех случаях равно 2, то выводим наименьший номер типа -- 1.
Пояснение к примеру 2: Владимир может съесть блюда с №№1,3,5 (тип 1).
*Система оценки и описание подзадач*
||.u|Подзадача 1 (40 баллов)||
`1 <= N <= 100`, `1 <= T_i <= 100`, `K=1`
В этой подзадаче 4 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 2 (30 баллов)||
`100 <= N <= 100000`, `1 <= T_i <= 100000`, `K=1`
Необходимые подзадачи: 1.
В этой подзадаче 3 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 3 (30 баллов)||
`100 <= N <= 100000`, `1 <= T_i <= 10^9`, `1< K <= 100`
Необходимые подзадачи: 1, 2.
В этой подзадаче 3 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
4. Высадка (9-11 класс)
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
На планете Арракис вокруг пустыни расположены `N` поселений. В `i`-м поселении может разместиться `P_i` колонистов.
Челнок, доставляя новых колонистов с орбиты, делает `M` рейсов.
`j`-й рейс приземляется возле поселения `X_j` и привозит `K_j` колонистов.
Часть колонистов остается в поселении `X_j`. Те, для кого места в этом поселении нет, движутся вокруг пустыни наземным транспортом в
следующие поселения, в порядке увеличения номера поселения. После `N`-го поселения следующим является поселение с номером 1.
Если в следующем поселении есть места, то часть колонистов остается там. Остальные продолжают движение.
Для каждого рейса нужно подсчитать расходы на перевозку колонистов наземным транспортом, как сумму
расстояний, на которое нужно перевезти каждого колониста. Расстояние между соседними поселениями будем считать равным 1.
Первоначально все поселения пустые и заполняются по мере выполнения рейсов.
Первая строка ввода содержит одно целое число `N` (`2 <= N <= 100000`) -- количество поселений.
Вторая строка ввода содержит `N` целых чисел `P_i` (`1 <= P_i <= 10^9`) -- вместимость поселений.
Третья строка ввода содержит одно целое число `M` (`1 <= M <= 100000`) -- количество рейсов.
Следующие `M` строк содержат по два целых числа -- номер поселения, возле которого приземляется челнок `X_j` (`1 <= X_j <= N`) и
количество колонистов в челноке `K_j` (`1 <= K_j <= 10^9`).
Гарантируется, что сумма всех `K_j` не превышает суммы всех `P_i`.
Для каждого рейса вывести на отдельной строке расходы на перевозку колонистов наземным транспортом.
```sample Пример ввода
5
3 3 4 5 1
2
2 11
3 3
```
```sample Пример вывода
12
6
```
Пояснение к примеру: Из 11 прибывших 1-м рейсом колонистов 3 остаются в поселении №2,
4 остаются в поселении №3, 4 -- в поселении №4. Расходы на перевозку равны `3*0+4*1+4*2=12`.
После размещения колонистов в поселениях остается следующее количество свободных мест: (3,0,0,1,1).
Из 3 прибывших 2-м рейсом колонистов 1 остается в поселении №4,
1 - в поселении №5, еще 1, проехав поселение №5, доезжает до поселения №1. Расходы на перевозку равны `1*1+1*2+1*3=6`.
*Система оценки*
||.u|Подзадача 1 (40 баллов)||
`1 <= N <= 100`, `1 <= M <= 100`, `1 <= P_i <= 100`, `1 <= K_j <= 100`
В этой подзадаче 4 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
||.u|Подзадача 2 (30 баллов)||
`100 < N <= 1000`, `100 < M <= 1000`, `1 <= P_i <= 10^9`, `1 <= K_j <= 10^9`
Необходимые подзадачи: 1.
В этой подзадаче 3 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
||.u|Подзадача 3 (30 баллов)||
`1000 < N <= 100000`, `1000 < M <= 100000`, `1 <= P_i <= 10^9`, `1 <= K_j <= 10^9`
Необходимые подзадачи: 1, 2.
В этой подзадаче 3 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
4. Клад (7-8 класс)
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Напишите программу для робота, который движется по полю размером `5 xx 5` клеток.
Первоначально робот всегда находится в клетке в верхнем левом углу. В одной из клеток находится
закопанный клад.
Ваша задача -- написать программу для управления роботом, которая поможет найти и раскопать клетку с кладом.
Для управления роботом вы можете использовать следующие команды:
Первые четыре команды позволяют роботу перемещаться в соответствующем направлении. Если выполнение команды движения невозможно, то она игнорируется.
Пятая команда позволяет раскопать текущую клетку. Можно раскапывать любую клетку.
Шестая и седьмая команда используется в условиях цикла и ветвления для проверки, что робот стал ближе к кладу (теплее) или дальше от клада (холоднее)
после перемещения. Если робот не сдвинулся с места (еще не было перемещений или попытка перемещения не была успешной), то обе проверки будут ложными. (Расстояние вычисляется как длина отрезка между центром клетки, на которой находится робот, и центром клетки с кладом).
Последние две команды позволяют узнать текущие координаты робота.
Дополнительно вы можете использовать команды для циклов, ветвлений, арифметических действий.
Например, при расположении клада в центре поля робот должен переместиться на 2 клетки вправо и 2 клетки вниз, затем начать копать.
Эту последовательность действий можно задать следующей программой:
*Система оценки и описание подзадач*
||.u|Подзадача 1 (10 баллов)||
В этой подзадаче 1 тест, показанный на рисунке. Нет ограничений на количество перемещений и раскопок.
||.u|Подзадача 2 (30 баллов)||
В этой подзадаче 1 тест. Программа запускается 25 раз на всех возможных размещениях клада.
Нет ограничений на количество перемещений и раскопок.
Необходимые подзадачи: 1.
Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 3 (30 баллов)||
В этой подзадаче 1 тест. Программа запускается 25 раз на всех возможных размещениях клада. Нет ограничений на количество перемещений.
Можно выполнить раскопку только один раз.
Необходимые подзадачи: 1, 2.
Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 4 (30 баллов)||
В этой подзадаче 1 тест. Программа запускается 25 раз на всех возможных размещениях клада.
Количество перемещений робота в процессе поиска клада не должно превышать 10.
Учитываются только успешные перемещения. Можно выполнить раскопку только один раз.
Необходимые подзадачи: 1, 2, 3.
Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
---
Для написания программы для робота используется [специальная версия среды Blockly](blockly/2593.html).
Вы можете использовать полную среду Blockly при решении других задач этого соревнования, выбрав пункт Blockly в информационном меню задачи.
Для проверки работы используйте кнопки:
Первая кнопка позволяет отправить ваше решение для проверки в проверяющую систему соревнований, вторая кнопка выполняет запуск программу локально, третья –
пошаговое выполнение или временная остановка программы, четвертая -- завершение выполнения программы, после которой программа будет выполняться сначала.
Щелкая мышкой по клеткам начального состояния поля, можно задать начальное положение клада для тестирования программы.
5. Сумма минимумов (7-8 класс)
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Рассмотрим все возможные подсписки списка из `N` элементов. Подсписком называется часть списка с `i`-го до `j`-го элемента, где `1 <= i<=j <= N`.
В каждом подсписке найдем минимальное значение.
Например, для списка [3,1,2,5] получаются следующие подсписки и их минимумы.
Подсписок|Минимум
---------|-------
[3]|3
[3,1]|1
[3,1,2]|1
[3,1,2,5]|1
[1]|1
[1,2]|1
[1,2,5]|1
[2]|2
[2,5]|2
[5]|5
Сумма минимумов по всем возможным подспискам равна `3+1+1+1+1+1+1+2+2+5=18`.
Напишите программу, которая находит сумму минимумов по всем возможным подспискам
для заданного списка из `N` элементов.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 35000`) -- количество элементов в списке.
Следующие `N` строк содержат по одному целому числу `A_i` (`1 <= A_i <= 10000`) -- элементы списка.
Вывести одно целое число -- сумму минимумов.
```sample Пример ввода
4
3
1
2
5
```
```sample Пример вывода
18
```
*Система оценки и описание подзадач*
||.u|Подзадача 1 (30 баллов)||
`1 <= N <= 100`, `1 <= A_i <= 100`
В этой подзадаче 3 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 2 (40 баллов)||
`100 <= N <= 2000`, `1 <= A_i <= 1000`
Необходимые подзадачи: 1.
В этой подзадаче 4 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 3 (30 баллов)||
`2000 <= N <= 35000`, `1 <= A_i <= 10000`
Необходимые подзадачи: 1, 2.
В этой подзадаче 3 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
5. Экспедиция (9-11 класс)
Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В некоторых точках длинной прямой дороги, идущей через пустыню,
расположены посадочные площадки.
Известны расстояния от начала дороги до каждой из площадок.
Несколько экспедиций хотят добраться до разных точек на дороге.
Для этого каждая экспедиция должна сначала высадиться на одной из площадок
(не обязательно ближайшей к нужной точке), затратив на это определенное количество топлива для вертолета,
а затем проехать от площадки до нужной точки по дороге, затратив дополнительное топливо на каждую единицу пути.
Напишите программу, которая рассчитает для каждой экспедиции, какое минимальное количество топливо необходимо для
доставки экспедиции в заданную точку.
В первой строке ввода содержатся три целых числа: количество площадок `N` (`1 <= N <= 10^5`),
количество экспедиций `M` (`1 <= M <= 10^5`) и затраты топлива на проезд одной единицы дороги `C` (`1 <= C <= 10^9`).
Далее следует `N` строк, содержащих по два целых числа: расстояние от начала дороги до `i`-й
площадки `A_i` (`0 <= A_i <= 10^9`) и затраты топлива для доставки экспедиции на `i`-ю площадку
`B_i` (`1 <= B_i <= 10^9`). Все площадки расположены в разных точках дороги.
Далее следует `M` строк, содержащих одно целое числа: расстояние от начала дороги до цели `j`-й экспедиции `D_j` (`0 <= D_j <= 10^9`).
Для каждой экспедиции вывести одно целое число на отдельной строке -- минимальное количество топлива для доставки экспедиции в заданную точку.
```sample Пример ввода
3 2 1
200 300
300 100
100 250
150
110
```
```sample Пример вывода
250
260
```
Пояснение к примеру: первая экспедиция высаживается на второй площадке (на расстоянии 300 от начала дороги),
затратив 100 единиц топлива, а затем проезжает до точки 150, затратив еще 150 единиц топлива.
Вторая экспедиция высаживается на третьей площадке (на расстоянии 100 от начала дороги), затратив 250 единиц топлива, а
затем проезжает до точки 110, затратив еще 10 единиц топлива.
*Система оценки и описание подзадач*
||.u|Подзадача 1 (30 баллов)||
`N = 1`, `M = 1`
В этой подзадаче 5 тестов, каждый тест оценивается в 6 баллов. Баллы за каждый тест начисляются независимо.
||.u|Подзадача 2 (40 баллов)||
`1 < N <= 1000`, `1 < M <= 1000`
Необходимые подзадачи: 1.
В этой подзадаче 5 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 3 (30 баллов)||
`1000 < N <= 100000`, `1000 < M <= 100000`
Необходимые подзадачи: 1, 2.
В этой подзадаче 3 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Начало
Соревнования
Разбор случаев