Олимпиада школьного этапа ВсОШ по Информатике (Программирование) 9-11 класса задания и ответы: 3 группа, 21 октября 2026. Полный доступ к ответам и разбору всероссийской олимпиады, проходящей на площадке uts.sirius.
Скачать полные задания и ответы
Олимпиада ВсОШ по Информатике (Программирование) 9-11 класс 3 группа
Задание 1. Жетон в подарок
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Для участия в игре нужны жетоны. Один жетон стоит 1 рубль. При покупке каждых k оплаченных жетонов посетитель получает ещё один жетон бесплатно.
Пете нужно получить не меньше n жетонов. Какую наименьшую сумму он должен потратить?
Формат входных данных
В первой строке дано целое число k (1 ≤ k ≤ 10⁹).
Во второй строке дано целое число n (1 ≤ n ≤ 10⁹).
Формат выходных данных
Выведите одно целое число — наименьшую сумму в рублях.
Замечание
В первом примере Петя платит по 1 рублю за 1-й, 2-й, 4-й, 5-й, 7-й и 8-й жетоны, а 3-й и 6-й получает в подарок. Всего Петя заплатит 6 рублей.
Пример 1
Ввод:
2
8
Вывод:
6
Пример 2
Ввод:
3
3
Вывод:
3
Пример 3
Ввод:
1
5
Вывод:
3
→Узнать ответ
Задание 2. Два плаката
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Для выставки подготовили два прямоугольных плаката размером a × b и c × d сантиметров.
Их нужно разместить на квадратном стенде. Каждый плакат разрешается поворачивать на 90 градусов. Стороны плакатов должны быть параллельны сторонам стенда. Плакаты могут соприкасаться границами, но не должны перекрываться или выходить за границы стенда.
Найдите минимальную целую длину стороны стенда в сантиметрах, при которой можно разместить оба плаката.
Формат входных данных
В первой строке вводится целое число a (1 ≤ a ≤ 10⁹) — первая сторона первого плаката в сантиметрах.
Во второй строке вводится целое число b (1 ≤ b ≤ 10⁹) — вторая сторона первого плаката в сантиметрах.
В третьей строке вводится целое число c (1 ≤ c ≤ 10⁹) — первая сторона второго плаката в сантиметрах.
В четвёртой строке вводится целое число d (1 ≤ d ≤ 10⁹) — вторая сторона второго плаката в сантиметрах.
Формат выходных данных
Выведите одно целое число — минимальную длину стороны квадратного стенда в сантиметрах, на котором можно разместить оба плаката.
Система оценки
Решения, правильно работающие при a = b и c = d, будут оцениваться в 20 баллов.
Решения, правильно работающие при условии, что хотя бы один из плакатов квадратный, будут оцениваться в 30 баллов.
Решения, правильно работающие при a ≤ b и c ≤ d, будут оцениваться в 60 баллов.
Пример 1
Ввод:
2
2
3
3
Вывод:
5
Пример 2
Ввод:
5
2
3
4
Вывод:
5
→Узнать ответ
Задание 3. Лесная переправа
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Туристическая фирма водит группы в походы по лесу. Маршрут похода проходит через овраг ширины w. Раньше через этот овраг был перекинут мостик, но сейчас его сорвало ураганом.
Вдоль оврага растут деревья, для каждого дерева известны его высота и расстояние от него до оврага. Если свалить дерево в сторону оврага так, чтобы оно перекрыло его ширину, то по этому дереву можно будет перейти через овраг.
Например, пусть овраг имеет ширину 3, дерево расположено на расстоянии 5 от него и имеет высоту 10. Если свалить это дерево в сторону оврага, то оно его перекроет и по этому дереву можно будет перейти.
А если дерево расположено на расстоянии 4 и имеет высоту 6, то при его падении тот же овраг ширины 3 не перекроется и его нельзя будет перейти.
На завтра запланированы две группы, поэтому для их переправы нужно свалить два дерева. Определите, сколькими способами это можно сделать.
Обратите внимание, что значение ответа в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).
Формат входных данных
В первой строке содержится целое число w (1 ≤ w ≤ 10⁹) — ширина оврага.
Во второй строке содержится целое число n (1 ≤ n ≤ 10⁵) — количество деревьев, растущих вдоль оврага.
Далее записаны n пар целых чисел x, h, где x (0 ≤ x ≤ 10⁹) — расстояние от дерева до оврага, а h (1 ≤ h ≤ 10⁹) — высота каждого дерева. Каждое число в паре вводится с новой строки.
Формат выходных данных
Выведите количество способов, которыми можно выбрать два подходящих дерева.
Система оценки
Решения, правильно работающие при N ≤ 1000, получат не менее 40 баллов.
Замечание
Пояснение ко второму примеру.
Овраг имеет ширину 3, вдоль него расположено 5 деревьев.
Первое дерево расположено на расстоянии 5 и имеет высоту 10, с его помощью можно перейти овраг.
Второе дерево расположено на расстоянии 4 и имеет высоту 6, с его помощью нельзя перейти овраг.
Третье дерево расположено на расстоянии 2 и имеет высоту 2, с его помощью нельзя перейти овраг.
Четвёртое дерево расположено на расстоянии 4 и имеет высоту 7, с его помощью можно перейти овраг.
Пятое дерево расположено на расстоянии 2 и имеет высоту 10, с его помощью можно перейти овраг.
Получается, что для перехода через овраг подходят первое, четвёртое и пятое деревья.
Поэтому переправу можно сделать тремя способами:
1. Свалить первое и четвёртое деревья;
2. Свалить четвёртое и пятое деревья;
3. Свалить первое и пятое деревья.
Пример 1
Ввод:
3
4
1
10
5
3
3
8
10
10
Вывод:
1
Пример 2
Ввод:
3
5
5
10
4
6
2
2
4
7
2
10
Вывод:
3
→Узнать ответ
Задание 4. Верни палиндром
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Для прохождения очередного уровня в игре Пете нужно было составить из заданных букв слово-палиндром. Он быстро справился с этой задачей, но отвлёкся. Пока Петя не видел, его брат Витя поменял местами две буквы в строке, стоявшие на разных позициях.
Теперь Пете надо быстро найти позиции двух букв и поменять их местами, чтобы опять получился палиндром (не обязательно тот же самый).
Палиндром — это строка, которая читается одинаково как слева направо, так и справа налево. Например, level, noon, racecar.
Формат входных данных
На вход подаётся одна строка из строчных латинских букв длиной не менее 3 и не более 10⁵ символов.
Гарантируется, что данная строка может получиться из строки-палиндрома с помощью обмена местами двух символов, расположенных на разных позициях.
Формат выходных данных
Выведите два различных числа через пробел: номера символов в исходной строке — таких, что после обмена их местами получится палиндром. Нумерация элементов строки начинается с 1.
Если существует несколько пар элементов строки, дающих палиндром в результате обмена, то выведите любую пару.
Система оценки
Решения, правильно работающие со строками, длина которых не превышает 100, будут оцениваться в 50 баллов.
Замечание
Если в строке cbcaba поменять местами первый и четвёртый символы, то получится abccba, и это палиндром.
Заметим, что для данной строки также правильным ответом является пара 3 6, так как при обмене третьего и шестого символов получится cbaabc, что тоже является палиндромом.
Пример
Ввод:
cbcaba
Вывод:
1 4
→Узнать ответ
Задание 5. Нефтяные вышки
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт
Li-Fi (Light Fidelity) — это инновационная технология беспроводной связи, использующая модулированные световые лучи для передачи данных на высоких скоростях. Главной особенностью этого протокола является то, что для установки надежного соединения требуется прямая видимость между передатчиками: световой сигнал распространяется строго по прямой линии и не способен огибать препятствия.
Шельфовое нефтяное месторождение представляет собой прямоугольник размером n × m метров, разделённый на квадраты со стороной в один метр. В трёх разных квадратах нужно возвести по нефтяной вышке, которые будут объединены в единую сеть по протоколу Li-Fi.
Поскольку шельф представляет собой идеально ровную поверхность, прямая видимость между вышками обеспечивается только в том случае, если они находятся на одной вертикали или горизонтали. Для успешной настройки сети необходимо выполнить следующие условия:
• нефтяная вышка № 1 должна находиться на одной линии (в одной строке или столбце) с центральной вышкой № 2;
• нефтяная вышка № 3 также должна находиться на одной линии (в одной строке или столбце) с вышкой № 2.
Обратите внимание, что для настройки связи по протоколу Li-Fi вышки № 1 и № 3 могут находиться на одной линии друг с другом.
Вам известна стоимость проведения буровых работ и возведения вышки в каждой из клеток участка. Определите минимальную общую стоимость постройки трёх нефтяных вышек в различных клетках так, чтобы выполнить все условия связи.
Формат входных данных
Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 1000, n · m ≥ 3) — высоту и ширину нефтяного шельфа.
Следующие n строк описывают клетки шельфа. Каждая из них содержит m целых чисел aᵢⱼ (1 ≤ aᵢⱼ ≤ 10⁸) — стоимость возведения нефтяной вышки в соответствующей клетке.
Формат выходных данных
Выведите одно целое число — минимальную общую стоимость постройки трёх нефтяных вышек в соответствии с условиями организации сети.
Система оценки
Решения, правильно работающие при n = 1, будут оцениваться в 8 баллов.
Решения, правильно работающие при n, m ≤ 10, будут оцениваться в 10 баллов.
Решения, правильно работающие при n, m ≤ 100, будут оцениваться в 42 балла.
Замечание
В первом тесте оптимально поставить вышки в клетках с координатами (1, 2), (2, 1) и (2, 2).
Во втором тесте оптимально поставить вышки в клетках с координатами (1, 2), (1, 45) и (1, 6).
Пример 1
Ввод:
3 3
100 1 100
2 5 3
100 4 100
Вывод:
8
Пример 2
Ввод:
1 7
1298 12 927 17 10 12 17
Вывод:
34
→Узнать ответ
