Всероссийская олимпиада школьников по информатике, 2020–2021 уч. г.

Всероссийская олимпиада школьников по информатике, 2020–2021 уч. г.

Школьный этап. Задания для 9-11 классов

Задача 1.

Вам даны пять чисел:

Для каждого из этих чисел найдите минимальное целое число, которое было бы больше данного, и запись этого числа была бы палиндромом, то есть читалась бы одинаково как слева направо, так и справа налево. Например, палиндромами являются такие числа, как 121, 9009, 734437.

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

Задача 2.

При проведении ремонта в квартире дизайнер предложил выложить стену узором из квадратных плиток, повернув их на 45°. Длина диагонали квадрата равна 2 дм.

Стена, которую необходимо покрыть плиткой, имеет размеры n × m дм, при этом числа n и m – целые чётные. Для покрытия такой стены необходимо какое-то количество целых квадратных плиток, а также несколько треугольных обрезков плитки. На рисунке на следующей странице приведён пример покрытия плиткой стены размером 4 × 6 дм, при этом было использовано 8 целых квадратных плиток.

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

Ответом на эту задачу является некоторое выражение, которое может содержать целые числа, переменные n и m (записываемые английскими буквами), операции сложения (обозначаются «+»), вычитания (обозначаются «−»), умножения (обозначаются «*»), деления (обозначаются «/») и круглые скобки для изменения порядка действий. Запись вида «2n» для обозначения произведения числа 2 и переменной n неверная, нужно писать «2 * n».

Ваше выражение должно давать правильный ответ для любых чётных значений n и m, например, для n = 4 и m = 6 значение выражения должно быть равно 8.

Пример правильной формы записи ответа. m / 2 + (m * n − m) * 2

Задание 3

Новый квест, в котором участники должны выбраться с территории проведения, представляет собой прямоугольник из 16 комнат в виде квадрата 4 × 4. Каждая комната имеет четыре двери, ведущие в соседние комнаты, из комнат на краю прямоугольника двери ведут наружу, через эти двери можно покинуть территорию проведения квеста.

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

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

Разработчки квеста попросили Вас составить такой план отпирания дверей, при котором ровно 7 человек из 16 смогут выбраться наружу с территории квеста. При этом Вам необходимо минимизировать количество дверей, которые будут открыты из крайних комнат наружу (тех дверей, через которые участники будут покидать территорию квеста).

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

U: дверь в верхнюю по данному плану комнату.

D: дверь в нижнюю комнату.

L: дверь в левую комнату.

R: дверь в правую комнату.

Например, рассмотрим следующий план квеста, в котором 8 комнат:

RDRR

ULRR

Этот план соответствует следующему рисунку. Стрелками обозначены открытые двери, точками помечены комнаты, обитатели которых выйдут из квеста.

В этом примере наружу выходят 4 человека из 8.

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

Задание 4

Робот стоит на поле 4×4 в левой верхней клетке. В остальных клетках поля записаны буквы A, Б, В, Г (см. рисунок слева). Робот умеет шагать в соседнюю клетку только по вертикали или по горизонтали. Покидая клетку, робот стирает записанную в ней букву.

У робота есть память из четырёх пронумерованных по порядку ячеек (см. рисунок справа). Каждая ячейка содержит одну из букв А–Г. Буквы в ячейках не повторяются.

Очередной шаг робот выполняет по следующим правилам:

• Робот не шагает в клетку, буква в которой была стёрта.

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

• Если робот нашёл такую ячейку, что буква в этой ячейке записана в двух и более соседних с роботом клетках, то он ломается.

• Если робот не нашёл ни одной подходящей ячейки, то он ломается.

Останавливается робот, когда достигает правой нижней клетки.

Заполните ячейки памяти робота так, чтобы робот пришёл в правый нижний угол поля и постройте маршрут робота.

Робот	Б	А	В	Номер ячейки	Буква в ячейке
А	Г	А	Г
Б	В	В	В
Г	Г	В	Г