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

print1. В магазине (9-11 класс)

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

В магазине продаются два вида печенья. Первый вид печенья упакован в коробки по `A` штук и стоит `B` центов за коробку, второй вид печенья упакован в коробки по `C` штук и стоит `D` центов за коробку. Аня собирается угостить печеньем `N` гостей и хочет приобрести столько коробок печенья одного вида, чтобы каждому гостю досталось по одному печенью. Например, для 22 гостей можно купить либо 3 коробки за 11 центов по 10 печений, либо 2 коробки за 15 центов по 12 печений. В первом случае Аня потратит 33 цента, во втором случае — 30 центов.
Напишите программу, определяющую, какой вид печенья выгоднее купить.
Первая строка ввода содержит пять целых чисел `A`, `B`, `C`, `D` и `N`, разделенных пробелами — информация о количестве печенья в коробке и стоимости для каждого вида печенья и количество гостей.
В первой строке вывести сообщение "FIRST", если выгоднее купить печенье первого вида, или сообщение "SECOND", если выгоднее купить печенье второго вида, или сообщение "ANY", если стоимость приобретения `N` или более штук печенья для обоих видов одинакова. Во второй строке вывести одно целое число — стоимость покупки.

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

10 11 12 15 22

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

SECOND
30

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

10 8 25 20 100

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

ANY
80
Описание подзадач и системы оценивания
Подзадача 1 (50 баллов)
`1\ ≤\ A,\ B,\ C,\ D,\ N\ ≤\ 1000`
В этой подзадаче 5 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (50 баллов)
Необходимые подзадачи: 1.
`1\ ≤\ A,\ B,\ C,\ D,\ N\ ≤\ 10^9`
В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.

print1. Побег робота-кладовщика (7-8 класс)

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

Для управления роботом-кладовщиком используется программа, которая может содержать следующие команды:
  • F – идти вперед на один шаг;
  • F* – идти вперед, пока движение вперед возможно;
  • R – повернуться на 180 градусов;
  • T – взять верхний ящик в стопке ящиков прямо перед роботом;
  • D – поставить ящик в стопку ящиков прямо перед роботом;
  • C – подняться или спуститься на соседнюю стопку ящиков.
Пусть `h` – высота из стопки ящиков, на которой находится робот, и `z` – высота соседней стопки ящиков, на которую смотрит робот, тогда для команд F, T, D и C должны выполняться следующие ограничения.
КомандаОграничения
F`h=z`
C`h=z-1` или `h=z+1`
T`h=z` или `h+1=z` или `h+2=z`, робот не держит ящик
D`h=z-1` или `h=z` или `h=z+1`, робот держит ящик
Робот может переносить только один ящик. Робот не может покидать комнату. Комната имеет фиксированную длину, равную длине 20 ящиков, фиксированную ширину (1 ящик) и неограниченную высоту. Выход из комнаты находится на левой стене на высоте 3 ящиков. Перед выполнение программы робот стоит в самой левой (первой) позиции и смотрит направо. Если робот не может выполнить очередную команду программы из-за ограничений, то команда пропускается. Например, программа "TFRDRTRDRF*TRF*RFRDCC" выполняет следующие действия:
Начальная позиция (вид сбоку)Конечная позиция (вид сбоку)
....................
....................
>##.....#...........
<...................
#...................
##..................
Напишите программу, которая поможет роботу добраться до выхода из комнаты. Длина программы не должна превышать 100 символов.
Описание подзадач и системы оценивания
Подзадача 1 (25 баллов)
Программа для робота должна помочь роботу в следующей ситуации.
Начальная позиция (вид сбоку)Конечная позиция (вид сбоку)
....................
....................
....................
>######.............
<...................
#...................
##..................
###.................
Подзадача 2 (75 баллов)
Ящики находятся в любой позиции комнаты, кроме первой, высоты стопок из ящиков не более 2, всего в комнате ровно 6 ящиков.
Необходимые подзадачи: 1.
В этой подзадаче 3 теста, каждый тест оценивается в 25 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки для всех подзадач (без разделения на отдельные тесты).

print2 (4). Первоклассные числа-2 (9-11 класс)

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

