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

printАлгоритм (7-9 класс)

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

Реализуйте на одном из языков программирования алгоритм, представленный на схеме.

42132.png

В первой строке ввода содержатся два целых числа `N` и `K` (`1\ ≤\ N,\ K\ ≤\ 100`). Во второй строке – `K` целых чисел в диапазоне от 0 до `N`.
Вывести два целых числа — вычисленный ответ.

Пример ввода

10 2
9 9

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

8 9
Система оценки
В этой задаче 10 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.

printДесятичная дробь

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

Дробь `1/8` может быть представлена в виде конечной десятичной дроби 0,125, а дробь `1/7` – в виде бесконечной десятичной дроби 0,142857142857142857....
Напишите программу, которая определяет, представима ли дробь `1/N` в виде конечной десятичной дроби.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10^9`).
Вывести одно целое число – количество цифр после десятичной запятой в представлении `1/N` в форме конечной десятичной дроби или сообщение NO, если дробь `1/N` не представима в виде конечной десятичной дроби.

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

8

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

3

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

7

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

NO
Система оценки и описание подзадач
Подзадача 1 (20 баллов)
`1\ ≤\ N\ ≤\ 10`
В этой подзадаче 8 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Подзадача 2 (50 баллов)
Необходимые подзадачи: 1.
`10\ <\ N\ ≤\ 1000`
В этой подзадаче 5 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Подзадача 3 (30 баллов)
Необходимые подзадачи: 1,2.
`1000\ <\ N\ ≤\ 10^9`
В этой подзадаче 6 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат окончательной проверки на каждом тесте.

printЛиния города (9-11 класс)

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

Озимандии не нравится вид на Манхэттен, и он решил очистить город от существующих зданий и построить новые небоскрёбы так, чтобы "линии города" (skyline) при взгляде с юга и востока имели заданную форму.
42228.png
Напишите программу, которая определяет минимальное количество зданий для получения заданных "линий города" с юга и востока.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10^5`) – ширина вида с юга в зданиях, следующая строка содержит `N` целых положительных чисел – высоты зданий на "линии города" при взгляде с юга. Третья строка ввода содержит одно целое число `M` (`1\ ≤\ M\ ≤\ 10^5`) – ширина вида с востока в зданиях, следующая строка содержит `M` целых положительных чисел – высоты зданий на "линии города" при взгляде с востока.
Вывести одно целое число – минимальное количество зданий. Если получить заданные "линии города" невозможно, то вывести сообщение "NO".

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

3
1 6 4
4
6 3 1 2

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

5

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

2
1 1
2
5 5

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

NO
Пояснение к примеру 1: нужно построить здания в местах, показанных на рисунке

64
3
1
2

Система оценки и описание подзадач
Подзадача 1 (40 баллов)
`1\ ≤\ N,\ M\ ≤\ 100`, высоты зданий от 1 до 1000
В этой подзадаче 8 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Подзадача 2 (40 баллов)
Необходимые подзадачи: 1.
`1\ ≤\ N,\ M\ ≤\ 10^5`, высоты зданий от 1 до `10^5`
В этой подзадаче 5 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Подзадача 3 (20 баллов)
Необходимые подзадачи: 1,2.
`1\ ≤\ N,\ M\ ≤\ 10^5`, высоты зданий от 1 до `10^9`.
В этой подзадаче 4 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат окончательной проверки на каждом тесте.

printМиссия невозможна (10-11 класс)

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

