Официальные задания и ответы школьного этапа 2023-2024 всероссийской олимпиады школьников Сириус по Информатике 7-8 класс 26.10.2023
Задания и ответы ВсОШ Сириус по Информатике 2023-2024 (26 октября 2023)
Приобрести задания и ответы (все варианты)
Задание 1: Знакомства
Лиза пригласила на свой день рождения n гостей. Лиза очень общительная, поэтому гостей намного больше трёх. К сожалению, до этого праздника гости не знали друг друга, поэтому Лиза решила первым делом их всех познакомить. Сначала Лиза предложила гостям встать в хоровод и познакомиться с соседями по хороводу. Но этого оказалось мало. Лиза хотела, чтобы каждый гость познакомился с каждым другим. Для этого она каждую минуту зовёт к себе пару каких‑нибудь незнакомых между собой гостей и знакомит их. Какое количество минут потратит Лиза, чтобы осуществить задуманное —— чтобы каждый гость оказался знакомым с каждым другим?
Например, к Лизе пришли 4 гостя. Пусть они встали в хоровод в порядке 2,3,1,4. Тогда второй с третьим, третий с первым, первый с четвёртым и четвёртый со вторым познакомятся в хороводе. Лизе останется позвать к себе первого гостя со вторым и третьего гостя с четвёртым. То есть ей понадобится организовать 2 встречи, на которые требуется 2 минуты.
Запишите формулу для вычисления количества минут, необходимых Лизе, чтобы познакомить между собой всех гостей. Формулой является некоторое выражение, которое может содержать целые числа, переменную n, операции сложения (обозначается «+»), вычитания (обозначается «−»), умножения (обозначается «∗»), деления (обозначается «/») и круглые скобки для изменения порядка действий. Запись вида «2n» для обозначения произведения числа 2 и переменной n неверна, нужно писать «2∗n».
Наличие пробелов внутри строки‑выражения неважно.
Пример правильного (по форме записи) выражения: 71+(n/2−6)∗n.
Но это неправильная формула, потому что, как показано выше, при подстановке в формулу n=4 должно получаться 2.
Задание 2: Легендарные тренировки
Легендарная футбольная группа занимается по легендарной системе тренировок.
Для очередной тренировки игроки делятся на 2 команды и проводят игру между командами, при этом считается, что каждый игрок первой команды сыграл против каждого игрока второй команды и наоборот. Количество игроков в командах может быть различным, но каждый игрок должен попасть в одну из команд.
На следующей тренировке игроки делятся на команды уже как‑то по‑другому.
Тренер считает, что очень важно, чтобы каждый игрок хотя бы раз сыграл против каждого другого. Помогите тренеру добиться этого за минимальное количество тренировок.
Например, если бы у тренера было 3 игрока, то ему было бы достаточно провести 2 тренировки. В первой тренировке нужно включить в первую команду первого и второго игроков, а во вторую —— третьего игрока. А во второй тренировке первую команду составить только из второго игрока, а вторую —— из первого и третьего игрока. Тогда первый игрок сыграет против второго во второй тренировке, первый против третьего —— в первой тренировке, и второй против третьего —— в обеих тренировках. Получается, что каждый игрок сыграет против каждого другого хотя бы один раз.
У нашего тренера 15 игроков в группе. Составьте для него расписание тренировок.
В качестве ответа выведите несколько строк. Каждая строка должна описывать одну тренировку. Для этого напишите номера игроков первой команды на тренировке в строку через пробел.
Например, для группы из 3 игроков ответ может выглядеть так:
12 2
Этот вариант распределения игроков по командам описан выше, есть и другие правильные ответы для группы из 3 игроков.
Если в результате составленных вами тренировок каждый игрок сыграет с каждым, то ваше решение получит не меньше 40 баллов. Чем меньше тренировок вам понадобится, тем больше баллов вы получите. За минимальное количество тренировок, при котором каждый игрок сыграет с каждым другим, вы получите 100 баллов.
Задание 3: Рыцари и лжецы
В городе M живут только рыцари и лжецы. Рыцари всегда говорят правду, а лжецы всегда врут. Каждый год у них проходит фестиваль. На фестивале есть квадратное поле, в каждую клетку которого встал либо рыцарь, либо лжец. Все они одновременно сказали, что во всех соседних по стороне клетках стоят лжецы. Это значит, что рядом с каждым рыцарем стоят только лжецы, а с каждым лжецом должен соседствовать хотя бы 1 рыцарь.
Расставьте рыцарей и лжецов на поле 5×5, выполнив условия задачи и используя как можно меньше рыцарей.
Решения, при которых рыцари и лжецы окажутся расставлены корректно, будут оцениваться хотя бы в 10 баллов. Чем меньше рыцарей, тем больше баллов вы получите.
Ответ представьте в виде заполненной нулями и единицами таблицы размера 5×5, где 1 обозначает, что на этой клетке стоит рыцарь, а 0 —— что на этой клетке стоит лжец.
Задание 4: Игра
Игра
Петя нашёл консоль с электронной игрой. Консоль состоит из экрана, на котором изображено игровое поле, и трёх кнопок:
< (налево),
# (прямо),
> (направо).
Под центральным столбцом игрового поля находится птичка. Пете нужно управлять движением птички по игровому полю.
При каждом нажатии любой кнопки птичка передвигается на одну строку выше.
При этом если нажата кнопка <, то птичка смещается на один столбец влево, если нажата кнопка >, то птичка смещается на один столбец вправо, а если нажата кнопка #, то птичка никуда не смещается, а просто поднимается выше в том же столбце.
Если в момент нажатия на кнопку << птичка находилась в крайнем левом столбце, или в момент нажатия на кнопку >> птичка находилась в крайнем правом столбце, то ей некуда сдвигаться, и она просто поднимается вверх.
Некоторые клетки игрового поля запрещены для посещения птичкой, они выделены тёмным цветом. Если в результате своего хода птичка попадает на такую клетку, то она погибает, и игра заканчивается.
Некоторые клетки игрового поля содержат бонусные монеты, они обозначены числами. Если в результате своего хода птичка попадает на такую клетку, то она получает то количество бонусных монет, которое написано на этой клетке.
Задача игрока —— собрать максимальную сумму бонусных монет.
Программой для игры является строка, состоящая из символов <, #, >, эти символы задают последовательность нажатия кнопок.
Запишите одну строку из 10 символов <, #, > —— программу, в результате выполнения которой птичка наберёт наибольшую сумму бонусных монет. Примером правильного оформления ответа является строка:
#><###><#>
Эта строка‑программа задаёт такой маршрут движения птички:
При этом птичка соберёт суммарно 4 бонусные монеты. Конечно, можно составить программу, чтобы набрать гораздо больше монет, поэтому предложенное решение является неправильным.
Система оценки
Чем больше бонусных монет наберёт птичка, двигаясь согласно предложенной вами программе, тем больше баллов вы получите.
Программы, в результате выполнения которых птичка соберёт менее 10 бонусных монет, будут оцениваться в 0 баллов.
Задание 5: Лёша‑путешественник
Ограничение по времени: 11 секунда
Ограничение по памяти: 256 мегабайт
Алексей очень спешил в поездку и, забежав в поезд, не успел посмотреть номер вагона, зато успел посчитать, что перед ним находится не менее A вагонов, а за ним —— не более B вагонов. Всего в составе N вагонов. Выведите количество вариантов номера вагона, в котором может оказаться Алексей.
Формат входных данных
В первых трёх строках вводится 3 целых числа N, A, B (1≤N≤10^9,0<A,B<N).
Формат выходных данных
Выведите одно целое число —— количество вариантов номера вагона, в котором может оказаться Алексей. Гарантируется, что ответ равен хотя бы 1.
Система оценки
Решения, правильно работающие при N≤10^5, будут оцениваться в 40 баллов.
Замечание
В первом тесте Лёша может находиться только в вагонах с номерами 6, 7, 8.
Ответ на задание
Задание 6: Ход слона
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Миша учится играть в шахматы. Самая любимая фигура Миши —— это слон, потому что слон может атаковать все клетки, которые находятся с ним на одной диагонали. Миша очень любознательный мальчик, поэтому он задумался: сколько клеток будет атаковать слон, если поставить его на клетку с номером строки R и номером столбца C на шахматной доске размером N×N?
Открыть изображение в новой вкладке
Формат входных данных
Первая строка содержит целое число N (3≤N≤109) —— размер шахматной доски.
Вторая строка содержит целое число R (1≤R≤N) —— номер строки, в которой расположен слон.
Третья строка содержит целое число C (1≤C≤N) —— номер столбца, в котором расположен слон.
Строки и столбцы нумеруются с единицы, начиная с левого нижнего угла.
Формат выходных данных
Выведите одно целое число —— количество клеток, которые находятся под атакой слона.
Система оценки
Решения, правильно работающие при R=C, будут оцениваться в 16 баллов.
Решения, правильно работающие при N≤100, будут оцениваться в 22 балла.
Замечание
Первый пример рассмотрен на рисунке.
Во втором примере слон находится в уголке доски, поэтому может атаковать клетки только одной диагонали доски.
Ответ на задание
Задание 7: Озеленение
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Администрация города решила разбить парк на пустыре площадью N×M. В парке планируется высадить деревья. Для каждого дерева нужно выделить участок прямоугольной формы с целочисленными сторонами и площадью, равной S.
Все участки должны быть равны, одинаково ориентированы, и их стороны должны быть параллельны сторонам пустыря.
Какое наибольшее количество деревьев можно высадить в парке?
Формат входных данных
В трёх строках вводится три числа N, M, S (1≤N⋅M≤1018,, 1≤S≤1012) —— длина поля, ширина поля и площадь участка соответственно.
Обратите внимание, что значения N, M и S могут превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++ тип long в Java и C#).
Формат выходных данных
В первой строке выведите одно целое число —— максимальное количество деревьев, которые можно высадить в этом парке. Гарантируется, что всегда удастся высадить хотя бы одно дерево.
Система оценки
Решения, правильно работающие при N, M, S≤102, будут оцениваться в 20 баллов. Решения, правильно работающие при S≤106, будут оцениваться в 40 баллов.
Замечание
В первом примере все участки будут иметь только размер 1×1, их поместится ровно 100 штук. Во втором примере оптимальный размер участков будет 2×1, их поместится ровно 5 штук.
В третьем примере оптимальный размер участка будет 3×3 и участков поместится только два. Три или более участков разместить невозможно.