Если взять натуральное число и найти сумму квадратов его цифр, затем сумму квадратов цифр результата и так далее, то через несколько шагов для некоторых из чисел получится число 1. Такие числа будем называть первоклассными. Например, первоклассным будет число 19, так как `1^2+9^2=82`, `8^2+2^2=68`, `6^2+8^2=100`, `1^2+0^2+0^2=1`. А числа 2 или 5 первоклассными не являются.
Напишите программу, которая находит количество первоклассных чисел среди чисел в диапазоне от `A` до `B` включительно.
Первая строка ввода содержит два целых чисел `A`, `B`.
Вывести одно целое число – количество первоклассных чисел среди чисел в диапазоне от `A` до `B`.

Пример ввода

1 20

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

5
Описание подзадач и системы оценивания
Подзадача 1 (25 баллов)
`1\ ≤\ A\ ≤\ B\ ≤\ 10^6`, `B\ -\ A\ ≤\ 1000`
В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (25 баллов)
Необходимые подзадачи: 1.
`1\ ≤\ A\ ≤\ B\ ≤\ 10^9`, `B-\ A\ ≤\ 10^6`
В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (50 баллов)
Необходимые подзадачи: 1,2.
`1\ ≤\ A\ ≤\ B\ ≤\ 10^{18}`
В этой подзадаче 5 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.

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

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

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

39821.png

В первой строке ввода содержится одно целое число `N` (`0 ≤ N ≤ 10^9`).
Вывести два целых числа — вычисленный ответ.

Пример ввода

77

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

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

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

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

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

39838.png

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

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

5 
4 5 6 3 7

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

4

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

3
9 5 6

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

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

print2. Робот-кладовщик (9 класс)

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

Для управления роботом-кладовщиком используется программа, которая может содержать следующие команды:
  • F – идти вперед на один шаг;
  • F* – идти вперед, пока движение вперед возможно;
  • R – повернуться на 180 градусов;
  • T – взять верхний ящик в стопке ящиков прямо перед роботом;
  • D – поставить ящик в стопку ящиков прямо перед роботом;
  • C – подняться или спуститься на соседнюю стопку ящиков.
