Задачи муниципального этапа олимпиады школьников по информатике 2024

1. Пирожки (все классы)

Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

В кошельке у Анны было ровно $X$ рублей, и она смогла купить на них $N$ одинаковых пирожков. Оставшихся после покупки денег не хватит на покупку ещё одного такого же пирожка. Определите минимальную возможную стоимость одного пирожка в рублях.

Например, для $X=14$ Анна может купить ровно $N=2$ пирожков при стоимости 5 рублей (останется 4 рубля), 6 рублей (останется 2 рубля) или 7 рублей (останется 0 рублей). Минимальная стоимость – 5 рублей. Для некоторых вариантов $X$ и $N$ (например, $X=6$ и $N=4$ ) не существует искомой стоимости пирожка в целых числах – при стоимости 1 рубль Анна может купить 6 пирожков, а при стоимости 2 рубля – 3 пирожка.

В первой строке ввода находится целое число $X$ ( $1<=X<=10^12$ ) – количество рублей у Анны до покупки. Во второй строке ввода находится целое число $N$ ( $1<=N<=X$ ) – количество купленных пирожков.

Выведите одно целое число – минимальную стоимость пирожка в рублях, при которой описанная ситуация возможна. Если такой стоимости не существует (как в примере для $X=6$ и $N=4$ ), выведите -1 вместо стоимости.

Пример ввода 1

14
2

Пример вывода 1

Пример ввода 2

10
5

Пример вывода 2

Система оценки и описание подзадач

Подзадача 1 (50 баллов)

$1<=N<=X<=10^4$ , гарантируется, что существует положительный ответ.

Подзадача 2 (30 баллов)

$10^3<=N<=X<=10^12$ , гарантируется, что существует положительный ответ.

Необходимые подзадачи: 1

Подзадача 3 (20 баллов)

Ограничения из условий задачи, ответ может быть отрицательным.

Необходимые подзадачи: 1, 2

Баллы за каждую из подзадач начисляются только в случае, если все тесты для этой подзадачи успешно пройдены. По запросу сообщается о первой ошибке в тестах подзадачи.

2 или 4. Склад (все классы)

Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Егор работает на складе. Каждый день ему поступают $N$ заказов на получение цепей из заданного количества звеньев $L_i$ . Обычно Егор отматывает от бесконечной катушки с цепью $L_i$ звеньев, разгибает $L_i$ -ое звено, чтобы отцепить цепь от катушки, затем сгибает снова это звено, получая цепь нужной длины. Марина предложила Егору разгибать $L_i+1$ -ое звено, но при этом к концу дня у Егора будут оставаться $N$ одиночных разогнутых звеньев. Егор хотел бы, чтобы после выполнения всех заказов, у него не оставалось одиночных звеньев. Из них можно собирать некоторые цепи, выбрав правильный порядок выполнения заказов.

Напишите программу, которая определяет минимальное количество звеньев, которые придется разогнуть и согнуть Егору.

В первой строке ввода содержится единственное целое число $N$ ( $1<=N<=10^5$ ) – количество заказов. Во второй строке ввода содержатся $N$ целых чисел $L_i$ ( $1 <= L_i <= 10^5$ ) – длина цепи в $i$ -ом заказе.

Выведите единственное целое число – минимальное количество звеньев, которые нужно разогнуть и согнуть.

Пример ввода

5
5 2 4 6 1

Пример вывода

Пояснение к примеру: Егор может отделить цепи длиной 5, 4, 6 по способу, предложенному Мариной, а из 3 одиночных звеньев сделать цепи длиной 2 и 1. Это на 2 звена меньше, чем при способе, который он использовал ранее.

Пример ввода 2

1
5

Пример вывода 2

Система оценки и описание подзадач

Подзадача 1 (60 баллов)

$1<=N<=100$

В этой подзадаче 6 тестов, каждый тест оценивается в 10 баллов.

Подзадача 2 (40 баллов)

Ограничения из условий задачи.

Необходимые подзадачи: 1

В этой подзадаче 4 теста, каждый тест оценивается в 10 баллов.

Во всех подзадачах баллы за каждый тест начисляются независимо. По запросу сообщается результат окончательной проверки на каждом тесте.

2. Алгоритм (7-8 класс)

Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Реализуйте на одном из языков программирования алгоритм, представленный на схеме. Операция mod находит остаток от деления (обозначается % в С и Python).

Алгоритм

Первая строка ввода содержит одно целое число $N$ ( $1 <= N <= 1000000000$ ).

Вывести два целых числа – вычисленный ответ.

Пример ввода 1

Пример вывода 1

10 4

Пример ввода 2

Пример вывода 2

0 1

Система оценки

