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

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

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

Задание 1: Лёша‑путешественник

Ограничение по времени: 11 секунда
Ограничение по памяти: 256256 мегабайт
Алексей очень спешил в поездку и, забежав в поезд, не успел посмотреть номер вагона, зато успел посчитать, что перед ним находится не менее A вагонов, а за ним —— не более B вагонов. Всего в составе N вагонов. Выведите количество вариантов номера вагона, в котором может оказаться Алексей.

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

В первых трёх строках вводится 3 целых числа N, A, B (1≤N≤10^9,0<A,B<N).

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

Выведите одно целое число —— количество вариантов номера вагона, в котором может оказаться Алексей. Гарантируется, что ответ равен хотя бы 1.

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

Решения, правильно работающие при N≤10^5, будут оцениваться в 40 баллов.

Замечание

В первом тесте Лёша может находиться только в вагонах с номерами 6, 7, 8.​

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

Задание 2: Ход слона

Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Миша учится играть в шахматы. Самая любимая фигура Миши —— это слон, потому что слон может атаковать все клетки, которые находятся с ним на одной диагонали. Миша очень любознательный мальчик, поэтому он задумался: сколько клеток будет атаковать слон, если поставить его на клетку с номером строки R и номером столбца C на шахматной доске размером N×N?

Открыть изображение в новой вкладке

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

Первая строка содержит целое число N (3≤N≤109) —— размер шахматной доски.
Вторая строка содержит целое число R (1≤R≤N) —— номер строки, в которой расположен слон.
Третья строка содержит целое число C (1≤C≤N) —— номер столбца, в котором расположен слон.
Строки и столбцы нумеруются с единицы, начиная с левого нижнего угла.

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

Выведите одно целое число —— количество клеток, которые находятся под атакой слона.

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

Решения, правильно работающие при R=C, будут оцениваться в 16 баллов.
Решения, правильно работающие при N≤100, будут оцениваться в 22 балла.

Замечание

Первый пример рассмотрен на рисунке.
Во втором примере слон находится в уголке доски, поэтому может атаковать клетки только одной диагонали доски.

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

Задание 3: Озеленение

Ограничение по времени: 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 и участков поместится только два. Три или более участков разместить невозможно.

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

Задание 4: Заплыв

Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт

Петя любит плавать в реке. Место, доступное для плавания, ограничено буйками. Плавать левее первого буйка и правее последнего буйка запрещено.
Линия, вдоль которой расположены N буйков, проходит параллельно берегу. Будем считать, что буйки пронумерованы числами от 1 до N слева направо. Известны расстояния S1, S2, ……, SN−1, где Sj —— расстояние от буйка j до буйка (j+1).
В хорошую погоду Петя входит в воду напротив первого буйка, очень быстро доплывает до него, а затем несколько раз плавает до последнего буйка и обратно. После этого он возвращается от первого буйка к берегу. Но сегодня так не получится: по прогнозу погоды через T единиц времени начнётся сильный дождь.
Петя хотел бы войти в воду напротив одного из буйков, проплыть вдоль буйков вправо и вернуться обратно —— то есть выйти из воды там, где он заходил —— до начала дождя. При этом мальчик хотел бы проплыть вдоль как можно большего количества различных буйков.
Петя полагает, что он проплыл вдоль некоторого буйка, если оказался в воде строго напротив этого буйка.
Считайте, что Петя проплывает за одну единицу времени одну единицу расстояния между буйками в любом направлении. Буйки расположены близко к берегу, поэтому считайте, что расстояние от берега до буйка и обратно Петя преодолевает мгновенно.
Ваша задача —— определить номер буйка, напротив которого Петя войдёт в воду, и номер самого правого буйка, вдоль которого проплывёт Петя.

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

В первой строке содержится целое число N (2≤N≤105) —— количество буйков.
Во второй строке содержится целое число T (1≤T≤109) —— время, оставшееся до дождя.
В каждой из следующих N−1 строк по одному в строке содержатся целые числа S1 , S2, …, SN−1, где S (1≤Sj≤109, j=1,2,…,N−1), Sj —— расстояние между буйком j и буйком (j+1).

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

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

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

В этой задаче применяется потестовая система оценки.
Решения, верно работающие при N≤1000, могут набрать от 40 баллов.

Замечание

Поясним приведённые примеры.
В первом примере Петя может войти в воду напротив первого буйка, доплыть до четвёртого буйка, потратив 10 единиц времени, и вернуться назад. При этом он проплывёт вдоль четырёх буйков.
Также он может проплыть вдоль четырёх буйков, если войдёт в воду напротив третьего буйка и доплывёт до шестого буйка, а потом вернётся обратно. На это у него уйдёт 16 единиц времени, так что при желании он может проплыть ещё две единицы расстояния вправо и успеть вернуться до начала дождя, но следующего буйка он при этом не достигнет.
Ещё одна возможность для Пети состоит в том, чтобы войти в воду напротив четвёртого буйка и доплыть до седьмого буйка, а затем вернуться обратно. На это он потратит 18 единиц времени. Таким образом, правильными ответами будут не только 1 4, но и 3 6, и 4 7.
Во втором примере Пете не хватит времени, чтобы, войдя в воду напротив одного из буйков, успеть доплыть до другого и вернуться. Поэтому он может войти в воду напротив любого буйка, проплыть половину единицы расстояния вправо и обратно, а затем выйти на берег.

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

