Школьный этап ВсОШ по Информатике “Сириус” 2 группа 7-8 класс 2023-2024 (Задания и Ответы)

Официальные задания и ответы школьного этапа 2023-2024 всероссийской олимпиады школьников Сириус по Информатике 7-8 класс 25.10.2023

Задания и ответы ВсОШ Сириус по Информатике 2023-2024 (25 октября 2023)
Приобрести задания и ответы (все варианты)

Задание 1: Игра Арсения

Арсений играет в игру «Раскраска». Мальчик выбирает на белой клетчатой доске, имеющей n строк и m столбцов, начальную клетку и красит её в чёрный цвет, после чего происходит несколько ходов.
За первый ход все непосредственные соседи выбранной клетки (то есть клетки, имеющие с выбранной общую границу) будут окрашены в чёрный цвет.
За второй ход все соседи клеток, окрашенных на предыдущем ходу, тоже окажутся окрашены в чёрный цвет и так далее.
Арсений хочет выбрать начальную клетку таким образом, чтобы таблица окрасилась полностью через как можно меньшее число ходов. Через сколько ходов таблица будет окрашена?
Даны четыре значения n и m, для которых требуется посчитать минимальное число ходов, после которых таблица будет полностью окрашена. Если вы не знаете ответ для какого‑то из примеров, запишите 0.

Ответ на задание

Задание 2: Капибары

Амир хочет подарить Ляйсан n капибар, пронумерованных натуральными числами от 1 до n.
Ляйсан не может оставить всех капибар у себя, так как любые две капибары, у которых сумма номеров кратна разности номеров, будут ссориться. Капибар, которых девочка не сможет у себя оставить, она подарит ответственным друзьям.
Амир знает, что Ляйсан оставит у себя наибольшее количество капибар. Помогите Амиру узнать номера грызунов, которых оставит у себя Ляйсан для разных значений n. Учтите, что Ляйсан хочет оставить у себя как можно больше капибар.
Даны четыре возможных значения n, для которых Амир хочет узнать ответ. Для каждого примера запишите через пробел номера капибар, которых Ляйсан сможет оставить у себя.

Ответ на задание

Задание 3: Секретные слова

Ваш знакомый Петя работал шифровальщиком на секретном предприятии и столкнулся с проблемой создания нового качественного шифра. После длительной работы ему наконец удалось это сделать. Петя попросил вас оценить его труды.
В шифре Пети запрещено использовать слова, в которых есть хотя бы две подряд идущие буквы, такие, что и в алфавите они тоже идут подряд. Например, слова «аббревиатура», «деятельный» —— содержат пары букв АБ и ДЕ соответственно. Такие слова в шифре использовать нельзя. А вот слово «банк» —— подходит для шифра Пети.
Дана последовательность букв —— Б, А, Й, Т —— из которой необходимо составить как можно больше слов для шифра Пети. Каждую букву из набора можно использовать только один раз. Словом считается любая последовательность символов, не обязательно осмысленная.
Выпишите все возможные четырёхбуквенные слова для шифра, используя для каждого слова заданный набор целиком. Каждое слово записывайте в отдельное поле, добавляя их по мере необходимости.
Ответ на задание

Задание 4: Трёхзначный вариант

Ваш учитель математики для подготовки к контрольной создал огромное количество вариантов (с номерами от 100 до 999) и выдал их ученикам заранее. При этом, чтобы у учеников появился интерес, он поставил интересное условие. На доске написано три трёхзначных числа. Учитель сказал, что если ученик сможет назвать ещё одно трёхзначное число, такое, что у него будет совпадать с каждым из написанных чисел ровно один разряд, то ученик может выбрать этот вариант. При этом вы понимаете, что сложность вариантов возрастает с увеличением их номера.
Постарайтесь выбрать минимальное число, удовлетворяющее заданному условию, тогда вы с лёгкостью получите отличную оценку на контрольной. Поняв алгоритм действий, помогите трём своим лучшим друзьям.
Даны четыре примера троек чисел, записанных на доске. Для каждого из них укажите минимальное возможное трёхзначное число, удовлетворяющее заданному условию. Если вы не знаете ответ для какого‑то из примеров, запишите 0.

Ответ на задание

Задания по программированию.

Задание 1: Вирус

Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
По сети распространяется вирус, который заражает по t компьютеров в конце каждого дня. Специалист по информационной безопасности Евгений узнал про вирус и уже готовится от него избавиться. Как только вирус заразит хотя бы k компьютеров, Евгений сразу же идентифицирует угрозу и начнёт с ней работать. Однако, чтобы обезвредить вирус, Евгению понадобится ещё m дней, и только в конце m-го дня ему удастся спасти пользователей сети.
Сейчас Евгений занят расчётами —— ему интересно, сколько суммарно дней пройдёт прежде, чем вирус будет обезврежен. Помогите Евгению ответить на этот вопрос.

Формат входных данных

Первая строка содержит одно целое число t (1⩽t⩽10⁹) —— количество компьютеров, которые заражаются вирусом каждый день.
Вторая строка содержит одно целое число k (1⩽k⩽10⁹) —— количество компьютеров, которые должен заразить вирус, чтобы его можно было идентифицировать.
Третья строка содержит одно целое число m (1⩽m⩽10⁹) —— количество дней, которые понадобятся Евгению, чтобы обезвредить вирус после его обнаружения.

