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

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

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

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

10 2
9 9

8 9

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

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

Дробь `1/8` может быть представлена в виде конечной десятичной дроби 0,125, а дробь `1/7` – в виде бесконечной десятичной дроби 0,142857142857142857....

Напишите программу, которая определяет, представима ли дробь `1/N` в виде конечной десятичной дроби.

Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10^9`).

Вывести одно целое число – количество цифр после десятичной запятой в представлении `1/N` в форме конечной десятичной дроби или сообщение NO, если дробь `1/N` не представима в виде конечной десятичной дроби.

8

3

7

NO

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

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

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

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

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

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

Озимандии не нравится вид на Манхэттен, и он решил очистить город от существующих зданий и построить новые небоскрёбы так, чтобы "линии города" (skyline) при взгляде с юга и востока имели заданную форму.

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

Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 10^5`) – ширина вида с юга в зданиях, следующая строка содержит `N` целых положительных чисел – высоты зданий на "линии города" при взгляде с юга. Третья строка ввода содержит одно целое число `M` (`1\ ≤\ M\ ≤\ 10^5`) – ширина вида с востока в зданиях, следующая строка содержит `M` целых положительных чисел – высоты зданий на "линии города" при взгляде с востока.

Вывести одно целое число – минимальное количество зданий. Если получить заданные "линии города" невозможно, то вывести сообщение "NO".

3
1 6 4
4
6 3 1 2

5

2
1 1
2
5 5

NO

`1\ ≤\ N,\ M\ ≤\ 100`, высоты зданий от 1 до 1000

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

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

`1\ ≤\ N,\ M\ ≤\ 10^5`, высоты зданий от 1 до `10^5`

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

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

`1\ ≤\ N,\ M\ ≤\ 10^5`, высоты зданий от 1 до `10^9`.

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

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

Вор по кличке «Призрак» собирается похитить известный алмаз «Розовая пантера». Алмаз находится в углу комнаты размером `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».

10 22 2
6 16 5
4 6 5

YES

10 10 2
5 4 4
3 7 4

NO

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

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

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

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

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

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

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

"Мегамакс" проводит конкурс по поеданию попкорна на скорость. В конкурсе участвуют команды из `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`) слева направо.

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

5 3 4
5 8 3 10 7

4

3 2 1
1 5 1

6

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

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

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

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

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

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

Дана последовательность из `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`).

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

5
1
2
4
3
5

168

2
1
1

1

10
5
8
10
9
1
4
12
6
13
3

10530

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

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

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

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

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

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

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

После выполнения программы роботом количество красных, жёлтых и зелёных полей должно стать одинаковым (по 4 поля каждого цвета). Робот должен использовать наименьшее количество краски, учитывая факт, что часть полей уже имеют нужный цвет. В примере на рисунке робот может покрасить поле 5 в красный цвет, а поле 6 – в жёлтый.

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

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

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

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

Последняя команда возвращает номер текущего поля.

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

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

Поля могут иметь любой цвет из трёх.

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

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

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

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

Рассмотрим процесс создания программы в Blockly на примере покраски полей в два цвета (6 красных и 6 жёлтых).

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

После этого в категории "Переменные" появятся блоки для получения и изменения значения переменной.

Для подсчета количества красных полей необходимо пройти по всем полям и увеличивать переменную kr при обнаружении красного поля.

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

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

Результирующая программа для робота выглядит следующим образом:

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

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

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