Задание 5: Перекрёсток

Ограничение по времени: 11 секунда
Ограничение по памяти: 256256 мегабайт
Путь Пети в школу пролегает через оживлённый перекресток. На этом перекрёстке есть светофоры для пешеходов и светофоры для автомобилей.
Пешеходы могут переходить дорогу только по пешеходным переходам.
Пронумеруем пешеходные переходы числами от 1 до 4 так, как показано на рисунке.
Углы перекрёстка будем обозначать комбинациями цифр 12, 23, 34 и 41 —— по номерам переходов, которыми можно воспользоваться, находясь на этом углу.
Для каждого перехода известно время RJ, в течение которого пешеходам горит красный свет, и время GJ, в течение которого пешеходам горит зелёный свет (J=1, 2, 3, 4). Также для каждого перехода известно время TJ, за которое его может перейти Петя.

Петя будет переходить ту или иную дорогу только в том случае, если успеет полностью перейти её на зелёный свет.
Чтобы попасть в школу, Пете нужно перейти с угла 12 на угол Y (Y≢12). Известно, что в тот момент, когда Петя достиг угла 12, на всех пешеходных светофорах включился красный свет.
Ваша задача —— определить, через какое минимальное время Петя сможет попасть на угол Y.

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

В первой строке содержится число Y (Y ∈ {23, 34, 41}) —— обозначение угла, на который нужно попасть Пете.
Во второй строке содержатся три целых числа R1, G1, T1, записанных через пробел.
В третьей строке содержатся три целых числа R2, G2, T2, записанных через пробел.
В четвёртой строке содержатся три целых числа R3, G3, T3, записанных через пробел.
В пятой строке содержатся три целых числа R4, G4, T4, записанных через пробел.
Здесь RJ —— время, в течение которого на переходе J горит красный свет, GJ —— время, в течение которого на переходе J горит зелёный свет, TJ —— время, в течение которого Петя может пересечь переход J (J=1, 2, 3, 4). Все числа положительные и не превосходят 106.

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

Выведите целое число —— минимальное время, которое потребуется Пете, чтобы попасть с угла 12 на угол Y.
Гарантируется, что Петя всегда может перейти на угол Y.

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

В этой задаче применяется потестовая оценка.
Верные решения, предполагающие, что TJ≤GJ, могут набрать от 8080 баллов.

Замечание

Поясним приведённые примеры.
Рассмотрим первый пример.
Предположим, что Петя решил идти на угол 34 через угол 23. В этом случае он сначала дождётся окончания красного сигнала на переходе 2 —— это произойдёт через 120 секунд, после чего перейдёт на угол 23 за 14 секунд. Таким образом, он окажется на этом углу в момент 134.
Теперь ему нужно пройти по переходу 3. К моменту 134 на светофоре перехода 3 горит красный сигнал. Действительно, в течение 60 секунд горел красный, затем в течение 22 секунд горел зелёный, и в момент 82 секунды вновь включился красный, который будет гореть до момента 142 секунды. Таким образом, Пете придётся подождать 8 секунд, после чего он сможет перейти дорогу за 10 секунд и окажется на углу 34 в момент 152 секунды.
Рассмотрим другую возможность: пусть Петя решил идти на угол 34 через угол 41. В этом случае он будет ожидать на переходе 1 в течение 80 секунд, пока горит красный, а затем перейдёт дорогу за 12 секунд и окажется на углу 41 в момент 92 секунды.
Далее Пете нужно перейти по переходу 4. В момент 90 на переходе 4 красный сигнал светофора сменился на зелёный, при этом горит зелёный сигнал в течение 18 секунд. Это значит, что в момент, когда Петя окажется на углу 41, зелёный сигнал уже будет гореть в течение 2 секунд, так что на переход Петя может потратить до 16 секунд. Нам известно, что на пересечение этого перехода Пете требуется 14 секунд, поэтому Петя может сразу начать движение по переходу 4. На углу 34 он окажется в момент 92+14=106 секунд.
Как можно видеть, второй вариант позволяет Пете оказаться на углу 34 раньше, именно это число и является ответом.
Теперь рассмотрим второй пример.
Если Петя пойдёт на угол 41 напрямую, он потратит на это 3255 секунд.
Если Петя пойдёт сначала на угол 23, то там он окажется в момент 144 секунды —— сначала ему придётся подождать 120 секунд, пока включится зелёный сигнал, а затем он сможет перейти дорогу 2 за 24 секунды.
В момент 144 на переходе 3 будет гореть красный сигнал. В момент 85 секунд на этом переходе включился зелёный, в момент 85+25=110 секунд он сменился красным, и красный сигнал будет гореть до момента 195 секунд. В этот момент Петя сможет перейти дорогу 3 за 14 секунд и окажется в момент 209 секунд.
В момент 209 секунд на переходе 4 будет гореть зелёный сигнал. В момент 90 секунд на этом переходе включится зелёный сигнал, в момент 108108 секунд он сменится красным, затем в момент 198 секунд вновь загорится зелёный и будет гореть до момента 216 секунд. Однако Петя не пойдёт через дорогу: 7 секунд на переход ему не хватит. Поэтому он подождёт до момента 3053 секунд, когда красный сигнал вновь сменится зелёным, и уже тогда перейдёт дорогу. Таким образом, он окажется на углу 41 в момент 323 секунды, и это число будет ответом.