26 октября 2023 Сириус олимпиада по информатике ответы для 5, 6, 7, 8, 9, 10, 11 классов школьный этап 2023 ВСОШ
Ответы и решения для олимпиады по информатике Сириус для 5, 6, 7, 8, 9, 10, 11 класса школьного этапа 2023 всероссийской олимпиады школьников ВСОШ 3 группы регионов 26 октября.
Все ответы и решения: скачать
Ответы и решения для 5-6 класса
Задание 1: Лёша‑путешественник
Алексей очень спешил в поездку и, забежав в поезд, не успел посмотреть номер вагона, только посчитал, что перед ним находится не более 7 вагонов, а за ним —— не более 5 вагонов. При подсчёте Лёша не учитывает вагон, в который забежал. Всего в составе 10 вагонов.
Перечислите все возможные номера вагонов, в которых может оказаться Алексей. Каждый номер вагона записывайте в отдельное поле ввода, добавляя их по мере необходимости.
Задание 2: Легендарные тренировки
Легендарная футбольная группа занимается по легендарной системе тренировок.
Для очередной тренировки игроки делятся на 2 команды и проводят игру между командами, при этом считается, что каждый игрок первой команды сыграл против каждого игрока второй команды и наоборот. Количество игроков в командах может быть различным, но каждый игрок должен попасть в одну из команд.
На следующей тренировке игроки делятся на команды уже как‑то по‑другому.
Тренер считает, что очень важно, чтобы каждый игрок хотя бы раз сыграл против каждого другого. Помогите тренеру добиться этого за минимальное количество тренировок.
Например, если бы у тренера было 3 игрока, то ему было бы достаточно провести 2 тренировки. В первой тренировке нужно включить в первую команду первого и второго игроков, а во вторую —— третьего игрока. А во второй тренировке первую команду составить только из второго игрока, а вторую —— из первого и третьего игрока. Тогда первый игрок сыграет против второго во второй тренировке, первый против третьего —— в первой тренировке, и второй против третьего —— в обеих тренировках. Получается, что каждый игрок сыграет против каждого другого хотя бы один раз.
У нашего тренера 7 игроков в группе. Составьте для него расписание тренировок.
В качестве ответа выведите несколько строк. Каждая строка должна описывать одну тренировку. Для этого напишите номера игроков первой команды на тренировке в строку через пробел.
Например, для группы из 3 игроков ответ может выглядеть так: 1 22
Этот вариант распределения игроков по командам описан выше, есть и другие правильные ответы для группы из 3 игроков. Если в результате составленных вами тренировок каждый игрок сыграет с каждым, то ваше решение получит не меньше 40 баллов. Чем меньше тренировок вам понадобится, тем больше баллов вы получите. За минимальное количество тренировок, при котором каждый игрок сыграет с каждым другим, вы получите 100 баллов.
Задание 3: Рыцари и лжецы
В городе MM живут только рыцари и лжецы. Рыцари всегда говорят правду, а лжецы всегда врут. Каждый год у них проходит фестиваль. На фестивале есть квадратное поле, в каждую клетку которого встал либо рыцарь, либо лжец. Все они одновременно сказали, что во всех соседних по стороне клетках стоят лжецы. Это значит, что рядом с каждым рыцарем стоят только лжецы, а с каждым лжецом должен соседствовать хотя бы 1 рыцарь. Расставьте рыцарей и лжецов на поле 4×4, выполнив условия задачи и используя как можно меньше рыцарей.
Решения, при которых рыцари и лжецы окажутся расставлены корректно, будут оцениваться хотя бы в 10 баллов. Чем меньше рыцарей, тем больше баллов вы получите.
Ответ представьте в виде заполненной нулями и единицами таблицы размера 4×4, где 1 обозначает, что на этой клетке стоит рыцарь, а 0 —— что на этой клетке стоит лжец.
Задание 4: Последовательность
Маша любит исследовать разные последовательности. Сегодня она придумала такую. Первый элемент последовательности равен 1, а каждый следующий строится по такому принципу: если сумма цифр в текущем числе чётная, то к нему прибавляется 2, а если нечётная, то 1. Первые 10 чисел этой последовательности: 1, 2, 4, 6, 8, 10, 11, 13, 15, 17, …
Ответьте на вопросы.
1) Какое число будет стоять на 20 месте?
2) Какое число будет стоять на 100 месте?
3) Сколько нечётных чисел среди первых 47 чисел этой последовательности?
4) Сколько чётных чисел среди первых 103 чисел этой последовательности?
Задание 5: Игра
Петя нашёл консоль с электронной игрой. Консоль состоит из экрана, на котором изображено игровое поле, и трёх кнопок:
< (налево),
# (прямо),
> (направо).
Под центральным столбцом игрового поля находится птичка. Пете нужно управлять движением птички по игровому полю.
При каждом нажатии любой кнопки птичка передвигается на одну строку выше.
При этом если нажата кнопка <, то птичка смещается на один столбец влево, если нажата кнопка >, то птичка смещается на один столбец вправо, а если нажата кнопка ##, то птичка никуда не смещается, а просто поднимается выше в том же столбце.
Если в момент нажатия на кнопку < птичка находилась в крайнем левом столбце, или в момент нажатия на кнопку > птичка находилась в крайнем правом столбце, то ей некуда сдвигаться, и она просто поднимается вверх.
Некоторые клетки игрового поля запрещены для посещения птичкой, они выделены тёмным цветом. Если в результате своего хода птичка попадает на такую клетку, то она погибает, и игра заканчивается. Некоторые клетки игрового поля содержат бонусные монеты, они обозначены числами. Если в результате своего хода птичка попадает на такую клетку, то она получает то количество бонусных монет, которое написано на этой клетке. Задача игрока —— собрать максимальную сумму бонусных монет.
Программой для игры является строка, состоящая из символов <, #, >, эти символы задают последовательность нажатия кнопок. Запишите одну строку из 10 символов <, #, > —— программу, в результате выполнения которой птичка наберёт наибольшую сумму бонусных монет. Примером правильного оформления ответа является строка: #><###><#> Эта строка‑программа задаёт такой маршрут движения птички:
При этом птичка соберёт суммарно 4 бонусные монеты. Конечно, можно составить программу, чтобы набрать гораздо больше монет, поэтому предложенное решение является неправильным.
Система оценки
Чем больше бонусных монет наберёт птичка, двигаясь согласно предложенной вами программе, тем больше баллов вы получите.
Программы, в результате выполнения которых птичка соберёт менее 10 бонусных монет, будут оцениваться в 0 баллов.
Ответы и решения для 7-8 класса
Задание 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 и участков поместится только два. Три или более участков разместить невозможно.
Ответы и решения для 9-11 класса
Задание 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 секунды, и это число будет ответом.
Задания и ответы олимпиада Сириус школьный этап 2023 ВСОШ 4-11 класс