В этой задаче 5 тестов, каждый тест оценивается в 20 баллов. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки на каждом тесте.

3. Коттеджный поселок (9-11 класс)

Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Василий руководит строительством элитного коттеджного поселка, имеющего форму прямоугольника с противоположными углами в точках (0, 0) и ( $W$ , $H$ ). Василий собирается проложить несколько узких (настолько узких, что их ширина считается нулевой) внутренних проездов, которые разобьют весь поселок на участки прямоугольной формы с целочисленными сторонами. Каждый из участков должен быть огорожен высоким забором точно по периметру. Смежные участки огораживаются независимо друг от друга, то есть внутренние проезды между участками окружаются заборами с обеих сторон. Стороны участков, совпадающие с внешними границами поселка, также должны быть огорожены.

Василий уже договорился с поставщиком о поставке стройматериалов, поэтому общая длина заборов в поселке теперь должна в точности равняться $L$ . Помогите Василию нарисовать любой подходящий план поселка или определите, что сделать это невозможно.

В единственной строке ввода находятся три целых числа: длина поселка $W$ , ширина поселка $H$ ( $1 <= W,H <= 100$ ) и требуемая длина заборов $L$ ( $2H + 2W <= L <= 10^9$ ).

Если создать требуемый план поселка невозможно, выведите единственную строку, содержащую -1. Если создать план возможно, в первой строке выведите число $N$ – количество участков. Затем выведите $N$ строк, описывающих прямоугольные участки. Каждая строка должна содержать четыре целых числа – координаты противоположных углов участка в порядке: $x_1$ , $y_1$ , $x_2$ , $y_2$ ( $0<=x_1,x_2<=W$ , $0<=y_1,y_2<=H$ ). Прямоугольники должны полностью покрывать территорию поселка без наложений и пропусков, и их суммарный периметр должен равняться $L$ . Если существует несколько подходящих планов, выведите любой из них.

Пример ввода 1

4 2 20

Пример вывода 1

План для примера 1 изображен на рисунке.

Пример

Участки имеют периметры 6, 6 и 8 соответственно.

Пример ввода 2

4 2 99

Пример вывода 2

-1

Система оценки и описание подзадач

Подзадача 1 (15 баллов)

$H=1$ , остальные ограничения из условий задачи.

Подзадача 2 (30 баллов)

$H=2$ , остальные ограничения из условий задачи.

Необходимые подзадачи: 1

Подзадача 3 (55 баллов)

Ограничения из условий задачи.

Необходимые подзадачи: 1, 2

Баллы за каждую из подзадач начисляются только в случае, если все тесты для этой подзадачи успешно пройдены. По запросу сообщается о первой ошибке.

Хотя примеры ввода не соответствуют ограничениям подзадачи 1, ваше решение должно давать правильный ответ и на этих примерах для выполнения дальнейшего тестирования.

3. Рисование снежинки (7-8 классы)

Ограничения: время – 200ms/200ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Пора готовить новогодние украшения, можно украсить комнату снежинками. Для этого нужно взять квадратный лист бумаги, сложить его вдвое трижды, сделать несколько вырезов и снова развернуть лист – снежинка готова.

Снежинка

Напишите в Blockly программу для робота, который анализирует расположение цветов в треугольнике в верхнем углу квадратного поля $9 xx 9$ клеток и выполняет их отражение по трём осям симметрии на остальные части поля.

vertical-align: middle|Начало $->$

Для написания программы управления роботом вы можете использовать следующие блоки, заданные в категории "Робот":

Команды робота

Первые четыре команды позволяют роботу перемещаться в соответствующем направлении. Если выполнение команды движения невозможно, то она игнорируется.

Пятая команда позволяет переместить робота в клетку с указанными координатами.

Шестая команда позволяет перекрасить клетку, на котором находится робот, в указанный цвет.

Остальные команды позволяет узнать цвет текущей клетки и координаты текущей клетки.

Для создания переменной в категории "Переменные" нужно щелкнуть по кнопке "Создать переменную" и ввести её название, например, "цвет". После этого в категории "Переменные" появятся блоки для получения и изменения значения переменной.

Например, чтобы скопировать цвет из клетки (1,1) в клетку (1,2), нужно выполнить программу:

Программа

Нажимая на клетки поля, можно задать цвета для рисования снежинки.

В категориях "Логические" и "Циклы" можно найти блоки для ветвления и циклов, в категории "Математика" – блоки для математических операций.

Для запуска программы используйте кнопки:

Кнопки

Первая кнопка позволяет отправить ваше решение для проверки в проверяющую систему соревнований, вторая кнопка выполняет запуск программу локально, третья – пошаговое выполнение или временная остановка программы, четвертая – завершение выполнения программы, после которой программа будет выполняться сначала.

