Начало
Соревнования
Задачи муниципального этапа олимпиады школьников по информатике 2017
1. Покраска забора
Разбор случаевОлимпиадные задачи на русском языке
| 03/11/2017 | Муниципальный этап 7-8 классы (1) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (1)
Том покрасил часть забора, начиная с доски под номером `A` до доски под номером `B` включительно.
Затем Том взял новое ведро с извёсткой и покрасил часть забора, начиная с доски под номером `C` до доски
под номером `D` включительно, при этом часть забора могла быть покрашена дважды. Кроме того Том мог
красить доски забора как справа налево, так и слева направо.
Напишите программу, вычисляющую общее количество покрашенных досок забора.
Первая строка ввода содержит четыре целых числа `A`, `B`, `C` и `D`, разделенных
пробелами (`1\ ≤\ A,\ B\ ≤\ 10^9`, `1\ ≤\ C,\ D\ ≤\ 10^9`) – диапазоны номеров досок забора, покрашенных Томом.
Вывести одно целое число – общее количество покрашенных досок.
Пример ввода 1
1 2 6 4
Пример вывода 1
5
Пример ввода 2
1 6 2 4
Пример вывода 2
6
Описание подзадач и системы оценивания
Подзадача 1 (50 баллов)
`1\ ≤\ A,\ B\ ≤\ 1000`, `1\ ≤\ C,\ D\ ≤\ 1000`
В этой подзадаче 5 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (50 баллов)
Необходимые подзадачи: 1.
`1\ ≤\ A,\ B\ ≤\ 10^9`, `1\ ≤\ C,\ D\ ≤\ 10^9`
В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
2. Числа-палиндромы
Сложение и вычитание длинных целых, умножение и деление на короткоеОлимпиадные задачи на русском языке
| 03/11/2017 | Муниципальный этап 7-8 классы (2) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Будем называть число палиндромом, если оно одинаково читается слева направо
и справа налево. Например, палиндромами будут числа 5, 121 и 2112, а число 1210
палиндромом не является.
Напишите программу, которая находит наименьшее число-палиндром, строго большее
заданного числа `N`.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10^{100}`).
Вывести одно целое число – первое число-палиндром больше `N`.
Пример ввода
2017
Пример вывода
2112
Описание подзадач и системы оценивания
Подзадача 1 (50 баллов)
`1\ ≤\ N\ ≤\ 10^6`
В этой подзадаче 5 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (50 баллов)
Необходимые подзадачи: 1.
`10^6\ <\ N\ ≤\ 10^{100}`
В этой подзадаче 5 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
3. Алгоритм
Реализация алгоритма по его схемеОлимпиадные задачи на русском языке
| 03/11/2017 | Муниципальный этап 7-8 классы (3) |
| 28/08/2023 | Реализация алгоритма по схеме (проводит BOGAT) (G) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Реализуйте на одном из языков программирования алгоритм,
представленный на схеме. Операция mod находит остаток от деления, а div – производит
деление нацело.
В первой строке ввода содержится одно целое число `N` (`1 ≤ N ≤ 2*10^9`).
Вывести одно целое число — вычисленный ответ.
Пример ввода
72
Пример вывода 1
3
Система оценки
В этой задаче 10 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест
начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
3. Медианный элемент
Дерево отрезков, декартово дерево, √-декомпозицияОлимпиадные задачи на русском языке
| 03/11/2017 | Муниципальный этап 10-11 классы (3) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Будем называть `i`-й элемент последовательности `a_1,\ a_2,\ …,\ a_N` медианным, если количество элементов,
меньших или равных `a_i` среди элементов `a_1,\ a_2,\ …,\ a_{i-1}`, больше или равно количеству элементов, больших
или равных `a_i` среди элементов `a_{i+1},\ a_{i+2},\ …,\ a_N`. В последовательности может быть несколько медианных элементов.
Напишите программу, которая находит минимальный индекс медианного элемента.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 100000`). Вторая строка ввода содержит `N` целых чисел
в диапазоне от 1 до `10^9`, разделенных пробелами – последовательность `a_1,\ a_2,\ …,\ a_N`.
Вывести в первой строке одно целое число — минимальный индекс медианного элемента.
Пример ввода 1
4 1 2 5 10
Пример вывода 1
3
Пример ввода 2
4 10 5 2 1
Пример вывода 2
1
Описание подзадач и системы оценивания
Подзадача 1 (50 баллов)
`1\ ≤\ N\ ≤\ 1000`
В этой подзадаче 5 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (50 баллов)
Необходимые подзадачи: 1.
`1000\ <\ N\ ≤\ 100000`
В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
4. НОД подпоследовательностей
Сокращение перебора с помощью идеиДеревья (map, set), хэш-таблицы
Олимпиадные задачи на русском языке
| 03/11/2017 | Муниципальный этап 9 класс (4) |
Ограничения: время – 2000ms/4000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Наибольший общий делитель (НОД) двух чисел может вычислен по формуле:
НОД(a,b)=a, если b=0;
НОД(a,b)=НОД(b, a mod b), если b>0.
НОД нескольких чисел вычисляется последовательным применением НОД к парам чисел:
НОД(a,b,c)=НОД(НОД(a,b),c)
НОД(a)=a
Напишите программу, которая находит НОД для всех непрерывных подпоследовательностей
`a_i,\ a_{i+1},\ …,\ a_j` (где `1\ ≤\ i\ ≤\ j\ ≤\ N`) в заданной последовательности `a_1,\ a_2,\ …,\ a_N` и
определяет количество различных значений среди них.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 500000`).
Вторая строка ввода содержит `N` целых чисел в диапазоне от 1 до `10^18`, разделенных пробелами – последовательность
`a_1,\ a_2,\ …,\ a_N`.
Вывести одно целое число – количество различных значений среди НОД для всех непрерывных подпоследовательностей
в заданной последовательности.
Пример ввода 1
4 9 6 2 4
Пример вывода 1
6
Пример ввода 2
4 9 6 3 4
Пример вывода 2
5
Пояснение к примеру 1:
НОД(9)=9; НОД(6)=6; НОД(2)=2; НОД(4)=4; НОД(9, 6)=3; НОД(6, 2)=2; НОД(2, 4)=2;
НОД(9, 6, 2)=1; НОД(6, 2, 4)=2; НОД(9, 6, 2, 4)=1
Из этих 10 значений различными являются 1, 2, 3, 4, 6, 9.
Описание подзадач и системы оценивания
Подзадача 1 (30 баллов)
`1\ ≤\ N\ ≤\ 1000`, числа от 1 до `10^6`
В этой подзадаче 6 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (20 баллов)
`2\ ≤\ N\ ≤\ 1000`, числа от 1 до `10^18`
Необходимые подзадачи: 1.
В этой подзадаче 4 теста, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (25 баллов)
`1000\ <\ N\ ≤\ 100000`, числа от 1 до `10^6`
Необходимые подзадачи: 1.
В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 4 (25 баллов)
`100000\ ≤\ N\ ≤\ 500000`, числа от 1 до `10^18`
Необходимые подзадачи: 1,2,3.
В этой подзадаче 25 тестов, каждый тест оценивается в 1 балл. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
4. Робот в лабиринте
Олимпиадные задачи на русском языкеИсполнители
| 03/11/2017 | Муниципальный этап 7-8 классы (4) |
| 02/09/2024 | Входное соревнование 1 курс (проводит admin) (H) |
Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Робот движется по лабиринту 4x4 под управлением программы,
состоящей из следующих команд управления: N – идти на соседнюю клетку в северном
направлении (вверх), S – идти на юг (вниз), E – на восток (вправо), W – на запад (влево).
Если на пути робота стоит стена, то команда не выполняется. Робот сообщает
для каждой команды, удалось ли ее выполнить или нет.
Строка сообщений робота содержит в `i`-й позиции символ "+",
если робот смог выполнить `i`-ю команду, и символ "-", если `i`-ю команду
выполнить не удалось. При выполнении программы робот побывал в каждой
клетке лабиринта и попробовал пройти через каждую внутреннюю стенку лабиринта
и, возможно, через несколько внешних стен, которые находятся по периметру поля лабиринта.
Перед началом выполнения программы робот находился в неизвестной клетке лабиринта.
| Программа | EWNSWENESENWNWWESEENWSENSWSWSSWNESEEEN |
| Сообщения робота | ++-+-+-+--+-++++-++-+++--++++-++++++-+ |
По результатам выполнения программы восстановите внутреннюю
структуру лабиринта и напишите две новых программы. В качестве решения вы
должны выслать текстовый файл, содержащий ровно две строки. В первой строке нужно
написать программу для решения первой подзадачи, во второй строке — для решения
второй подзадачи. Если вы не можете написать программу для решения одной
из подзадач, поставьте в соответствующей строке символ "-" (минус).
Система оценки и описание подзадач
Подзадача 1 (40 баллов)
В этой подзадаче только 1 тест. Робот должен пройти из клетки A в клетку B.
Программа должна быть минимальной длины.
Подзадача 2 (60 балла)
В этой подзадаче 15 тестов, каждый тест оценивается в 4 балла. До
выполнения программы робот находится в некоторой клетке, определяемой номером теста,
а после завершения программы должен находиться в клетке A. Длина программы
может быть любой, но не более 1000 команд. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки для всех подзадач (без разделения на отдельные тесты).