Вор по кличке «Призрак» собирается похитить известный алмаз «Розовая пантера». Алмаз находится в углу комнаты размером `M\ times\ N` метров в точке с координатами `(M,N)`. Вход в комнату находится в другом углу комнаты в точке с координатами `(0,0)`. Инспектор Клузо установил в комнате `K` сенсорных датчика, `i`-й датчик находится в точке с координами `(X_i,\ Y_i)` может засечь движение на расстоянии не более `D_i` метров.
Напишите программу, которая определяет, сможет ли «Призрак» похитить алмаз.
Первая строка ввода содержит три целых числа – размеры комнаты `M` и `N` (`10\ ≤\ M,\ N\ ≤\ 10^4`) и количество сенсоров `K` (`1\ ≤\ K\ ≤\ 1000`). Следующие `K` строк содержат по три целых числа – координаты сенсора `X_i`, `Y_i` (`0\ <\ X_i\ <\ M`, `0\ <\ Y_i\ <\ N`) и его чувствительность `D_i` (`1\ ≤\ D_i\ ≤\ 10^4`).
Вывести сообщение «YES», если алмаз можно похитить, обойдя все сенсоры, иначе вывести сообщение «NO».

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

10 22 2
6 16 5
4 6 5

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

YES

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

10 10 2
5 4 4
3 7 4

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

NO
Описание подзадач и системы оценивания
Подзадача 1 (20 баллов)
`K\ =\ 1`
В этой подзадаче 8 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Программа должна проходить тесты из условия задачи, несмотря на то, что они не соответствуют ограничениям на подзадачу.
Подзадача 2 (50 баллов)
Необходимые подзадачи: 1.
`1\ <\ K\ ≤\ 50`
В этой подзадаче 16 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Подзадача 3 (30 баллов)
Необходимые подзадачи: 1,2.
`50\ <\ K\ ≤\ 1000`
В этой подзадаче 16 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат окончательной проверки для всех подзадач (без разделения на отдельные тесты).

printПопкорн (9-11 класс)

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

"Мегамакс" проводит конкурс по поеданию попкорна на скорость. В конкурсе участвуют команды из `K` человек. Для конкурса на столе выстраивается в линию `N` упаковок с попкорном, и каждый член команды берет несколько упаковок подряд из линии, начиная слева. Можно брать любое количество упаковок, в том числе ни одной, если предыдущий член команды забрал последнюю. Последний член команды забирает все оставшиеся упаковки. Нельзя меняться упаковками или нескольким членам команды есть из одной упаковки. После распределения попкорна дается сигнал к старту, и все участники начинают есть свой попкорн. Время завершения определяется по съевшему последний кусочек участнику и округляется вверх до целого числа секунд.
Количество попкорна в упаковках может быть разным, поэтому важно распределить упаковки среди участников команды так, чтобы время поедания было минимальным. Известно, что человек может съесть ровно `S` кусочков попкорна в секунду.
Напишите программу, которая определяет минимальное время для поедания попкорна.
Первая строка ввода содержит три целых числа – количество упаковок попкорна `N` (`1\ ≤\ N\ ≤\ 10^5`), количество членов команды `K` (`1\ ≤\ K\ ≤\ 10^5`) и скорость поедания попкорна `S` (`1\ ≤\ S\ ≤\ 50`) Следующая строка содержит `N` целых чисел – количество попкорна в упаковках `P_i` (`1\ ≤\ P_i\ ≤\ 10^4`) слева направо.
Вывести одно целое число – минимальное время на поедание попкорна по правилам конкурса.

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

5 3 4
5 8 3 10 7

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

4

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

3 2 1
1 5 1

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

6
Система оценки и описание подзадач
Подзадача 1 (30 баллов)
`1\ ≤\ N\ ≤\ 20`
В этой подзадаче 6 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (30 баллов)
Необходимые подзадачи: 1.
`20\ <\ N\ ≤\ 1000`
В этой подзадаче 6 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (40 баллов)
Необходимые подзадачи: 1,2.
`1000\ <\ N\ ≤\ 10^5`
В этой подзадаче 8 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.

printРазбиение последовательности (7-8 класс)

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

