Автор Все варианты заданий с ответами и решением заключительного и отборочного этапа Московской олимпиады школьников МОШ по информатике 6, 7, 8, 9, 10, 11 класс материалы прошлых лет с официального сайта олимпиады для подготовки к олимпиаде 2024-2025 учебному году. Победители и призёры получают льготы при поступлении в ВУЗЫ.
2023-2024 учебный год
Отборочный этап для 6-9 классов:
Отборочный этап для 10-11 классов:
Заключительный этап для 6-9 класса:
Заключительный этап для 10-11 класса:
2022-2023 учебный год
Отборочный этап для 6-9 классов:
Отборочный этап для 10-11 классов:
Заключительный этап для 6-9 класса:
Заключительный этап для 10-11 класса:
2021-2022 учебный год
Заключительный этап для 6-9 класса:
Заключительный этап для 10-11 класса:
2020-2021 учебный год
Отборочный этап для 10-11 классов:
Заключительный этап для 6-9 класса:
Заключительный этап для 10-11 класса:
Интересные задания с олимпиады:
Задача A. Экзамен. В самом лучшем университете России есть специальный предмет, который называется «Теория Лени». Вы очень любите этот предмет и стараетесь постоянно использовать то, чему вас там научили. Но, как и везде, на нём есть устный экзамен. Всего есть n билетов, из которых вы выучили ровно a (ваша лень не позволяет вам выучить больше). Экзамен проходит в стандартном формате: есть стопка с билетами, каждый билет встречается в ней ровно один раз, и каждый студент случайно выбирает себе один билет. При этом, когда студент достал билет, то он забирает его себе и не возвращает обратно в стопку. Вы знаете, что до вас отвечали уже b человек, а это значит, что стопка содержит уже на b билетов меньше. Так как вас интересует не только «Теория Лени», но и математика (и даже чутьчуть информатика!), вы хотите узнать, какое минимальное и максимальное количество билетов из оставшихся вы можете знать.
Формат входных данных Первая строка содержит одно целое число n (1 6 n 6 109 ) — количество билетов на экзамене. Вторая строка содержит одно целое число a (1 6 a 6 n) — количество билетов, которые вы выучили. Третья строка содержит одно целое число b (0 6 b < n) — количество людей, которые уже взяли свой билет до вас.
Формат выходных данных Вывод вашей программы должен состоять из двух строк. Первая строка должна содержать единственное целое число — минимальное количество билетов, которое вы можете знать из оставшихся. Вторая строка должна содержать единственное целое число — максимальное количество билетов, которое вы можете знать из оставшихся.
Система оценки В данной задаче 10 тестов, помимо тестов из условия, каждый из них оценивается в 10 баллов. Результаты работы ваших решений на всех тестах будут доступны сразу во время соревнования. Решения, корректно работающие при a = 1, наберут не менее 20 баллов. Решения, корректно работающие при b = 1, наберут не менее 20 баллов.
Задача B. Разрез прямоугольника. У Пети есть прямоугольник размера a×b с целыми сторонами, хотя бы одна из которых больше 1. Он пробует разрезать этот прямоугольник на два прямоугольника с целыми сторонами, сделав разрез, параллельный какой-то из сторон исходного прямоугольника. Затем Петя пытается из двух получившихся прямоугольников сложить какой-то отличный от исходного прямоугольник, при этом он может как угодно поворачивать и двигать эти два прямоугольника. Если у него получается это сделать, то он называет прямоугольник a × b интересным. Обратите внимание, что если два прямоугольника отличаются поворотом на 90◦ , то они считаются одинаковыми. Например, прямоугольники 6 × 4 и 4 × 6 считаются одинаковыми. Таким образом, прямоугольник 2 × 6 является интересным, потому что его можно разрезать на два прямоугольника 2 × 3, после чего из этих двух прямоугольников сложить прямоугольник 4 × 3, который отличается от прямоугольника 2 × 6.
При этом прямоугольник 2×1 не является интересным, потому что его можно разрезать только на два прямоугольника 1×1, а из них можно сложить только прямоугольники 1×2 и 2×1, которые считаются одинаковыми с исходным. Также у Пети есть некоторое целое число n. Он хочет узнать, сколько существует различных интересных прямоугольников со сторонами, которые являются целыми числами, не превосходящими n. Помогите ему это сделать.
Задача C. Урок физкультуры. В известной школе прошёл урок физкультуры. Как полагается, всех построили в шеренгу и попросили рассчитаться на «первый–k-й». Как известно, расчёт на «первый–k-й» происходит следующим образом: первые k человек имеют номера 1, 2, 3, . . . , k, следующие k−1 человек имеют номера k−1, k−2, . . . , 1, следующие k−1 человек имеют номера 2, 3, . . . , k и т.д. Таким образом, расчёт повторяется через каждые 2k − 2 позиции. Примеры расчёта приведены в разделе «Замечание». Мальчик Вася постоянно всё забывает. Например, он забыл позицию, которую занимал в шеренге. Но он помнит число k, описанное выше, номер, который он получил при расчёте, а также, что его позиция в шеренге была не больше n. Другими словами, если Вася стоял на позиции y в шеренге, то y 6 n. Помогите Васе понять, сколько есть различных позиций в ряду, где он мог стоять.
Задача D. Самокат. В городе Новый Нижгород открылась новая служба доставки еды с оригинальным названием «Камосат». Курьеры этой службы передвигаются на самокатах и стремятся максимально эффективно доставлять заказы клиентам. Для того чтобы упростить задачу планирования маршрутов, был разработан алгоритм, основанный на топографии города. Город расположен вдоль реки, поэтому его можно представить одномерным массивом, где каждый элемент массива — это высота местности в соответствующей точке. Расстояние между двумя соседними точками считается равным 1. Каждый курьер начинает свой маршрут в некоторой точке города. Он может двигаться только вправо (по увеличению номеров элементов массива) и посещать только те точки, где высота меньше, чем в точке старта. Курьер стремится проехать как можно дальше, учитывая данное условие. Курьер, встретив местность не ниже, чем точка старта, не может продолжить путь. Помогите курьерам определить длину максимального маршрута, по которому они могут проехать, выбрав произвольную точку старта.
Задача F. Суммы модулей. Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 512 мегабайт Для последовательности целых чисел a1, a2, . . . , an и целого числа x обозначим через f(a, x) количество таких целых i от 1 до n, что ai 6 x. Для пары последовательностей целых чисел a1, a2, . . . , an и b1, b2, . . . , bn обозначим через g(a, b, c) сумму значений |f(a, x) − f(b, x)| по всем целым x, лежащим в отрезке [0, c]. Более формально, g(a, b, c) = Pc x=0 |f(a, x) − f(b, x)|. Вам даны два целых числа n и c, а также две последовательности целых чисел a1, a2, . . . , an и b1, b2, . . . , bn, все элементы которых лежат в отрезке [−1, c]. Известно, что ни в a, ни в b нет двух подряд идущих элементов, равных −1.
Скажем, что пара последовательностей целых чисел a 0 1 , a0 2 , . . . , a0 n и b 0 1 , b0 2 , . . . , b0 n , все элементы которых лежат в отрезке [0, c], соответствует шаблону (a, b), если выполняются следующие условия: • Для всех i (1 6 i 6 n), таких, что ai 6= −1, выполняется a 0 i = ai . • Для всех i (1 6 i 6 n), таких, что bi 6= −1, выполняется b 0 i = bi . • Для всех i (1 6 i 6 n − 1) выполняется a 0 i 6 a 0 i+1. • Для всех i (1 6 i 6 n − 1) выполняется b 0 i 6 b 0 i+1. Обозначим через h(a, b, c) сумму значений g(a 0 , b0 , c) по всем парам последовательностей (a 0 , b0 ), соответствующих шаблону (a, b). Вы должны посчитать h(a, b, c). Также вы должны обработать q запросов изменения последовательностей a и b и посчитать h(a, b, c) после каждого изменения. Обратите внимание, что ни в a, ни в b нет двух подряд идущих элементов, равных −1, ни до всех запросов, ни после какого-либо запроса.
Все олимпиады школьников по информатике:
Заключительный этап по информатике высшая проба задания и ответы