На официальном сайте Всероссийской олимпиады школьников представлены задания и ответы школьного этапа олимпиады по информатике для учеников 9-11 классов, группа 2, запланированный на 26 октября 2022 года. Получите доступ к полной информации о заданиях, проверьте свои знания и подготовьтесь к успешному выступлению на олимпиаде. Участвуйте и достигайте новых успехов в области информатики!
🔗Список заданий “Сириус” по Информатике 9-11 класс – 2 группа🔗
1.Лука в кинотеатре
Ограничение по времени: 1 секунда
Воскресным утром в кинотеатре в двух залах одновременно начался показ фильмов. Фильм, показываемый в первом зале, имеет длительность a минут, а фильм, показываемый во втором зале — b минут. В каждом из залов после окончания фильма его сразу начинают показывать с начала. Любой посетитель может войти в любой из залов.
Лука знает, что с момента начала показа фильмов прошло t минут. Ему неважно, какой фильм посмотреть, так как Лука просто хочет весело провести время. Однако мальчик нетерпелив, поэтому хочет узнать, через какое минимальное время хотя бы в одном из залов начнут показывать фильм с начала.
Формат входных данных
Первая строка содержит одно целое число a (1≤a≤2⋅109) — длительность первого фильма в минутах.
Вторая строка содержит одно целое число b (1≤b≤2⋅109) — длительность второго фильма в минутах.
Третья строка содержит одно целое число t (0≤t≤2⋅1018) — время в минутах, прошедшее с начала показа фильмов.
Обратите внимание, что входные данные и ответ могут быть достаточно большими, поэтому следует использовать 64-битный тип данных, например long long в C/C++, long в Java, int64 в Pascal.
Формат выходных данных
Выведите одно целое число — минимальное время в минутах, через которое хотя бы в одном зале начнут показывать фильм с начала.
Система оценки
Решения, правильно работающие только для случаев, когда t не превосходит 2⋅109, будут оцениваться в 60 баллов.
Пояснение
Рассмотрим первый пример из условия. Фильм, показываемый в первом зале, имеет длительность 3 минуты, а фильм, показываемый во втором зале — 7 минут. Таким образом, первый фильм начинается спустя 0,3,6,9,12,… минут после начала показа, а второй фильм — спустя 0,7,14,21,28,… минут после начала показа. Лука знает, что с начала показа фильмов прошло 10 минут. Для того, чтобы попасть на начало первого фильма, ему придётся подождать 12−10=2 минуты, а чтобы попасть на начало второго фильма — 14−10=4 минуты.
Рассмотрим второй пример из условия. Оба фильма имеют длительность 5 минут и начинаются спустя 0,5,10,15,… минут после начала показа. Так как с момента начала показа прошло 10 минут, Луке не придётся ждать.
Рассмотрим третий пример из условия. Оба фильма начнутся спустя 9 минут после начала показа, поэтому вне зависимости от выбора фильма Луке придётся подождать 9−8=1 минуту.
Ввод
Вывод
3
7
10
2
5
5
10
0
3
9
8
1
2
4
1000000000000000000
0
2.Лука покупает динозавров
Ограничение по времени: 1 секунда
На карте «Шестёрочки» у Луки уже есть t бонусных баллов, за которые он может покупать фигурки динозавров. Лука хочет купить всю коллекцию новых динозавров, состоящую из r фигурок. Один динозавр стоит l бонусных баллов.
Баллы в «Шестёрочке» можно получить следующим образом: за покупку первого товара на карту начисляется p1 баллов, за покупку второго товара — p2 баллов, за покупку третьего товара — p3 баллов, за покупку четвёртого товара — снова p1 баллов, за покупку пятого товара — p2 баллов, и так далее. Какое минимальное количество товаров должен купить Лука, чтобы приобрести всю коллекцию динозавров?
Обратите внимание на то, что покупка товаров осуществляется не на бонусные баллы, а за настоящие деньги.
Формат входных данных
Первая строка содержит одно целое число t (0≤t≤1018) — изначальное количество баллов на карте.
Вторая строка содержит одно целое число r (0≤r≤109) — количество динозавров в коллекции.
Третья строка содержит одно целое число l (0≤l≤109) — стоимость одного динозавра.
Четвёртая строка содержит одно целое число p1 (0≤p1≤1017) — количество баллов, начисляемых за покупку.
Пятая строка содержит одно целое число p2 (0≤p2≤1017) — количество баллов, начисляемых за покупку.
Шестая строка содержит одно целое число p3 (0≤p3≤1017) — количество баллов, начисляемых за покупку.
Гарантируется, что p1+p2+p3>0.
Обратите внимание, что входные данные и ответ могут быть достаточно большими, поэтому следует использовать 64-битный тип данных, например, long long в C/C++, long в Java, int64 в Pascal.
Формат выходных данных
Выведите одно число — минимальное количество товаров, которые должен купить Лука, чтобы приобрести всю коллекцию динозавров.
Система оценки
Решения, правильно работающие только для случаев, когда t не превосходит 106, l и r не превосходят 103, а p1, p2 и p3 не превосходят 106, будут оцениваться в 35 баллов.
Решения, правильно работающие только для случаев, когда Луке потребуется покупать по три товара, будут оцениваться в 25 баллов.
Пояснение
Рассмотрим второй пример. Изначально у Луки есть два бонусных балла, при том что в коллекции два динозавра, каждый из которых стоит по пять баллов. Сначала Лука купит первый товар и получит два балла за первую покупку. Далее Лука купит второй товар, получит один бонусный балл, в сумме пять. Далее он купит третий товар и получит ещё три бонусных балла, в итоге восемь баллов. На покупку всех моделей из коллекции до сих пор не хватает, поэтому Луке придётся сделать ещё одну, четвёртую покупку, после чего он получит два балла (потому что за четвёртую покупку начисляется столько же, сколько и за первую). Теперь у Луки десять баллов, на которых он может купить всю коллекцию динозавров. Значит, ответ — четыре.
Ввод
Вывод
8
2
22
58
70
31
1
2
2
5
2
1
3
4
66
83
57
54
78
98
62
3.Лука наблюдает за кузнечиками
Ограничение по времени: 1 секунда
Любимое занятие Луки — наблюдать за кузнечиками. Сегодня утром, прогуливаясь по парку, он обнаружил кузнечика, который прыгал по окружности длиной n метров. Лука заметил, что за один прыжок кузнечик может переместиться по часовой стрелке на k или k+1 метров от своей текущей позиции на окружности. Мальчику стало интересно, какое минимальное количество прыжков потребуется кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.
Формат входных данных
Первая строка содержит одно целое число n (1≤n≤106) — длина окружности в метрах.
Вторая строка содержит одно целое число k (1≤k≤109) — характеристика длины прыжка кузнечика в метрах.
Гарантируется, что 1≤n⋅k≤109.
Формат выходных данных
Выведите одно целое число — минимальное количество прыжков, которое придётся сделать кузнечику, чтобы, начав прыгать из некоторой точки окружности, снова оказаться в ней.
Система оценки
Решения, правильно работающие только для случаев, когда n не превосходит 100, будут оцениваться в 60 баллов.
Пояснение
Рассмотрим первый пример из условия. Один из вариантов действий кузнечика таков:
Выполнить прыжок длины 3,
Выполнить прыжок длины 4,
Выполнить прыжок длины 3.
Таким образом, суммарно кузнечик преодолеет 3+4+3=10 метров, то есть вернётся в исходную точку.
Во втором примере из условия кузнечику достаточно выполнить пять прыжков длины 2.
В третьем примере из условия можно выполнить один прыжок длины 8 и два прыжка длины 7. Таким образом, суммарно кузнечик преодолеет 8+7+7=22 метра, то есть обойдёт окружность дважды и вернётся в исходную точку.
Ввод
Вывод
10
3
3
10
1
5
11
7
3
4.Лука и массив
Ограничение по времени: 2 секунды
У Луки есть массив из n целых чисел a1, a2, . . . , an. K каждому элементу массива можно произвольное количество раз применять каждую из следующих магических операций:
Выбрать некоторый элемент массива ai и заменить его на число [ai2] (данная запись обозначает число ai2, округлённое вниз). Для выполнения данной операции требуется k единиц энергии.
Выбрать некоторый элемент массива ai и заменить его на число ai−1. Для выполнения данной операции требуется одна единица энергии.
Ваша задача — определить, какое минимальное количество энергии необходимо, чтобы после выполнения магических операций все элементы массива были равны единице (то есть a1=a2=…=an=1).
Формат входных данных
Первая строка содержит одно целое число n (1≤n≤5⋅104) — количество элементов массива.
Вторая строка содержит одно целое число k (1≤k≤105) — количество энергии, необходимое для выполнения операции первого типа.
Каждая из следующих n строк содержит одно целое число ai (1≤ai≤109) — элементы массива.
Обратите внимание, что ответ может быть достаточно большим, поэтому следует использовать 64-битный тип данных, например, long long в C/C++, long в Java, int64 в Pascal.
Формат выходных данных
Выведите одно целое число — минимальное количество энергии, необходимое для требуемого преобразования массива.
Система оценки
Решения, правильно работающие только для случаев, когда k=1, будут оцениваться в 25 баллов.
Решения, правильно работающие только для случаев, когда все ai не превосходят 105, будут оцениваться в 50 баллов.
Пояснение
Рассмотрим первый пример из условия.
Первый элемент массива равен 4. Использовав одну единицу энергии, применим к нему первую магическую операцию, после чего первый элемент массива станет равен [42]=2. После этого применим к нему вторую операцию, также затратив одну единицу энергии.
Второй элемент массива уже равен 1, поэтому применять к нему операции не нужно.
К третьему элементу применим первую операцию, используя одну единицу энергии. После этого третий элемент станет равен [32]=1.
Во втором примере из условия применение первой операции расходует слишком много единиц энергии, поэтому выгодно применить вторую операцию девять раз.
Ввод
Вывод
3
1
4
1
3
3
1
100
10
9
5.Лука и локальная сеть динозавров
Ограничение по времени: 1 секунда
Лука смог приобрести всю коллекцию динозавров из «Шестёрочки» и обнаружил, что в динозаврах есть коммутаторы, поэтому ему захотелось объединить их в одну локальную сеть. Он расставил на декартовой плоскости всю коллекцию, то есть местоположение каждого динозавра задана двумя числами — координатами по осям x и y.
Лука хочет соединить их проводами так, чтобы между любыми двумя динозаврами существовал путь по этим проводам. Луку раздражают спутанные провода, поэтому никакие два провода не должны пересекаться (пересечения в концах отрезков разрешены). Кроме того, у Луки мало денег на покупку проводов, поэтому общее количество проведённых отрезков не должно превышать 2n.
Формат входных данных
Первая строка содержит одно целое число n (1≤n≤103) — количество динозавров.
В следующих 2n строках заданы координаты динозавров. В каждой строке записано одно целое число: первая строка содержит координату по оси x для первого динозавра, вторая строка — координату по оси y для первого динозавра, третья строка — координату по оси x для второго динозавра, и так далее. Таким образом, координата xi для i-го динозавра находится в (2i)-й строке входных данных, координата yi для i-го динозавра находится в (2i+1)-й строке входных данных. Гарантируется, что (−109≤xi,yi≤109), а также никакие два динозавра не находятся в одной точке плоскости.
Формат выходных данных
В первой строке выведите одно число m — количество проведённых проводов, либо число −1, если соединить динозавров описанным в условии способом невозможно.
Если существует подходящее под условие соединение, то в следующих m строках выведите по два целых числа — порядковые номера динозавров, соединённых очередным проводом.
Если решений несколько, можно вывести любое из них.
Система оценки
Решения, правильно работающие только для случаев, когда n не превосходит 4, будут оцениваться в 25 баллов.
Решения, правильно работающие только для случаев, когда никакие три динозавра не лежат на одной прямой, будут оцениваться в 25 баллов.
Решения, правильно работающие только для случаев, когда у всех динозавров координаты по оси x различны, будут оцениваться в 25 баллов.
Пояснение
Иллюстрация ответа для первого примера из условия:
Ввод
Вывод
6
8
7
-8
6
-7
-3
9
-3
6
2
4
1
7
1 2
1 5
2 3
2 6
3 6
3 4
4 5
3
-3
4
8
-4
-1
0
2
1 3
3 2