Дана последовательность из `N` целых положительных чисел `A_1,\ A_2,\ …,\ A_N`. Найдите способ разбиения последовательности на две части так, чтобы произведение суммы квадратов элементов первой части последовательности на сумму элементов второй части последовательности было максимальным, то есть нужно найти максимум значения выражения
`(A_1^2\ +\ …\ +\ A_k^2)*(A_{k+1}\ +\ …\ +\ A_N)`.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10^6`). Далее следует `N` строк, содержащих по одному целому числу – элементы последовательности `A_i` (`1\ ≤\ A_i\ ≤\ 100`).
Вывести одно целое число – максимум указанного выражения.

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

5
1
2
4
3
5

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

168

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

2
1
1

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

1

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

10
5
8
10
9
1
4
12
6
13
3

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

10530
Система оценки и описание подзадач
Подзадача 1 (40 баллов)
`1\ ≤\ N\ ≤\ 100`
В этой подзадаче 10 тестов, каждый тест оценивается в 4 балла. Баллы за каждый тест начисляются независимо.
Подзадача 2 (40 баллов)
Необходимые подзадачи: 1.
`100\ <\ N\ ≤\ 10^5`
В этой подзадаче 8 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (20 баллов)
Необходимые подзадачи: 1,2.
`10^5\ <\ N\ ≤\ 10^6`
В этой подзадаче 4 теста, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.

printРобот-маляр (7-8 класс)

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

Напишите программу для робота, который движется по области из 12 разноцветных полей и может их перекрашивать в различные цвета. Первоначально робот всегда находится на поле с номером 1.
42102.png
После выполнения программы роботом количество красных, жёлтых и зелёных полей должно стать одинаковым (по 4 поля каждого цвета). Робот должен использовать наименьшее количество краски, учитывая факт, что часть полей уже имеют нужный цвет. В примере на рисунке робот может покрасить поле 5 в красный цвет, а поле 6 – в жёлтый.
Для управления роботом могут использоваться следующие команды:
42101.png
Команды движения позволяют перейти роботу на соседнее поле влево или вправо. Если выполнение команды движения невозможно, то она игнорируется.
Следующая группа команд позволяют перекрасить поле, на котором находится робот, в указанный цвет. Робот может красить поле несколько раз, в том числе текущим цветом этого поля.
Следующая группа команд, которую можно использовать в логических блоках, позволяет проверить цвет текущего поля.
Последняя команда возвращает номер текущего поля.
Система оценки и описание подзадач
Подзадача 1 (30 баллов)
Программа должна помочь роботу, когда все поля имеют одинаковый цвет (красный, жёлтый или зелёный).
В этой подзадаче 3 теста, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (70 баллов)
Поля могут иметь любой цвет из трёх.
Необходимые подзадачи: 1.
В этой подзадаче 7 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.

Для написания программы для робота используется специальная версия среды Blockly. Вы можете использовать полную среду Blockly при решении других задач этого соревнования, выбрав пункт Blockly в информационном меню задачи.
Рассмотрим процесс создания программы в Blockly на примере покраски полей в два цвета (6 красных и 6 жёлтых).
Сначала нам потребуется переменная kr, в которой будем хранить количество полей красного цвета. Для создания переменной в категории "Переменные" нужно щелкнуть по кнопке "Создать переменную" и ввести её название.
42106.png
После этого в категории "Переменные" появятся блоки для получения и изменения значения переменной.
Для подсчета количества красных полей необходимо пройти по всем полям и увеличивать переменную kr при обнаружении красного поля.
42105.png
При обратном движении нужно перекрашивать поля, если количество красных полей отличается от 4. Для этого действия потребуется изменить условный блок, нажав на символ шестерёнки в левом верхнем углу блока.
42104.png
После завершения настройки блока нужно повторно нажать на символ шестерёнки.
Результирующая программа для робота выглядит следующим образом:
42103.png
Для проверки работы используйте кнопки:
42100.png
Первая кнопка позволяет отправить ваше решение для проверки в проверяющую систему соревнований, вторая кнопка выполняет запуск программу локально, третья – пошаговое выполнение или временная остановка программы, четвертая – завершение выполнения программы, после которой программа будет выполняться сначала.
Щелкая мышкой по полям рабочей области, можно задать начальную раскраску полей для тестирования.
loading