Формат выходных данных

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

Система оценки

Решения, правильно работающие при k⩽100 000, будут оцениваться в 30 баллов.
Решения, правильно работающие при k, делящемся на t, будут оцениваться в 45 баллов.

Замечание

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

Задание 2: Кинотеатр

Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Евгений насколько усердно боролся с компьютерным вирусом, что сам заболел, и, поскольку он не мог оставить работу, Евгений заразил всех своих коллег, которые заразили своих знакомых и так далее. В итоге весь ваш город оказался заражён. На фоне этой эпидемии власти ввели масочный режим, а в ваш любимый кинотеатр «Малина» теперь пускают только по электронному сертификату о прививке.
Сегодня вы решили сходить в ваш любимый кинотеатр. Подойдя ко входу в здание кинотеатра, вы встали в очередь, в которой вместе с вами находятся n человек. В начале очереди у посетителей проверяют наличие сертификата о прививке. Подтверждение сертификата каждого посетителя занимает q секунд, после чего человек отправляется в зал на показ фильма. Как и всегда, у входа в зал собралась очередь из m человек с билетами, которые предстоит проверить контролёру. Проверка билета одного человека занимает t секунд, после чего человек сразу же занимает место в кинозале.
Перерыв в кинотеатре закончится с минуты на минуту, после чего очереди двинутся, и в скором времени вы сможете посмотреть фильм. Но вас, как настоящего программиста, интересуют точные значения. Поэтому, пока перерыв не закончился, вам предлагается написать программу, которая по заданным значениям n, q, m и t посчитает, сколько секунд вам придется подождать после окончания перерыва, прежде чем вы окажетесь в кинозале.

Формат входных данных

Первая строка содержит одно целое число n (1⩽n⩽10⁹) —— количество человек в первой очереди, считая вас.
Вторая строка содержит одно целое число q (1⩽q⩽10⁹)—— время проверки сертификата.
Третья строка содержит одно целое число m (1⩽m⩽10⁹) —— количество людей во второй очереди.
Четвёртая строка содержит одно целое число t (1⩽t⩽10⁹) —— время проверки билета контролёром.

Формат выходных данных

Выведите одно целое число —— количество секунд, по истечении которых вы окажетесь в кинозале.

Система оценки

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

Замечание

Рассмотрим первый тестовый пример. В первой очереди стоят два человека, каждому из которых требуется одна секунда, чтобы перейти во вторую очередь. Во второй очереди стоят три человека, каждому из которых также требуется по секунде, чтобы выйти из очереди.
Таким образом, в первую секунду первый человек из первой очереди перейдёт во вторую очередь, а первый человек из второй покинет очередь. После чего во второй очереди останется три человека, а в первой—— один. По истечении второй секунды оставшийся в первой очереди человек перейдёт во вторую, а первый человек из второй очереди покинет её. Таким образом, во второй очереди останется три человека, а в первой уже никого не останется. После чего этим трём людям потребуется суммарно три секунды, чтобы пройти очередь. Поэтому ответ в данном случае —— пять секунд.
Обратите внимание, что ответы могут получиться достаточно большими, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Free\Pascal.
Ответ на задание

Задание 3:

Подотрезок

Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Переполненные впечатлениями после фильма, вы вышли из кинотеатра. «Побег из матрицы» оставил очень много вопросов без ответа.
В самом конце фильма была показана битовая строка s, состоящая из n символов, каждый из которых был равен 0 или 1. Играла напряжённая музыка, и Мёбиусу предстояло принять судьбоносное решение. Он должен был выбрать два индекса l и r, после чего инвертировать биты на подотрезке sl, s_l+1, …… , sr. Иными словами, на выбранном подотрезке Мёбиус должен был заменить каждый символ, равный 0, на 1 и наоборот. Судьба Мёбиуса зависела от того, сможет ли он найти такие индексы, чтобы после инвертирования битов на соответствующем подотрезке битовая строка s состояла бы из одинаковых символов.
И вот, в самый интересный момент фильм закончился, а зрители так и не узнали, какой выбор сделал Мёбиус. Не желая дожидаться следующей части фильма, вы захотели сами разгадать тайну. Для этого вы решили написать программу, которая по заданной строке s, состоящей из n символов, найдёт такие индексы l и r, что после инвертирования битов на подотрезке sl, s_l+1, …… , sr строка s будет состоять из одинаковых символов.

Формат входных данных

Первая строка содержит одно целое число n (1⩽n⩽100 000).
Вторая строка состоит из n символов 0 или 1 и описывает битовую строку s.

Формат выходных данных

Выведите два целых числа l и r (1⩽r⩽n) —— границы подотрезка, который мог бы выбрать Мёбиус. Если существует несколько подходящих пар индексов, выведите любую из них. Если такого подотрезка не существует, выведите число −1.

Система оценки

Решения, правильно работающие при n⩽100, будут оцениваться в 30 баллов.
Решения, правильно работающие при n⩽1000, будут оцениваться в 60 баллов.

Замечание

В первом примере Мёбиус мог выбрать подотрезок, который состоит из одного символа, стоящего на второй позиции. Тогда после инвертирования второго бита строка «010» станет равна строке «000», состоящей только из нулей.
Во втором примере Мёбиус мог выбрать всю строку как подотрезок, тогда после инвертирования строка будет равна строке «1111», состоящей только из единиц.
Ответ на задание