На официальном сайте Всероссийской олимпиады школьников представлены задания и ответы школьного этапа олимпиады по информатике для учеников 9-11 классов, группа 4, запланированный на 28 октября 2022 года. Получите доступ к полной информации о заданиях, проверьте свои знания и подготовьтесь к успешному выступлению на олимпиаде. Участвуйте и достигайте новых успехов в области информатики!
🔗Список заданий “Сириус” по Информатике 9-11 класс – 4 группа🔗
1.Треугольник из палочек
Ограничение по времени: 1 секунда
У Тимофея есть три палочки с натуральными длинами a, b и c, из которых можно сложить треугольник. За одну операцию мальчик отламывает от каждой палочки по кусочку единичной длины. Спустя какое минимальное количество операций из палочек уже нельзя будет сложить треугольник?
Для определённости считайте, что от палочки единичной длины можно отломить кусок длины 1, после чего палочка исчезнет.
Формат входных данных
Три строки входного файла содержат три натуральных числа a, b и c (1≤a,b,c≤109). Гарантируется неравенство треугольника для указанных длин.
Формат выходных данных
Выведите одно натуральное число — ответ на вопрос задачи.
Система оценки
Решения, правильно работающие для равных a, b и c, будут оцениваться в 10 баллов.
Решения, правильно работающие для a, b и c, не превосходящих 105, будут оцениваться в 40 баллов.
Пояснение
В примере дано a=10, b=18 и c=12. Три операции спустя длины сторон окажутся равны 7, 15 и 9 (треугольник можно сложить в последний раз). А вот после четвёртой операции длины палочек составят 6, 14 и 8, и треугольник окажется вырожденным.
Ввод
Вывод
10
18
12
4
2.Раскрашенный куб
Ограничение по времени: 1 секунда
Поверхность куба со стороной n см покрасили снаружи в синий цвет (со всех шести сторон). После этого его распилили на кубики со стороной 1 см. В результате получились части, у которых синим цветом окрашены 0, 1, 2 или 3 стороны. Посчитайте количество кубиков указанного вида.
Формат входных данных
Первая строка содержит натуральное число n (2≤n≤1000) — размер кубика.
Вторая строка содержит неотрицательное целое число f (0≤f≤3) — количество окрашенных граней у кубиков, число которых нужно посчитать.
Формат выходных данных
Выведите одно неотрицательное целое число — ответ на вопрос задачи. Гарантируется, что оно не превосходит 109.
Система оценки
Решения, правильно работающие при f=0, будут оцениваться в 30 баллов.
Решения, правильно работающие при f=1, будут оцениваться в 30 баллов.
Решения, правильно работающие при f=2, будут оцениваться в 30 баллов.
Решения, правильно работающие при f=3, будут оцениваться в 10 баллов.
Пояснение
В примере дано n=3 и f=1. Рассмотрим рисунок: куб 3×3×3 покрасили и распилили на 33=27 маленьких кубиков. Требуется определить, сколько таких кубиков имеют единственную синюю грань.
Это кубики, расположенные посередине каждой из шести граней, их ровно шесть.
Ввод
Вывод
3
1
6
3.Антон и арбузы
Ограничение по времени: 1 секунда
На лето родители отправили Антона к бабушке помогать ей выращивать в огороде арбузы. Чтобы они выросли большими и вкусными, требуется поливать растения каждый день, что и было поручено мальчику. Если арбуз был полит, он вырастает на один килограмм (а если не был, то остаётся прежнего размера) за каждый день.
Сам огород представляет собой прямоугольную сетку из n строк и m столбцов, в каждой ячейке которой растёт арбуз, изначально имеющий массу 0 килограмм. Антон очень не любит работать, поэтому в i-й день из всех d, что он будет гостить у бабушки, планирует поливать только арбузы, лежащие на пересечении первых xi строк и первых yi столбцов.
В конце лета за свою работу мальчик получит самый большой арбуз из имеющихся в огороде (а если их несколько, то сразу все самые большие!). Антон очень любит гигантские арбузы, поэтому просит вас определить, сколько же их в итоге ему достанется, и какого они будут веса.
Формат входных данных
Первые три строки входных данных содержат целые числа n, m и d, именно в таком порядке — количество строк и столбцов в огороде и время пребывания Антона у бабушки (1≤n,m≤109, 1≤d≤105). Далее идут 2d чисел xi и yi, каждое в отдельной строке, обозначающих количество строк и столбцов, арбузы в которых были политы мальчиком в день i (1≤xi≤n, 1≤yi≤m). Уточним, что эти данные упорядочены по дням, т.е. сначала идёт пара чисел x1,y1 именно в таком порядке, затем x2,y2 и так далее.
Отметим отдельно, что бабушка пронумеровала все строки и столбцы в огороде, и Антон всегда поливает именно xi первых строк и yi первых столбцов.
Обратите внимание, что при заданных ограничениях для хранения ответов необходимо использовать 64-битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.
Формат выходных данных
Выведите два числа через пробел — количество арбузов, которые достанутся Антону, и вес каждого из них.
Система оценки
Решения, правильно работающие, когда произведение чисел n, m и d не превосходит 106, будут оцениваться в 50 баллов.
Пояснение
В первом примере Антон один раз поливает квадрат 2×2, поэтому ему достанется 4 арбуза массой 1 килограмм каждый.
Во втором примере будут политы 3 арбуза в первом столбце и 2 арбуза в первой строке. Тогда ровно один арбуз окажется полит дважды, его Антон и получит.
Ввод
Вывод
3
3
1
2
2
4 1
4
3
2
3
1
1
2
1 2
4.Платные музыкальные сервисы
Ограничение по времени: 1 секунда
Платные музыкальные сервисы предлагают самый разный контент за любые деньги, но работают по одному и тому же принципу: за первый месяц подписки клиент платит a рублей, далее за каждый следующий месяц подписки — ещё d рублей. Таким образом, за n месяцев клиент заплатит a+(n−1)⋅d рублей. Известно, что для любых натуральных a и d существует ровно один сервис, который предлагает свои услуги именно на таких условиях.
У Тимофея есть m рублей, и ему требуется подключить ровно один сервис. Он хочет выяснить, на скольких из них он может получать за эти деньги доступ к музыке в течение n месяцев. Если денег хватит на количество месяцев, превышающее n, Тимофея такой сервис тоже устроит.
Формат входных данных
На вход подаются два натуральных числа n (2≤n≤106) и m (1≤m≤106), каждое в своей строке.
Обратите внимание, что при заданных ограничениях для хранения ответа может понадобиться 64‑битный тип данных, например, long long в C++, int64 в Pascal, long в Java.
Формат выходных данных
Выведите одно неотрицательное целое число — количество различных сервисов, на которых Тимофей может n месяцев получать доступ к музыке, заплатив при этом не более m рублей.
Система оценки
Решения, правильно работающие, когда число m не превосходит 2, получат не менее 10 баллов.
Решения, правильно работающие, когда число m не превосходит 1000, получат не менее 50 баллов.
Замечание
В примере из условия у Тимофея есть 7 рублей, и он хочет слушать музыку 3 месяца. Тогда ему подойдут следующие сервисы:
a=1, d=1 (он заплатит в сумме 1+2⋅1=3 рубля);
a=2, d=1 (он заплатит в сумме 2+2⋅1=4 рубля);
a=3, d=1 (он заплатит в сумме 3+2⋅1=5 рублей);
a=4, d=1 (он заплатит в сумме 4+2⋅1=6 рублей);
a=5, d=1 (он заплатит в сумме 5+2⋅1=7 рублей);
a=1, d=2 (он заплатит в сумме 1+2⋅2=5 рублей);
a=2, d=2 (он заплатит в сумме 2+2⋅2=6 рублей);
a=3, d=2 (он заплатит в сумме 3+2⋅2=7 рублей);
a=1, d=3 (он заплатит в сумме 1+2⋅3=7 рублей).
Таким образом, для данного примера у Тимофея есть возможность выбора из 9 музыкальных сервисов.
Ввод
Вывод
3
7
9
5.Линейный футбол
Ограничение по времени: 1 секунда
Близнецам Петру и Павлу родители подарили на день рождения настольный футбол, но не простой, а линейный.
В этом варианте игры все фигурки игроков расположены в одну линию на равном расстоянии друг от друга. Всего есть n игроков. Для определённости пронумеруем их позиции числами от 1 до n слева направо. Ворота находятся в позициях 0 и n+1. Каждый игрок имеет свою силу удара и может при ударе по мячу перебросить его на фиксированное количество позиций другому игроку. Силу удара игрока на позиции i обозначим через ai, что означает, что после удара этого игрока мяч переместится на ai позиций. Если ai положительное, то мяч переместится вправо, в сторону увеличения номеров, а если ai отрицательное, то мяч переместится влево, в сторону уменьшения. Если после удара мяч попадает в позицию, меньшую либо равную 0, то засчитывается гол в левые ворота, а если в позицию, большую либо равную n+1, то в правые. Если после удара мяч попадает к другому игроку, то тот наносит следующий удар со своей силой, и игра продолжается.
Близнецы решили сыграть n игр, в i‑й из которых первый удар нанесёт игрок номер i. Для каждой игры выведите, в какие ворота будет забит мяч в этой игре (L, если в левые, R, если в правые, U, если гол никто не забьёт).
Формат входных данных
Первая строка входных данных содержит целое число n (1≤n≤105) — количество игроков. Далее в следующих n строках указаны силы и направления ударов игроков. В i+1 строке указана сила игрока ai, находящегося в позиции i. После удара этого игрока мяч окажется в позиции i+ai. (−105≤ai≤105 для любого i от 1 до n).
Формат выходных данных
Выведите n символов, обозначающих результаты игр, в одну строку без пробелов. Если пронумеровать эти символы от 1 до n, то в i‑й позиции этой строки может находиться символ L для мяча, забитого в левые ворота, R для мяча, забитого в правые ворота и U для случая, когда игра не закончилась взятием ворот (при начале этой игры c удара i‑го игрока).
Система оценки
Решения, правильно работающие для случаев, в которых количество игроков не превосходит 100, получат не менее 44 баллов.
Решения, правильно работающие для случаев, в которых все игроки, кроме самого правого, ударяют вправо, получат не менее 12 баллов.
Решения, правильно работающие для случаев, в которых левая половина игроков ударяет вправо, а правая половина игроков ударяет влево, причём количество игроков, перебрасывающих мяч на противоположную половину поля, не превосходит 10, получат не менее 12 баллов.
Решения, правильно работающие для случаев, в которых каждая игра заканчивается взятием ворот, получат не менее 12 баллов.
Пояснение
В примере первый игрок сразу забивает в левые ворота. Второй игрок передаёт четвёртому, четвёртый — девятому, девятый — восьмому, восьмой — седьмому, а седьмой забивает в правые ворота. Третий игрок играет сам с собой. Пятый и десятый перекидывают мяч друг другу. Шестой передает пятому и далее снова играют пятый и десятый.
Открыть изображение в новой вкладке
Ввод
Вывод
10
-5
2
0
5
5
-1
6
-1
-1
-5
LRURUURRRU