Каждая задача оценивается в 10 баллов. Итоговый балл выставляется как сумма баллов за 4 задачи с лучшим результатом (то есть для получения максимального балла нужно решить 4 любые задачи).
Задача 1. «Квартиры»
По проекту строительства многоэтажный жилой дом должен был содержать n подъездов и k этажей, на каждом этаже в каждом подъезде должно быть ровно p квартир.
Затем проект был изменён, при этом количество этажей уменьшилось на 3, а количество подъездов увеличилось на 2. Количество квартир на каждом этаже в каждом подъезде не изменилось. Оказалось, что общее количество квартир в доме при этом увеличилось.
Определите, на сколько увеличилось количество квартир в доме.
Ответом на эту задачу является некоторое выражение, которое может содержать целые числа, переменные n, k и p (записываемые английскими буквами), операции сложения
(обозначается «+»), вычитания (обозначается «−»), умножения (обозначается «*») и круглые скобки для изменения порядка действий. Пробелы в выражении не учитываются. Запись вида «2n» для обозначения произведения числа 2 и переменной n неверная, нужно писать «2 * n».
Пример правильного (по форме записи) выражения: n + (k − p) * 2.
Решение
Количество квартир в доме до изменения проекта было равно n * k * p, а после повышение стало равно (n + 2) * (k − 3) * p. Ответом будет разность этих значений.
Ответ: (n + 2) * (k − 3) * p − n * k * p.
Задача 2. «Танец»
Для исполнения большого танца в круг выстроилось N танцоров (N чётное).
Пронумеруем танцоров числами от 1 до N начиная от подиума по часовой стрелке.
На каждом шаге танца танцоры разбиваются на пары (пару образуют два соседних по кругу танцора), и танцоры в паре меняются местам, причём на первом и всех последующих нечётных шагах танцор, стоящий в начале круга, образует пару с танцором, стоящим рядом с ним по часовой стрелке. Также пару образуют два танцора, следующие за ними по часовой стрелке, и т. д. На втором шаге и всех шагах с чётными номерами танцор, стоящий в начале круга, образует пару с танцором, стоящим рядом с ним против часовой стрелки. Два танцора, следующие за ними против часовой стрелки, также образуют пару и т. д.
На рисунке (Рисунок 2.1) изображена начальная расстановка для N = 6 танцоров и два следующих шага танца. Расположение подиума отмечено точкой.
Пусть по кругу стоят N = 8 танцоров. Ответьте на вопросы.
- (1 балл) Через сколько шагов после начала танца танцоры 1 и 8 снова окажутся рядом? Напишите число 0, если такого не случится никогда.
- (1 балл) Через сколько шагов после начала танца соседями танцора 1 будут танцоры 6 и 8? Напишите число 0, если такого не случится никогда.
- (1 балл) Через сколько шагов после начала танца танцоры 3 и 7 окажутся рядом? Напишите число 0, если такого не случится никогда.
- (1 балл) Танцор с каким номером окажется у подиума через 2017 шагов?
Пусть по кругу стоят N = 200 танцоров. Ответьте на вопросы.
- (2 балла) Танцор с каким номером будет у подиума после 218-го шага?
- (2 балла) Через сколько шагов после начала танца у подиума окажется танцор с номером 179? Напишите число 0, если такого не случится никогда.
- (2 балла) Через сколько шагов после начала танца соседями танцора номер 1 в пятый раз будут танцоры номер 56 и 58? Напишите число 0, если такого не случится никогда.
Ответом на это задание служат семь целых чисел, записанных в отдельных строках, которые являются ответами на данные вопросы в таком же порядке. Необходимо записать в ответе ровно семь чисел в семи строках. Если вы не можете дать ответ на какой-либо вопрос, напишите вместо ответа любое число. Если ответом на вопрос может быть несколько чисел, нужно выбрать наименьшее из них.
Решение
Для того, чтобы ответить на первые четыре вопроса, выпишем перемещения танцоров для первых шагов.
Шаг танца | Порядок танцоров | |||||||
Начало | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 1 | 2 | 1 | 4 | 3 | 6 | 5 | 8 | 7 |
| 2 | 7 | 4 | 1 | 6 | 3 | 8 | 5 | 2 |
| 3 | 4 | 7 | 6 | 1 | 8 | 3 | 2 | 5 |
| 4 | 5 | 6 | 7 | 8 | 1 | 2 | 3 | 4 |
| 5 | 6 | 5 | 8 | 7 | 2 | 1 | 4 | 3 |
| 6 | 3 | 8 | 5 | 2 | 7 | 4 | 1 | 6 |
| 7 | 8 | 3 | 2 | 5 | 4 | 7 | 6 | 1 |
| 8 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Из таблицы видно, что ответ на вопрос 1 — 3, на вопрос 2 — 3, на вопрос 3 — 0 (такого не случится никогда, т. к. через 8 шагов все танцоры вернутся на исходные места и далее процесс повторяется). На вопрос 4 ответом будет число 2, так как число 2016 делится на 8, значит, через 2016 шагов танцоры вернутся на исходные места и на 2017 шагу у подиума будет танцор номер 2.
Для того, чтобы ответить на вопросы номер 5-7 нужно понять принцип движения танцоров. Можно заметить, что танцоры с нечётными номерами (1, 3, 5, 7) на каждом шаге движутся вправо, а танцоры с чётными номерами (2, 4, 6, 8) всегда движутся влево.
Найдем ответ на вопрос 5. Поскольку через 200 шагов танцоры возвращаются в исходную позицию, то через 218 шагов ситуация будет такой же, как и через 18 шагов.
Видим, что после чётного шага у подиума оказывается танцор с нечётным номером, начиная с танцора с наибольшим нечётным номером, и далее по убыванию номера. То есть после шага 2 у подиума будет танцор с номером 199, после 4 шага — с номером 197, после шага 6 — с номером 195 и т. д. После шага 18 у подиума будет танцор с номером 183.
Для ответа на вопрос 6 заметим, что танцор с номером 179 движется вправо. Через один шаг танца он будет на месте 180, через два шага — на месте 181 и т. д. Он окажется на 200-м месте через 21 шаг, и на шаге 22 он встанет у подиума.
Для ответа на вопрос 7 сначала определим, когда соседями танцора 1 впервые станут танцоры 56 и 58. После первого шага соседями 1 будут 2 и 4, после второго шага — 4 и 6, после третьего шага — 6 и 8, то есть на каждом шаге номера танцоров увеличиваются на 2.
Поэтому впервые соседями 1 станут 56 и 58 через 28 шагов. Далее нужно заметить, что взаимное расположение танцоров повторяется не через N шагов, а через N / 2 шагов, поэтому пятая встреча произойдет через 28 + 4 × 100 = 428 шагов.
Ответ:
3 3 0 2 183 22 428
Задача 3. «Крестраж»
Волан де Морт спрятал один из крестражей в золотой рыбке. Эта рыбка живёт в пяти озёрах, соединённых между собой рекой. Озёра пронумерованы числами от 1 до 5, из озера 1 можно попасть в озеро 2, из озера 2 можно попасть в озёра 1 и 3 и т. д.
Гарри Поттер должен добыть эту золотую рыбку. Для этого у него есть волшебные червячки. Рыбка обязательно клюнет на наживку, если забросить её в озеро с рыбкой.
Забрасывать наживку можно только в озеро. За один бросок можно бросить червячка только в одно озеро.
Каждый волшебный червячок может быть использован только один раз. Если снасть с червячком забросили в озеро, а рыбки там не оказалось, то волшебная сила наживки исчезает и для следующей попытки требуется новый волшебный червячок.
При этом рыбка чувствует Гарри Поттера и после каждого заброшенного червячка обязательно переплывает в одно из озёр, соседних с тем, в котором она находится. В самом начала рыбка может находиться в любом из пяти озёр.
Придумайте последовательность действий Гарри Поттера, при исполнении которой он обязательно поймает рыбку независимо от её первоначального местонахождения и дальнейших перемещений.
В ответе нужно записать последовательность чисел через пробел – номера озёр, в которые Гарри Поттер будет закидывать наживку, в том порядке, в котором он будет это делать. Чем меньше червячков потратит Гарри Поттер, тем больше баллов вы получите (при условии, что при исполнении вашего решения рыбка будет обязательно поймана).
Может показаться, что задача не имеет решения, но это не так. Рассмотрим случай трёх озёр. Гарри Поттер может закинуть наживку в озеро 2. Если он не поймает рыбку после этого, значит, она могла находиться в озёрах 1 или 3. После этого рыбка переплывает в соседнее озеро, и в каждом из этих случаев она попадёт в озеро 2. Поэтому вторую наживку Гарри Поттер снова закинет в озеро 2 и тогда обязательно поймает рыбку. Ответ для трёх озёр: «2 2».
Решение
Нетрудно заметить, что сначала Гарри Поттер должен бросить наживку в озеро 2 или 4, в противном случае после своего перемещения рыбка сможет оказаться в любом из пяти озёр и тем самым первый бросок будет бессмысленным. Пусть это будет озеро 2. Тогда после броска Гарри Поттера рыбка может находиться в следующих озёрах (звёздочкой помечены возможные расположения рыбки):
| 1 | 2 | 3 | 4 | 5 |
| * | . | * | * | * |
А после перемещения рыбки.
| 1 | 2 | 3 | 4 | 5 |
| . | * | * | * | * |
Аналогично, второй бросок Гарри Поттер может сделать только в озеро 3. Второй бросок Гарри Поттера:
| 1 | 2 | 3 | 4 | 5 |
| . | * | . | * | * |
После перемещения рыбки:
| 1 | 2 | 3 | 4 | 5 |
| * | . | * | * | * |
Теперь единственный бросок, который не приводит к ранее возникавшим ситуациям, это в 4.
| 1 | 2 | 3 | 4 | 5 |
| * | . | * | . | * |
После перемещения рыбки:
| 1 | 2 | 3 | 4 | 5 |
| . | * | . | * | . |
Дальнейшая последовательность действий проста. Гарри Поттер бросает наживку в озеро 2:
| 1 | 2 | 3 | 4 | 5 |
| . | . | . | * | . |
После перемещения рыбки:
| 1 | 2 | 3 | 4 | 5 |
| . | . | * | . | * |
Затем в озеро 3:
| 1 | 2 | 3 | 4 | 5 |
| . | . | . | . | * |
После перемещения рыбки:
| 1 | 2 | 3 | 4 | 5 |
| . | . | . | * | . |
И последний бросок делает в озеро 4. Всего потрачено 6 червячков. Можно менять последовательность действий, поэтому есть четыре наилучших решения: «2 3 4 2 3 4», «2 3 4 4 3 2», «4 3 2 2 3 4», «4 3 2 4 3 2».
Задача 4. «Робот»
В игре «Зажги свет» игрок управляет роботом, перемещающимся по клетчатому полю.
Робот находится в одной из клеток поля и обращён лицом в сторону одной из четырёх соседних клеток. Робот может перемещаться в соседнюю клетку в направлении своего лица (F), поворачиваться в своей клетке на 90° направо (R) или налево (L), а также включать свет в клетке поля, в которой он находится (T). В скобках указаны обозначения соответствующих команд.
Приведём примеры исполнения команд «L», «R», «F».
Дано следующее поле, на котором закрашенные клетки являются непроходимыми (попытка движения в непроходимые клетки приводит к разрушению робота), а клетки, в которых нужно зажечь свет, отмечены звёздочками. Начальное положение робота помечено знаком «⬇», и робот смотрит вниз (в направлении стрелки).
Попытка зажечь свет в клетке, не помеченной звёздочкой, приводит к аварийному завершению программы, но в клетке, в которой уже включён свет, разрешается его включать повторно.
Алгоритм действий робота представляет собой строку из нескольких команд «F», «R», «L», «T». Кроме того, несколько команд могут быть объединены в подпрограмму (P).
Подпрограмма – это последовательность команд, которую можно вызывать из основного алгоритма, указав только один символ «P».
Ответ должен быть записан в виде двух строк. Первая строка начинается с двух символов «P:» и содержит описание подпрограммы. После двоеточия в этой строке могут идти только символы «F», «R», «L», «T». Вторая строка начинается с двух символов «M:» и содержит описание основной программы. После двоеточия во второй строке могут идти все команды робота и команда вызова подпрограммы «P» – встретив эту команду, робот исполняет последовательность команд, записанных в первой строке после двоеточия. Сама по себе подпрограмма исполняется только в том случае, если в основном алгоритме встречается символ «P». Если в основном алгоритме не будет символов «P», команды подпрограммы не выполнятся ни разу. Пробелы, запятые, иные символы в записи алгоритма не используются.
Рассмотрим пример. Пусть дан алгоритм:
- P:FFT
- M:TPRPRP
В этом примере подпрограмма P перемещает робота вперёд на две клетки и включает свет в клетке, где остановился робот. В основном алгоритме робот включает свет в клетке и три раза последовательно вызывает подпрограмму, поворачивая между вызовами направо.
В результате робот включит свет в четырёх углах квадрата со стороной 3 клетки.
Вам необходимо составить алгоритм, содержащий как можно меньше символов в своей записи (а не в пути робота), учитывая описание подпрограммы и основной части алгоритма. Ответ должен быть записан в формате, приведённом выше. Если вы не хотите использовать подпрограмму, первая строка вашего ответа всё равно должна содержать символы «P:». Чем меньше символов будет использовано в вашем ответе, тем больше баллов вы получите (при условии правильного решения задачи).
Решение
В этой задаче нужно заметить, что начальное расположение робота и помеченных клеток связаны между собой движением «удлинённого коня» – три клетки вперёд и одна в сторону. Оформим в виде подпрограммы алгоритм такого перемещения, со включением света в конце.
- P:FFFRFT
Теперь вызовем подпрограмму два раза.
После первого вызова подпрограммы:
После второго вызова подпрограммы:
Теперь повернём направо и вызовем подпрограмму ещё раз:
И в четвёртый раз вызовем подпрограмму:
Подпрограмма завершается командой включение света, поскольку завершение подпрограммы происходит в клетках, отмеченных звёздочками, то во всех этих клетках свет будет включён. В одной клетке свет будет включён дважды, но это разрешено условиями.
Это самое короткое решение, оно содержит 11 команд суммарно в подпрограмме и в основном алгоритме.
Ответ:
- P:FFFRFT
- M:PPRPP
Архив файлов к заданиям 7-8 (информатика, муниципальный этап, 2016-2017)
Задачи 5–7 совпадают с задачами 1–3 для 9–11 классов, соответственно с их условиями и решениями можно ознакомиться на странице заданий по информатике для 9-11 классов, муниципального этапа 2016 года