Автор Всероссийская олимпиада школьников по информатике муниципальный этап 2023 ответы, решения и задания для 7, 8, 9, 10, 11 класса 2023-2024 учебный год для школьников Московской области олимпиада прошла 2 декабря 2023.
Задания для 7-8 класса олимпиада по информатике муниципальный этап 2023
zadanie-7-8klass-informatika-vos-2023Задания для 9-11 класса олимпиада по информатике муниципальный этап 2023
zadanie-9-11klass-informatika-vos-2023Задания для 7-8 класса
Задача A. Новые книги Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Эта задача с открытыми тестами. Ее решением является набор ответов, а не программа на языке программирования. Тесты указаны в самом условии, от вас требуется лишь ввести ответы на них в тестирующую систему. Ира очень любит программирование и математику.
Недавно друзья подарили Ире много новых книг — A книг по математике и B книг по программированию. Ира выделила отдельную книжную полку для новых книг, на которую их поместится не более K штук. Ира выяснила, что в каждой книге по математике содержится X новых для неё фактов, а в каждой книге по программированию — Y новых фактов. Стоит отметить, что все факты уникальны, и никакой факт не встречается в наборе книг дважды. Ира хочет выбрать не более K книг таким образом, чтобы суммарное количество новых фактов в выбранных книгах было как можно больше. Помогите Ире посчитать, какое максимальное количество новых фактов она сможет узнать, если оставит на полке не более K книг.
Формат выходных данных Для каждого теста выведите одно число — максимальное количество новых фактов, которое может получить Ира, если оставит не более K книг. Система оценки Каждый тест оценивается независимо в 10 баллов. Замечание Пусть Ире подарили 5 книг по математике и 3 по программированию. В каждой книге по математике встречается 2 новых факта, а в каждой книге по программированию 3. На полку Ира сможет поставить не более 4-х книг. В таком случае оптимально взять 3 книги по программированию и 1 по математике, чтобы узнать 3 · 3 + 1 · 2 = 11 новых фактов.
Задача B. Мыт на реке Яуза Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Мыт (или мыто) — государственная пошлина в Древней Руси. Название города «Мытищи» произошло именно от этого слова, однако «мытище» — совсем не большой мыт, а место, где мыт собирали. Образовано по аналогии со словами пожарище — место, где был пожар; городище — место, где был город. Эта задача с открытыми тестами. Ее решением является набор ответов, а не программа на языке программирования.
Тесты указаны в самом условии, от вас требуется лишь ввести ответы на них в тестирующую систему. В Москву на продажу плыл на лодке купец и вёз товар: i граммов икры и m граммов мёда. В столице на рынке он может продать икру по цене a рублей за грамм и мёд по цене b рублей за грамм. На его пути есть участок суши, где лодку нужно тащить волоком от реки Яуза до реки Клязьма. В этом месте расположен пункт сбора мыта. Мыт возможно уплатить не только деньгами, но и товаром. Так что купец может оставить в качестве уплаты пошлины на таможне одно из трёх: • v рублей • c граммов икры • d граммов мёда Посчитайте, какое максимальное количество денег сможет заработать купец при оптимальной стратегии, если у него изначально есть хотя бы v рублей. Гарантируется, что изначально у купца есть товар (икра и мед) на сумму более, чем v рублей, то есть i · a + m · b > v.
Формат входных данных Формат выходных данных Для каждого теста введите в тестирующую систему единственное число — максимально возможную прибыль купца в рублях. Система оценки Каждый тест оценивается независимо в 10 баллов. Замечание Например, если i = 5, m = 10, a = 2, b = 3, v = 7, c = 3, d = 3, то купцу выгоднее всего уплатить мыт икрой и в этом случае его прибыль будет равна 4 рубля за оставшуюся икру + 30 рублей за мед, то есть суммарно 34 рубля. Если i = 5, m = 10, a = 1, b = 3, v = 10, c = 6, d = 3, то купцу выгоднее всего уплатить мыт мёдом и в этом случае его прибыль будет равна 5 рублей за икру + 21 рубль за оставшийся мёд, то есть суммарно 26 рублей. Обратите внимание, что купец не может уплатить мыт икрой, так как у него недостаточно икры для уплаты мыта икрой. Если i = 5, m = 10, a = 2, b = 3, v = 7, c = 4, d = 3, то купцу выгоднее всего уплатить мыт деньгами и в этом случае его прибыль будет равна 10 рублей за икру + 30 рублей за мёд — 7 рублей в качестве мыта, то есть суммарно 33 рубля.
Задача C. Поиск сокровищ Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Эта задача с открытыми тестами. Ее решением является набор ответов, а не программа на языке программирования. Тесты указаны в самом условии, от вас требуется лишь ввести ответы на них в тестирующую систему. Валерий и Геннадий — друзья, они провели весь год в поисках сокровищ. Всего за год им удалось откопать n сундуков с сокровищами, в каждом из которых находятся монеты. Валерий и Геннадий хотят поровну разделить найденные монеты из каждого сундука между собой. Но есть проблема — в некоторых сундуках количество монет нечетное и в таком случае разделить их поровну нельзя. Валерий и Геннадий обратились к Вам за помощью. По их мнению, Вы можете выполнять только следующие операции: 1. Пересыпать все монеты из i-го сундука в j-й сундук (после чего i-й сундук становится пустым); 2. Если все монеты в сундуке можно разделить между Валерием и Геннадием поровну, то вы отдаете равное количество монет каждому из них; Помогите Валерию и Геннадию и скажите им максимальное количество монет, которое сможет получить каждый из них. Формат входных данных n — количество сундуков с золотом. n целых чисел ai обозначают количество монет в сундуках.
Формат выходных данных Выведите одно целое число — максимальное количество монет, которое может получить каждый из друзей. Система оценки Каждый тест оценивается независимо в 10 баллов. Замечание Рассмотрим пример n = 3, количество монет в сундуках: 1, 8, 2. Второй сундук можно разделить поровну между друзьями — каждый получит по четыре монеты. Также можно разделить третий сундук — каждый получит по одной монете. Но куда бы мы ни переложили золото из первого сундука, мы не сможем разделить монеты поровну, поэтому ответ 4 + 1 = 5 — монет получит каждый из друзей.
Задача D. Шоу с дельфинами Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В известном дельфинарии ставят шоу с дельфинами. В этом году организаторы решили добавить в шоу новый номер и удивить зрителей математическими навыками дельфинов. Дельфины умеют складывать числа, но делают это специфическим образом — они склеивают два числа. Например, из чисел 12 и 3 дельфин может получить число 123 путём «сложения». Тренер готовит дельфина к новому номеру и тренирует его — он показывает ему последовательно n карточек с числами.
Для каждого нового числа дельфин должен определить, можно ли его получить «сложением» каких-то двух карточек, которые тренер показывал ранее. Если число на текущей карточке можно получить «сложением» числа с увиденной ранее карточки два раза подряд, то это тоже учитывалось. Как только дельфин видит число, которое можно получить «сложением» увиденных ранее карточек — он издает специальный звук. Определите, сколько раз за тренировку дельфин издаст специальный звук. Формат входных данных Первая строка содержит одно целое число n (1 6 n 6 106 ) — количество показанных карточек. Вторая строка содержит n целых чисел a1, a2, …, an(0 6 ai < 106 ) — числа на карточках, записанные без ведущих нулей. Формат выходных данных Выведите одно целое число — количество раз, которое дельфин издаст специальный звук. Система оценки Каждый тест оценивается независимо в 4 балла. Если Ваше решение корректно работает при n 6 200, оно получит не менее 28 баллов.
Замечание Обратите внимание, что если мы используем карточку с 0, то в результате получается число с ведущим нулем. Например, в последовательности 0, 1, 1 ответ для последней карточки будет отрицательным, т.к. 01 не совпадает с 1. Рассмотрим пример из условия: пусть были показаны карточки 1, 23, 123, 11, 21, 1, 2311 именно в таком порядке. Тогда, увидев карточку 123, дельфин вспомнил, что ранее уже видел карточки 1 и 23, числа на которых при последовательной записи дают 123. Аналогично, увидев 11, дельфин смог представить это число как дважды повторенное число с карточки 1, а увидев 2311, дельфин смог представить это число как последовательную запись 23 и 11. Итого, дельфин издал специальный звук 3 раза.
Задания для 9-11 класса
Задача A. Поддержание бодрости Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Игорь начинает готовиться к олимпиаде, которая состоится через N дней. Игорь готовится к олимпиаде по вечерам, после того, как возвращается из школы и делает всю домашнюю работу. Каждый вечер Игорь может либо учиться, либо лечь спать пораньше. Если Игорь сегодня ложится спать пораньше, его уровень бодрости повышается на A единиц, если учится — снижается на B единиц. Игорь хочет составить себе расписание на каждый день — для каждого дня выбрать, будет ли он учиться или ляжет спать пораньше. При этом Игорь хочет составить расписание на N дней таким образом, чтобы учиться как можно больше дней, а его уровень бодрости через N дней должен быть таким же, как и сейчас.
Определите, сможет ли Игорь составить себе такое расписание, и, если сможет, вычислите, сколько дней Игорь будет учиться. Считается, что уровень бодрости может быть отрицательным. Формат входных данных В первой строке вводится натуральное число N (1 6 N 6 1018) — количество дней до олимпиады. Во второй строке вводится натуральное число A (1 6 A 6 1018) — число единиц, на которое повышается бодрость Игоря за каждый день, когда он выбирает лечь спать пораньше. В третьей строке вводится натуральное число B (1 6 B 6 1018) — число единиц, на которое понижается бодрость Игоря за каждый день, когда он выбирает учиться. Гарантируется, что N · A 6 1018 Формат выходных данных Если Игорь не сможет составить себе расписание, удовлетворяющее условиям, выведите −1. Если Игорь сможет составить себе расписание, удовлетворяющее условиям, выведите количество дней учебы в этом расписании. Система оценки Гарантируется, что решения, работающие корректно при n 6 105 , будут получать не менее 50 баллов.
Замечание В первом примере из условия Игорь может учиться 3 дня, а отдыхать один. За каждый день учебы его бодрость уменьшается на 2, то есть всего уменьшается на 6, а за день отдыха — увеличивается на 6. Таким образом, его уровень бодрости через 4 дня останется таким же. Во втором примере из условия если Игорь один день отдыхает, а второй учится, его уровень бодрости сначала увеличится на 1, а потом уменьшится на 2. Таким образом, через 2 дня он будет на 1 меньше, чем был изначально. В случае, если Игорь будет 2 дня учится, его уровень бодрости уменьшится на 4, а если будет 2 дня отдыхать, его уровень бодрости увеличится на 2. Таким образом, не существует сценария, при котором его уровень бодрости не изменится за 2 дня. Поэтому, в этом примере ответ на задачу −1.
Задача B. История о ферматисте Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Эта задача с открытыми тестами. Ее решением является набор ответов, а не программа на языке программирования. Тесты указаны в самом условии, от вас требуется лишь ввести ответы на них в тестирующую систему. Однажды всемирно известный Доцент, вновь доказывая Великую теорему Ферма, обнаружил удивительное свойство! Взяв 4 различных простых числа A, B, C, D, он заметил, что произведение A·B и произведение C · D дают одинаковые остатки от деления на некоторое натуральное число K.
Как настоящий Доцент, он решил узнать, при каком максимальном K может выполняться такое равенство. К сожалению, сейчас Доцент слишком занят доказательством теоремы Ферма, поэтому он поручил эту задачу Вам. Формат входных данных. Формат выходных данных Выведите единственное число — максимальное K, при котором выполняется равенство. Система оценки Каждый тест оценивается независимо в 10 баллов. Замечание Рассмотрим пример, при котором A = 3, B = 5, C = 11, D = 2. A · B = 15, C · D = 22. Тогда можно заметить, что при K > 22 остатки от деления на K не будут меняться и будут различны. Легко убедиться, что для K 6 22 максимальное значение, при котором выполняется нужное равенство, будет K = 7.
Задача C. Ресторанный бизнес Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт Эта задача с открытым тестированием. Решения по этой задаче тестируются «в открытую», во время олимпиады. Вы можете не дожидаться окончания олимпиады, чтобы узнать итоговый балл вашего решения по этой задаче. Как известно, Тимур — лучший поставщик продуктов во всей Московской области. В Московской области существует всего n ресторанов, в c из которых Тимур уже поставляет продукты.
Также, m пар ресторанов являются соседями друг для друга, при этом ресторан не может быть соседом сам себе и никакие два ресторана не могут быть соседями дважды. Так как Тимур не разбирается в рекламе, то новости о его качественной работе распространяются только с помощью сарафанного радио, а именно — ресторан решает нанять Тимура как поставщика, если хотя бы в k соседей этого ресторана Тимур уже поставляет продукты. Тимур очень дальновидный, поэтому его интересует, какие из ресторанов однажды наймут его как поставщика. Но так как сейчас он занят развозом товара, он поручил эту непростую задачу Вам!
Формат входных данных Первая строка содержит три целых числа n, m, k (1 6 k 6 n 6 2·105 , 1 6 m 6 min( n·(n−1) 2 , 2·105 )), обозначающие количество ресторанов, количество пар соседей и количество соседей, необходимое для того, чтобы ресторан нанял Тимура, соответственно. В следующих m строчках содержится описание пар соседних ресторанов. Каждая строка содержит два различных целых числа ui , vi — номера двух ресторанов, соседних друг другу (1 6 ui , vi 6 n, ui 6= vi). Гарантируется что одна и та же пара не встречается в этом списке дважды. В следующей строке содержится целое число c (0 6 c 6 n), обозначающее количество ресторанов, в которые Тимур с самого начала поставляет продукты. В следующей строке содержится c различных целых чисел от 1 до n — номера ресторанов, в которые Тимур уже поставляет продукты.
Формат выходных данных В первой строке выведите целое число a — количество ресторанов, которые однажды наймут Тимура как поставщика. Во второй строке выведите a целых чисел — номера всех ресторанов, в которые Тимур будет поставлять продукты, в любом порядке . Система оценки Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся при прохождении всех тестов этой группы, а также при прохождении тестов необходимых подгрупп. Баллы за соответствующие группы указаны в таблице.
Задача D. Мега OR Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 3 секунды Ограничение по памяти: 256 мегабайт Эта задача с открытым тестированием. Решения по этой задаче тестируются «в открытую», во время олимпиады. Вы можете не дожидаться окончания олимпиады, чтобы узнать итоговый балл вашего решения по этой задаче. Однажды Саше попалась последовательность a, состоящая из 109 целых неотрицательных чисел. Ему известны значения первых n элементов последовательности, остальные элементы равны нулю. Саша любит битовые операции и структуры данных, поэтому он решил дать Вам следующую задачу: необходимо выполнить q запросов. Запросы бывают двух типов: 1 i v — заменить элемент с индексом i на число v, т.е. присвоить ai = v. 2 z — вычислить количество целых неотрицательных чисел x, таких что (a1 or a2 or … or a109 or x) 6 z
Напишите программу, которая сможет обработать эти запросы достаточно быстро. Формат входных данных В первой строке входных данных содержится одно целое число n (1 6 n 6 100 000) — количество первых элементов массива a, которые знает Саша. Во второй строке содержится n целых чисел a1, a2, … an (0 6 ai 6 2 30 − 1). В третьей строке входных данных содержится одно целое число q (1 6 q 6 100 000) — количество запросов. Следующие q строк описывают запросы. В каждой из них находится числo t (1 6 t 6 2) — тип запроса. Если t = 1, то в строке содержатся еще два целых числа i и v (1 6 i 6 109 , 0 6 v 6 2 30 − 1). Если t = 2, то в строке содержится еще одно целое число z (0 6 z 6 2 30 − 1). Формат выходных данных Для каждого запроса второго типа в отдельной строке выведите ответ на запрос. Система оценки Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся при прохождении всех тестов этой группы, а также при прохождении тестов необходимых подгрупп. Баллы за соответствующие группы указаны в таблице. Исключение составляют группы 1 и 2, которые оцениваются за каждый пройденный тест отдельно.
Региональный этап 2023 по информатике 9, 10, 11 класс задания и ответы
Региональный этап 2023 по информатике 9, 10, 11 класс задания и ответы олимпиады