Пусть `h` – высота из стопки ящиков, на которой находится робот, и `z` – высота соседней стопки ящиков, на которую смотрит робот, тогда для команд F, T, D и C должны выполняться следующие ограничения.
КомандаОграничения
F`h=z`
C`h=z-1` или `h=z+1`
T`h=z` или `h+1=z` или `h+2=z`, робот не держит ящик
D`h=z-1` или `h=z` или `h=z+1`, робот держит ящик
Робот может переносить только один ящик. Робот не может покидать комнату. Комната имеет длину, равную длине `N` ящиков, фиксированную ширину (1 ящик) и неограниченную высоту. Перед выполнение программы робот стоит в самой левой (первой) позиции и смотрит направо. Если робот не может выполнить очередную команду программы из-за ограничений, то команда пропускается. Напишите программу, которая моделирует движение робота по заданной программе.
Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10`) – длина комнаты. Вторая строка ввода содержит `N` чисел от 0 до 1 – начальные высоты стопок ящиков. Третья строка ввода содержит программу для робота длиной от 1 до 100 символов, содержащая только символы F, R, D, T, С и возможно символ * после F.
В первой строке вывести одно целое число — позицию робота. Во второй строке вывести высоты стопок ящиков после выполнения программы.

Пример ввода

4
0 1 1 1
TFRDRTRDRFTRD

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

3
2 1 0 0
.... (до выполнения
>### программы)
#... (после выполнения
##<. программы)
Описание подзадач и системы оценивания
Подзадача 1 (50 баллов)
Программа для робота содержит только команды R, F, T и D, все команды в программе соответствуют ограничениям. В начальной позиции робота высота стопки равна 0.
В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (50 баллов)
Необходимые подзадачи: 1
Программа может содержать любые команды.
В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.

print3. Первоклассные числа-1 (7-8 класс)

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

Если взять натуральное число и найти сумму квадратов его цифр, затем сумму квадратов цифр результата и так далее, то через несколько шагов для некоторых из чисел получится число 1. Такие числа будем называть первоклассными. Например, первоклассным будет число 19, так как `1^2+9^2=82`, `8^2+2^2=68`, `6^2+8^2=100`, `1^2+0^2+0^2=1`. А числа 2 или 5 первоклассными не являются.
Напишите программу, которая определяет, является ли заданное число первоклассным.
Первая строка ввода содержит одно целое число `N`.
Вывести сообщение "YES", если число `N` является первоклассным, иначе вывести сообщение "NO".

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

19

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

YES

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

5

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

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

print3. Прогулка в лабиринте (10-11 класс)

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

Лабиринт строится следующим образом. Лабиринт L(`k`) имеет размер `2^k` и строится из 4 лабиринтов L(`k-1`). Две верхних части лабиринта L(`k`) повторяют структуру L(`k-1`), часть в левом нижнем углу — структуру L(`k-1`), повернутого по часовой стрелке, а часть в правом нижнем углу — структуру L(`k-1`), повернутого против часовой стрелки. На рисунке показаны планы лабиринтов L(1), L(2), L(3).

39833.png

Аня зашла в лабиринт, сделала несколько шагов и теперь не знает, где она находится. Напишите программу, которая определяет координаты Ани в лабиринте по размеру лабиринта и количеству сделанных ею шагов.
Первая строка ввода содержит два целых числа `N` и `M` (`M\ ≤\ N^2`) – размеры лабиринта и количество шагов. Число `N` является степенью числа 2.
Вывести два целых числа — координаты Ани в лабиринте.

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

4 10

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

3 4

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

8 19

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

2 6
Описание подзадач и системы оценивания
Подзадача 1 (50 баллов)
`2\ ≤\ N\ ≤\ 8`
В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (50 баллов)
Необходимые подзадачи: 1.
`16\ ≤\ N\ ≤\ 32768`
В этой подзадаче 25 тестов, каждый тест оценивается в 2 балла. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.

print4. Рамки (7-8 класс)

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

Имеется несколько планок разной длины, из которых нужно сделать рамки для фотографий. При изготовлении рамки планки нельзя разрезать на части или соединять несколько планок в одну длинную планку. Рамка должна быть прямоугольной, при этом длинная сторона должна быть не более чем в два раза длиннее короткой.
Напишите программу, которая определяет, какое максимальное количество рамок можно сделать из заданного набора планок.
Первая строка ввода содержит одно целое число `N` — количество планок. Следующая строка содержит `N` целых чисел — длины рамок.
Вывести одно целое число — максимальное количество рамок.

Пример ввода

10
5 5 10 5 8 8 10 7 25 25

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

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

print4. Скобки (10-11 класс)

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

Хорошей последовательностью скобок будем называть последовательность из открывающихся и закрывающихся скобок, в которой при последовательном чтении как слева направо, так и справа налево количество открывающихся скобок остается больше или равно количества закрывающихся скобок.
Напишите программу, которая определяет минимальное количество закрывающихся скобок, которое нужно удалить из последовательности скобок, чтобы она стала хорошей.
Первая строка ввода содержит одно целое число `N` — количество скобок. Вторая строка ввода содержит `N` открывающихся и закрывающихся скобок. Третья строка содержит одно целое число `Q` – количество запросов. Далее следует `Q` строк, в каждой строке содержится два целых числа `L_i`, `R_i` (`1\ ≤\ L_i\ ≤\ R_i\ ≤\ N`) – индекс начала и конца подпоследовательности, которую нужно превратить в хорошую.
Для каждого запроса вывести на отдельной строке одно целое число – минимальное количество закрывающихся скобок, которое нужно удалить из подпоследовательности скобок с `L_i` по `R_i`.

Пример ввода

11
((())))))((
3
1 11
4 9
1 6

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

4
6
3
В первом запросе хорошей является последовательность "((())((", во втором запросе – "", в третьем – "(((".
Описание подзадач и системы оценивания
Подзадача 1 (25 баллов)
`1\ ≤\ N,\ Q\ ≤\ 2000`
В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (50 баллов)
Необходимые подзадачи: 1.
`1\ ≤\ N,\ Q\ ≤\ 70000`
В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (25 баллов)
Необходимые подзадачи: 1,2.
`1\ ≤\ N,\ Q\ ≤\ 500000`
В этой подзадаче 10 тестов. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач.
loading