Система оценки и описание подзадач

Подзадача 1 (10 баллов)

Необходимо нарисовать снежинку из начального состояния на рисунке.

Начало

В этой подзадаче 1 тест, показанный на рисунке.

Подзадача 2 (20 баллов)

Все клетки треугольника для рисования снежинки имеют одинаковый цвет как показано на рисунке, т.е. снежинка будет одноцветным квадратом.

Начало

В этой подзадаче 2 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.

Подзадача 3 (30 баллов)

Клетки треугольника для рисования снежинки покрашены горизонтальными полосами как показано на рисунке.

vertical-align: middle|Начало $->$

Необходимые подзадачи: 2.

В этой подзадаче 3 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.

Подзадача 4 (40 баллов)

Клетки треугольника для рисования снежинки могут иметь любой цвет.

Необходимые подзадачи: 1,2,3.

В этой подзадаче 4 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки на каждом тесте.

Обратите внимание, что баллы за подзадачу 1 и подзадачу 2 будут просуммированы, только если решена подзадача 4.

Для написания программы для робота используется специальная версия среды Blockly. Вы можете использовать полную среду Blockly при решении других задач этого соревнования, выбрав пункт Blockly в информационном меню задачи.

4. Справедливые подмассивы-2 (9-11 класс)

Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

У $K$ людей есть общий массив из $N$ целых чисел. Любой его подмассив от $L$ до $R$ (то есть элементы, стоящие в позициях от $L$ до $R$ включительно, $1<=L<=R<=N$ ) они делят между собой следующим образом:

первое число достается первому человеку,
второе число – второму человеку,
…,
$K$ -тое число достается $K$ -тому человеку,
$K+1$ -ое число – снова первому,
$K+2$ -ое число – снова второму,
и так далее по кругу.

При этом длина подмассива не обязательно делится на $K$ , то есть разные люди могут получить разное количество чисел.

Если после деления подмассива суммы чисел у всех людей оказались равны друг другу, то такой подмассив называют справедливым. Подсчитайте, сколько различных справедливых подмассивов можно выбрать из заданного массива. Подмассивы считаются различными, если отличаются их левые или правые границы.

В первой строке ввода содержатся два целых числа: $N$ – размер массива ( $1<=N<=10^5$ ) и $K$ – количество людей ( $2<=K<=5$ ). Во второй строке ввода содержатся $N$ целых чисел $a_i$ – элементы массива ( $-10^9 <= a_i <= 10^9$ ).

Выведите единственное целое число – количество справедливых подмассивов.

Пример ввода

7 2
1 2 1 3 4 1 1

Пример вывода

Пояснение к примеру 1. Справедливыми являются следующие подмассивы: от 6 до 7 - [1 1], от 1 до 3 - [1 2 1], от 4 до 6 - [3 4 1], от 2 до 5 - [2 1 3 4], от 1 до 6 - [1 2 1 3 4 1], от 2 до 7 - [2 1 3 4 1 1]. В каждом из этих подмассивов сумма элементов, стоящих на четных местах, равна сумме элементов, стоящих на нечетных местах.

Пример ввода

2 2
0 0

Пример вывода

Пояснение к примеру 2. Cправедливыми являются все подмассивы: от 1 до 1 - [0], от 2 до 2 - [0], От 1 до 2 - [0, 0].

Система оценки и описание подзадач

Подзадача 1 (20 баллов)

$N<=100$ , $K=2$ , $-10 <= a_i <= 10$

Подзадача 2 (20 баллов)

$N<=1500$ , $K=2$ , $-10 <= a_i <= 10$

Необходимые подзадачи: 1.

Подзадача 3 (20 баллов)

$N<=10^5$ , $K=2$ , $-10 <= a_i <= 10$

Необходимые подзадачи: 1, 2.

Подзадача 4 (20 баллов)

$N<=10^5$ , $K=2$ , $-10^9 <= a_i <= 10^9$

Необходимые подзадачи: 1, 2, 3.

Подзадача 5 (20 баллов)

Ограничения из условий задачи.

Необходимые подзадачи: 1, 2, 3, 4

Баллы за каждую из подзадач начисляются только в случае, если все тесты для этой подзадачи успешно пройдены. По запросу сообщается о первой ошибке.

