Задания и ответы пригласительного этапа 2022 года ВОШ (Сириус) по Информатике для 8-10 класса всероссийская олимпиада школьников, дата проведения онлайн олимпиады: 26-27.05.2022 (26-27 мая 2022 г.).
Задание 1
Одного только не хватало мистеру Уолтерсу для полного счастья: возможности вручить наградную Библию и похвастать чудом учёности. У некоторых школьников имелись жёлтые билетики, но ни у кого не было столько, сколько надо, —— он уже опросил всех первых учеников. И в ту самую минуту, когда всякая надежда покинула его, вперёд выступил Том Сойер с девятью жёлтыми билетиками, девятью красными и десятью синими и потребовал себе Библию.
Марк Твен. Приключения Тома Сойера
Для получения одной награды нужно предъявить 10 жёлтых билетиков. 10 красных билетиков можно заменить на один жёлтый. 10 синих билетиков можно заменить на один красный. У Тома сейчас yy жёлтых билетиков, rr красных и bb синих. Сколько наград Том может получить?
Формат входных данных:
Три строки входного файла содержат три натуральных числа: yy, rr и bb. Все числа не превосходят 2×109.
Формат выходных данных:
Выведите одно неотрицательное целое число —— количество наград, которые может получить Том. В записи этого числа не должно быть десятичной точки, то есть вывод «1.0» вместо «1» является неправильным.
Система оценки:
Решения, верно работающие при b=r=0, будут оцениваться в 10 баллов.
Решения, верно работающие при b=0 будут оцениваться в 30 баллов.
Решения, верно работающие при y,r,b≤105, будут оцениваться в 55 баллов.
Замечание:
Пример из условия соответствует эпиграфу. Том обменяет 10 синих билетиков на 1 красный, после чего у него станет 9+1=10 красных билетиков. Далее он обменяет эти 10 красных билетиков на 1 жёлтый, и у него станет 9+1=10 жёлтых билетиков. В конце он обменяет эти 10 жёлтых билетиков на одну награду.
Ввод
9 9 10
Вывод
1
Ограничения
- Время выполнения: 1 секунда
Задание 2
Если цифры составляют часть системы символов, в них обычно заметен некий смысл, например, они являются математической прогрессией или определённой комбинацией, то есть каким-то образом связаны друг с другом.
Дэн Браун. Код да Винчи
Зайдя в класс, Вова увидел на доске три числа, записанные в ряд. Он не заметил никакой взаимосвязи между ними, и ему сказали, что изначально чисел было четыре и разности между четвёртым и третьим, третьим и вторым, вторым и первым равнялись друг другу. Иными словами, на доске была записана арифметическая прогрессия из четырёх чисел. Однако затем одно из чисел с доски стёрли.
Помогите Вове придумать и дописать на доску какое‑нибудь число так, чтобы описанное условие снова начало выполняться.
Формат входных данных:
Программа получает на вход три целых положительных числа, не превосходящих 105105 каждое, по одному в строке, в том порядке, в котором они шли на доске.
Формат выходных данных:
В первой строке выведите число, которое Вове необходимо написать. Можно доказать, что это число обязательно должно быть целым. В записи этого числа не должно быть десятичной точки, то есть вывод «13.0» вместо «13» является неправильным.
Во второй строке выведите целое число от 1 до 4 —— место, на которое его необходимо написать. 1 означает, что указанное число необходимо выписать перед первым из трёх приведённых во входных данных чисел, 2 —— между первым и вторым, 3 —— между вторым и третьим и 4 —— после третьего числа.
Гарантируется, что входные данные таковы, что существует хотя бы один способ дополнить их до арифметической прогрессии. Если подходящих способов несколько, выведите любой из них.
Замечание:
В примере из условия Вова увидел на доске числа 10,16 и 19. Если он напишет на доску между первым и вторым из них число 13, то в получившейся четвёрке чисел 10 13 16 19 разность между четвёртым и третьим (19−16), третьим и вторым (16−13) и вторым и первым (13−10) окажется одна и та же, поэтому эта четвёрка будет арифметической прогрессией.
Ввод
10 16 19 Вывод 13 2
Ограничения
- Время выполнения: 1 секунда
Задание 3
С утра по Васюкам ходил высокий худой старик в золотом пенсне и в коротких, очень грязных, испачканных клеевыми красками сапогах. Он наклеивал на стены рукописные афиши.
И.Ильф, Е.Петров. Двенадцать стульев
Ипполит Матвеевич Воробьянинов ходит вдоль улицы из nn домов, пронумерованных числами от 1 до n, и расклеивает афиши. Сначала он наклеил афиши на каждый дом, номер которого делился без остатка на aa. Поскольку афиш осталось ещё много, вторым проходом он наклеил афиши на каждый дом, номер которого делился без остатка на b. При этом, если на доме уже была наклеена афиша, новую Воробьянинов не клеил. Сколько всего афиш расклеил бывший предводитель дворянства?
Формат входных данных:
Три строки содержат три натуральных числа: nn —— количество домов на улице, a и b —— выбранные Воробьяниновым числа. Все числа не превосходят 109.
Формат выходных данных:
Выведите одно неотрицательное целое число —— количество расклеенных афиш.
Система оценки:
Решения, верно работающие при n≤105, будут оцениваться в 60 баллов.
Решения, верно работающие при a=2, будут оцениваться в 20 баллов.
Замечание:
В первом примере на улице 10 домов. Ипполит Матвеевич первым проходом расклеил пять афиш на дома, номера которых делятся на 2, то есть на дома с номерами 2,4,6,8,10.. Вторым проходом он расклеил две афиши на дома, номера которых делятся на 3, то есть на дома с номерами 3 и 9. Дом номер 6 Воробьянинов пропустил —— на нём афиша уже висит. Всего наклеено 7 афиш.
Во втором примере Воробьянинов не наклеит ни одной афиши.
Ввод
10 2 3
Вывод 7
Ввод 5 10 20
Вывод 0
Задание 4
Одиночество есть жребий всех выдающихся умов.
Артур Шопенгауэр
Однажды в летнем лагере после ужина осталась лишняя булочка. Выяснить, кому она достанется, дети решили с помощью жребия Крижановского. Правила этой игры такие: каждый участник называет ведущему натуральное число. Среди этих чисел выбираются те, которые были названы ровно один раз, а назвавший минимальное из этих чисел объявляется победителем. Обратите внимание, что победителя может не быть, если среди названных чисел каждое встречается несколько раз.
Вас назначили ведущим. Помогите установить победителя или определить, что такового нет.
Формат входных данных:
В первой строке дано одно число nn (1≤n≤105) —— количество участников игры. Далее в nn строках вводятся названные участниками натуральные числа, не превосходящие 109.
Формат выходных данных:
Программа должна вывести число, написанное победителем. Если победителя нет, то нужно вывести число —1.
Система оценки:
Решения, верно работающие при n≤103, будут оцениваться в 40 баллов.
Решения, верно работающие, когда все числа не превосходят 105, будут оцениваться в 30 баллов.
Замечание:
В первом примере из условия участвовали 7 игроков, которые назвали числа 5, 1, 1, 3, 4, 3, 1. Сначала оставим только те числа, которые встречаются ровно один раз: 5 и 4. Минимальное из этих чисел равно 4.
Во втором примере победителя нет, т.к. каждое из названных чисел встречается несколько раз.
Ввод
7 5 1 1 3 4 3 1
Вывод 4
Ввод 7 2 3 9 3 9 9 2
Вывод -1
Задание 5
Вызываемые мальчики подходили к доске и должны были писать мелом требуемые цифры и считать их как‑то от правой руки к левой…
Сергей Аксаков. Детские годы Багрова‑внука
На доске написано число nn, с которым несколько раз производят следующую операцию: если в записи числа на доске есть хотя бы одна нечётная цифра, то очередной мальчик вычитает из него 1, в противном случае —— делит на 2. Сколько мальчиков нужно вызвать, чтобы на доске получился ноль?
Формат входных данных:
Единственная строка входного файла содержит натуральное число nn (1≤n≤1018).
Обратите внимание, что входные данные в этой задаче могут превышать возможное значение 32‑битной целочисленной переменной, поэтому необходимо использовать 64‑битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C и C++, тип long в Java и C#).
Формат выходных данных:
Выведите одно натуральное число —— ответ на вопрос задачи.
Система оценки:
Решения, верно работающие при n≤105, будут оцениваться в 40 баллов.
Замечание:
В примере дано n=25. Число имеет в своей записи нечётную цифру 5, поэтому после первой операции nn уменьшится на 1 и станет равно 24. Число 24 не имеет в своей записи нечётных цифр, поэтому после второй операции nn уменьшится в 2 раза и станет равно 12.
Далее nn будет принимать значения: 11,10,9,8,4,2,1 и 0. Всего потребуется 10 операций.
Ввод
25
Вывод 10
Ограничения
- Время выполнения: 1 секунда
