Задачи муниципального этапа олимпиады школьников по информатике 2020
1,2,3,4,5 (7-8 класс)
Ограничения: время – 200ms/200ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Напишите программу для робота, который движется по полю из пяти клеток с числами от 1 до 5 и может менять числа в соседних клетках.
Первоначально робот всегда находится на двух первых клетках слева. Ваша задача - написать программу для робота,
которая расставит числа по порядку от 1 до 5, независимо от их начального расположения.
Дополнительной подзадачей является минимизация количества перемещений робота по полю в худшем случае (подробнее ниже).
Для управления роботом вы можете использовать следующие команды:
Первая команда позволяет выбрать варианты действий в зависимости от чисел в клетках, на которых находится робот.
Вторая команда позволяет повторить заданное количество раз некоторую последовательность действий.
Команды движения позволяют перейти роботу на соседнюю клетку влево или вправо. Если выполнение команды движения невозможно, то она игнорируется.
Последняя команда позволяет поменять числа в клетках, на которых находится робот.
Например, для упорядочения перестановки на рисунке робот должен переместиться на 2 клетки вправо и выполнить обмен.
Эту последовательность действий можно задать следующей программой:
*Система оценки и описание подзадач*
||.u|Подзадача 1 (20 баллов)||
В этой подзадаче 1 тест, показанный на рисунке. Количество перемещений робота не учитывается.
||.u|Подзадача 2 (70 баллов)||
Числа от 1 до 5 на поле расположены в произвольном порядке. Количество перемещений робота не учитывается.
Необходимые подзадачи: 1.
В этой подзадаче 7 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
||.u|Подзадача 3 (10 баллов)||
Необходимые подзадачи: 1, 2.
В этой подзадаче 1 тест.
В зависимости от начального расположения чисел на клетках для их упорядочения может потребоваться разное количество перемещений робота по полю.
Существует перестановка, для которой теоретический минимум количества перемещений
для упорядочения этой перестановки является максимальным по сравнению с другими перестановками (худший случай). Пусть он равен `N`.
Программа запускается на всех возможных перестановках чисел от 1 до 5, и определяется
максимальное количество перемещений робота `M` (количество успешно выполненных команд движения робота),
которое потребуется для упорядочения какой-либо из этих перестановок (худший случай).
Тест считается пройденным, если `M` = `N`.
---
Для написания программы для робота используется [специальная версия среды Blockly](blockly/2522.html).
Вы можете использовать полную среду Blockly при решении других задач этого соревнования, выбрав пункт Blockly в информационном меню задачи.
Для проверки работы используйте кнопки:
Первая кнопка позволяет отправить ваше решение для проверки в проверяющую систему соревнований, вторая кнопка выполняет запуск программу локально, третья –
пошаговое выполнение или временная остановка программы, четвертая – завершение выполнения программы, после которой программа будет выполняться сначала.
Щелкая мышкой по клеткам начального состояния поля, можно задать исходный порядок чисел для тестирования программы.
Алгоритм (7-9 класс)
Ограничения: время – 200ms/300ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Реализуйте на одном из языков программирования алгоритм, представленный на схеме. Для проверки нечетности вычислите остаток от деления на 2.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 1000`).
Вторая строка ввода содержит одно целое число `M` (`1 <= M <= 1000`).
Вывести одно целое число — вычисленный ответ.
```sample Пример ввода
5
4
```
```sample Пример вывода
22
```
*Система оценки*
В этой задаче 5 тестов, каждый тест оценивается в 20 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
Две строки (9-11 класс)
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Даны две строки одинаковой длины из латинских букв.
Напишите программу, которая составляет из них новую строку,
выбирая для `i`-й буквы новой строки `i`-ю букву из первой или второй строки.
Новая строка должна содержать как можно больше повторений одной из букв.
Если существует несколько вариантов для новой строки, максимизирующих повторение какой-то буквы,
можно вывести любой из них.
Например, из строк BASIC и ABBAT, можно получить строки BBBIT (максимизируется повторение буквы B) или
AABAC (максимизируется повторение буквы A).
Первая строка ввода содержит первую строку из прописных латинских букв, вторая строку - вторую строку той же длины.
Вывести результирующую строку.
```sample Пример ввода
BASIC
ABBAT
```
```sample Пример вывода
BBBIT
```
*Система оценки и описание подзадач*
||.u|Подзадача 1 (50 баллов)||
Длина строк от 1 до 100 символов.
В этой подзадаче 5 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 2 (50 баллов)||
Необходимые подзадачи: 1.
Длина строк от 100 до 100000 символов.
В этой подзадаче 5 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат окончательной проверки на каждом тесте.
Лабиринт (7-8 класс)
Ограничения: время – 200ms/200ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
> Из книги Перельман Я. И. Лабиринты, 1931:
>
> Существует очень простой способ входить в любой лабиринт, не боясь в нем заблудиться. Пользуясь этим правилом, можно всегда найти обратный выход из всякого лабиринта, как бы запутаны ни были его переходы. Вот в чем состоит правило безопасного блуждания в лабиринтах:
"Надо ходить по лабиринту, все время касаясь его стенки одной и той же рукой." Это значит, что при входе в лабиринт вы должны коснуться его стенки одной рукой (все равно, правой или левой) и во все время блуждания в нем продолжать касаться стенки той же самой рукой.
Лабиринт имеет размеры `5 xx 5`, между некоторыми клетками могут быть стены. В начальном состоянии робот находится на клетке с координатами (1,1) и
направлен на клетку (1,2), как показано на рисунке.
Ваша задача - написать программу, которая приведет робота в клетку с координатами (5,5), пользуясь правилом одной руки.
После завершения выполнения программы робот должен находится в клетке (5,5), направление не важно.
Для управления роботом вы можете использовать следующие команды:
Команда "двигаться вперед" перемещает робота вперед на следующую клетку, если впереди нет стенки.
Если выполнение команды невозможно, то она игнорируется. Следующие команды выполняют поворот робота.
Остальные команды можно использовать в логических условиях в циклах и ветвлениях.
*Система оценки*
В задаче 10 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте. Первый тест совпадает с лабиринтом на рисунке.
Гарантируется, что во всех лабиринтах существует путь из клетки (1,1) в клетку (5,5).
---
Для написания программы для робота используется [специальная версия среды Blockly](blockly/2523.html).
Вы можете использовать полную среду Blockly при решении других задач этого соревнования, выбрав пункт Blockly в информационном меню задачи.
Для проверки работы используйте кнопки:
Первая кнопка позволяет отправить ваше решение для проверки в проверяющую систему соревнований, вторая кнопка выполняет запуск программу локально, третья –
пошаговое выполнение или временная остановка программы, четвертая – завершение выполнения программы, после которой программа будет выполняться сначала.
Щелкая мышкой по промежуткам между клетками начального состояния поля, можно задать расположение стен для тестирования программы.
Перестановка (9-11 класс)
Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Дана строка, состоящая из 0 и 1.
Необходимо переставить некоторые символы в строке так, чтобы в получившейся строке подстрока 00 появлялась ровно один раз.
Напишите программу, которая определяет минимальное количество обменов символов в заданной строке
для получения строки с единственной подстрокой 00.
Первая строка ввода содержит строку из 0 и 1.
Вывести одно целое число - минимальное количество обменов.
Если невозможно переставить символы в строке так, чтобы получить строку с единственной подстрокой 00, то вывести -1.
```sample Пример ввода 1
1001
```
```sample Пример вывода 1
0
```
```sample Пример ввода 2
0100000111
```
```sample Пример вывода 2
2
```
```sample Пример ввода 3
10000
```
```sample Пример вывода 3
-1
```
Пояснение к примеру 1: В исходной строке ничего не нужно менять.
Пояснение к примеру 2: Нужно выполнить 2 обмена, например, 5-й символ строки с 10-м и 7-й с 8-м.
Получится строка 0100101010.
Пояснение к примеру 3: Возможные перестановки строки: 10000 (3 подстроки 00), 01000 (2 подстроки 00), 00100 (2 подстроки 00), 00010 (2), 00001 (3).
После любых перестановок в строке будет не менее 2 подстрок 00.
*Система оценки и описание подзадач*
||.u|Подзадача 1 (50 баллов)||
Длина строки от 2 до 15 символов.
В этой подзадаче 10 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 2 (50 баллов)||
Необходимые подзадачи: 1.
Длина строки от 16 до 1000 символов.
В этой подзадаче 5 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат окончательной проверки на каждом тесте.
Смешанные команды (все классы)
Ограничения: время – 200ms/300ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
На соревнования по спортивному программированию к участию допускаются
только смешанные команды из 3 участников (1 мальчик и 2 девочки или 1 девочка и 2 мальчика).
В школе учатся `N` девочек и `M` мальчиков. Напишите программу, вычисляющую максимальное количество
команд, которое можно составить из учащихся этой школы.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 10^{12}`) — количество девочек в школе.
Вторая строка ввода содержит одно целое число `M` (`1 <= M <= 10^{12}`) — количество мальчиков в школе.
Вывести одно целое число — вычисленный ответ.
```sample Пример ввода 1
3
4
```
```sample Пример вывода 1
2
```
```sample Пример ввода 2
3
10
```
```sample Пример вывода 2
3
```
Пояснение к примеру 1: из 3 девочек и 4 мальчиков можно составить 2 смешанных команды: либо 2 команды (1д+2м), либо
(1д+2м) и (2д+1м).
Пояснение к примеру 2: из 3 девочек и 10 мальчиков можно составить 3 смешанных команды в составе (1д+2м), 4 мальчика не будут участвовать в соревнованиях.
*Система оценки и описание подзадач*
||.u|Подзадача 1 (60 баллов)||
`1 <= N <= 1000`, `1 <= M <= 1000`
В этой подзадаче 6 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 2 (30 баллов)||
Необходимые подзадачи: 1.
`1000 < N <= 10^9`, `1000 < M <= 10^9`
В этой подзадаче 5 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 3 (10 баллов)||
Необходимые подзадачи: 1,2.
`10^9 < N <= 10^{12}`, `10^9 < M <= 10^{12}`
В этой подзадаче 2 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат окончательной проверки на каждом тесте.
Форсаж (все классы)
Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Маша и Витя играют в игру "Форсаж" с помощью кубика, двух фишек в форме машин и трассы из `N+1` клеток пронумерованных от 0 до `N`.
В начале игры обе машины стоят на клетке 0. Затем участники игры по очереди бросают кубик
и перемещают свою машину вперед на количество клеток, равное выпавшему на кубике количеству очков.
Если фишка одного из игроков достигает клетки с номером `N`, игра заканчивается.
Если на кубике выпадает 6, то участник делает ход и бросает кубик ещё раз. Пока у игрока выпадает 6 очков, он продолжает делать ход
и бросать кубик снова (режим форсажа).
Напишите программу, определяющую положение фишек после `M` бросков кубика. Если игра заканчивается раньше, чем будут выполнены все `M` бросков,
то определить положение фишек в момент окончания игры.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 1000`) - длина трассы для гонки.
Вторая строка ввода содержит одно целое число `M` (`1 <= M <= 1000`) - количество бросков кубика.
Следующие `M` строк содержат по одному целому числу от 1 до 6 - количество очков, выпавшее на кубики при очередном броске.
Вывести в первой строке позицию фишки первого игрока в момент окончания игры или после `M` бросков кубика.
Во второй строке вывести позицию фишки второго игрока.
```sample Пример ввода 1
100
3
4
6
2
```
```sample Пример вывода 1
4
8
```
```sample Пример ввода 2
5
4
3
2
4
2
```
```sample Пример вывода 2
5
2
```
Пояснение к примеру 1: 1-й участник бросает кубик и перемещает фишку на клетку 4, 2-й участник получает на кубике 6 очков,
перемещает фишку на клетку 6, повторно бросает кубик и перемещает фишку на клетку 8.
Пояснение к примеру 2: 1-й участник бросает кубик и перемещает фишку на клетку 3, 2-й участник бросает кубик и
перемещает фишку на клетку 2, ход получает 1-й игрок, который бросает кубик, достигает финиша на клетке 5. Игра на этом заканчивается.
Оставшийся бросок кубика не используется.
*Система оценки*
В этой задаче 10 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
Японский кроссворд (10-11 класс)
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (1)
Издательство публикует книгу-раскраску с упрощенными японскими кроссвордами для дошкольников.
В отличие от обычных японских кроссвордов в упрощенном кроссворде числа находятся
со всех сторон сетки кроссворда, но указано ровно одно число, как показано на рисунке.
Если число находится слева от сетки кроссворда, это означает, что от левого края сетки должно быть закрашено
указанное количество клеток по горизонтали.
Аналогично, число справа указывает количество закрашенных клеток по горизонтали от правого края, а числа
сверху и снизу от сетки указывают количество закрашенных клеток по вертикали от верхнего и нижнего края сетки по
вертикали соответственно. Пример закрашенного кроссворда показан на рисунке.
Напишите программу, с помощью которой издатель сможет проверить корректность публикуемых кроссвордов.
Первая строка ввода содержит одно целое число `N` (`2 <= N <= 100000`) - размер кроссворда.
Далее следует четыре строки содержащие по `N` целых чисел от 0 до `N` - числа записанные по сторонам сетки кроссворда.
Сначала указаны числа слева от сетки кроссворда в порядке сверху вниз, далее числа справа от сетки кроссворда сверху вниз, далее
числа над сеткой слева направо, и в последней строке - числа под сеткой кроссворда слева направо.
Вывести сообщение YES, если числа не противоречат друг другу, иначе вывести сообщение NO.
```sample Пример ввода 1
3
3 2 0
3 0 1
2 2 1
0 0 1
```
```sample Пример вывода 1
YES
```
```sample Пример ввода 2
3
3 0 1
3 2 1
3 2 3
1 0 3
```
```sample Пример вывода 2
NO
```
Пояснение к примеру 2: Первое число сверху равное 3
противоречит числу 0 слева и числу 2 справа во втором ряду, а также числу 1 снизу.
Если сделать закраску трех клеток сверху, эти три числа станут неверными. В правильном кроссворде либо первое число сверху равно 1, либо все указанные числа должны быть равны 3.
*Система оценки и описание подзадач*
||.u|Подзадача 1 (60 баллов)||
`2 <= N <= 1000`.
В этой подзадаче 12 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 2 (40 баллов)||
Необходимые подзадачи: 1.
`1000 < N <= 100000`.
В этой подзадаче 10 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат окончательной проверки на каждом тесте.
Начало
Соревнования
Олимпиадные задачи на русском языке