5. Круговая порука (9-11 класс)

Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Все сотрудники департамента, в котором работает Дмитрий, делятся на честных и коррумпированных, причем все знают друг про друга, кто кем является. В департамент прибыла проверка, всех сотрудников усадили за круглый стол и задали каждому один и тот же вопрос: сколько коррумпированных среди следующих $K$ сотрудников справа от вас? Все честные сотрудники отвечали верно. А коррупционеры стремились запутать проверяющих и всегда давали ответ, отличающийся от истинного ровно на 1. То есть, если справа $X$ коррупционеров, то коррумпированный сотрудник назовет число $X+1$ или $X-1$ (но не меньше 0: если справа все сотрудники честные, то единственный возможный ответ - это 1). Помогите по результатам опроса установить минимальное и максимальное возможное количество коррупционеров в департаменте.

В первой строке ввода содержатся 2 целых числа: количество сотрудников в департаменте $N$ ( $2 <= N <= 1000$ ) и число из опроса $K$ ( $1 <= K <= min(N-1,10)$ ). Во второй строке ввода содержатся $N$ целых чисел $a_i$ – ответы, названные сотрудниками ( $0 <= a_i <= K+1$ ).

В единственной строке выведите два неотрицательных целых числа, не превосходящих $N$ : минимальное и максимальное возможное количество коррупционеров, не противоречащее результатам опроса. Гарантируется, что для каждого теста существует хотя бы одна подходящая рассадка.

Пример ввода 1

4 1
0 0 0 0

Пример вывода 1

0 4

Пример ввода 2

5 1
1 1 1 1 0

Пример вывода 2

2 3

Система оценки и описание подзадач

Подзадача 1 (20 баллов)

$K=1$ , остальные ограничения из условий задачи.

Подзадача 2 (30 баллов)

$2<=N<=10$ , остальные ограничения из условий задачи.

Подзадача 3 (50 баллов)

Ограничения из условий задачи

Необходимые подзадачи: 1, 2.

Баллы за каждую из подзадач начисляются только в случае, если все тесты для этой подзадачи успешно пройдены. По запросу сообщается о первой ошибке.

5. Справедливые подмассивы-1 (7-8 класс)

Ограничения: время – 200ms/400ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

У Анны и Бориса есть массив из $N$ целых чисел. Любой его подмассив от $L$ до $R$ (то есть элементы, стоящие в позициях от $L$ до $R$ включительно, $1<=L<=R<=N$ ) они делят между собой: числа, стоящие на четных позициях, достаются Анне, а на нечетных – Борису. Если сумма чисел Анны оказалась равной сумме чисел Бориса, то такой подмассив называют справедливым. Подсчитайте, сколько различных справедливых подмассивов можно выбрать из заданного массива. Подмассивы считаются различными, если отличаются их левые или правые границы.

В первой строке ввода содержится единственное целое число $N$ – размер массива ( $1<=N<=10^5$ ). Во второй строке ввода содержатся $N$ целых чисел $a_i$ – элементы массива ( $-10^9 <= a_i <= 10^9$ ).

Выведите единственное целое число – количество справедливых подмассивов.

Пример ввода 1

7
1 2 1 3 4 1 1

Пример вывода 1

Пояснение к примеру 1. Справедливыми являются следующие подмассивы: от 6 до 7 - [1 1], от 1 до 3 - [1 2 1], от 4 до 6 - [3 4 1], от 2 до 5 - [2 1 3 4], от 1 до 6 - [1 2 1 3 4 1], от 2 до 7 - [2 1 3 4 1 1].

Пример ввода 2

2
0 0

Пример вывода 2

Пояснение к примеру 2. Cправедливыми являются все подмассивы: от 1 до 1 - [0], от 2 до 2 - [0], От 1 до 2 - [0, 0].

Система оценки и описание подзадач

Подзадача 1 (30 баллов)

$N<=100$ , $-10 <= a_i <= 10$ .

Подзадача 2 (40 баллов)

$N<=1500$ , $-10 <= a_i <= 10$ .

Необходимые подзадачи: 1

Подзадача 3 (20 баллов)

$N<=10^5$ , $-10 <= a_i <= 10$ .

Необходимые подзадачи: 1, 2

Подзадача 4 (10 баллов)

Ограничения из условий задачи.

Необходимые подзадачи: 1, 2, 3

Баллы за каждую из подзадач начисляются только в случае, если все тесты для этой подзадачи успешно пройдены. По запросу сообщается о первой ошибке.

Назад

Подразделы

Другие разделы

Дата и время

Авторизация

Задачи муниципального этапа олимпиады школьников по информатике 2024

1. Пирожки (все классы)

2 или 4. Склад (все классы)

2. Алгоритм (7-8 класс)

3. Коттеджный поселок (9-11 класс)

3. Рисование снежинки (7-8 классы)

4. Справедливые подмассивы-2 (9-11 класс)

5. Круговая порука (9-11 класс)

5. Справедливые подмассивы-1 (7-8 класс)