Автор Задания, ответы и решения заключительного этапа 9 февраля 2024 всероссийской олимпиады школьников «Высшая проба» по информатике 8, 9, 10, 11 класс официальные материалы прошлых лет для подготовки к олимпиаде. Победители и призёры получают льготы при поступлении в ВУЗЫ. Первый уровень в перечне олимпиад.
Задания для 9-10 класса
Задания 9-10 класс Высшая проба информатика 2024Задания для 11 класса
Задания 11 класс Высшая проба информатика 2024Задача A. Ремонт кладовки
Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Дима купил кладовку размера X × Y × Z, где X, Y, Z — это длина, ширина и высота в метрах соответственно. Но она оказалась без окон, без дверей и с голыми стенами. В магазине продается два типа обоев. В наличии имеется S1 квадратных метров обоев первого типа, стоимостью C1 рублей за квадратный метр, а второго типа — S2 квадратных метров стоимостью C2 рублей за квадратный метр. Дима хочет сделать дверь размера A × B, где A — ширина, а B — высота, в одной из стен (обои на дверь клеить не надо). Также он хочет, чтобы на стенах, расположенных друг напротив друга, были наклеены одинаковые обои. То есть обе стены размером X × Z должны быть оклеены одним типом обоев. Аналогично, обе стены размером Y × Z также должны быть оклеены одним типом обоев. Определите, получится ли у него поклеить обои, и если получится, то какая минимальная сумма в рублях ему потребуется.
Формат входных данных
В первой строке вводится три целых числа X, Y и Z (1 6 X, Y, Z 6 10 000) — длина, ширина и высота комнаты. Во второй строке вводится четыре целых числа S1, C1, S2 и C2 (1 6 S1, C1, S2, C2 6 108 ) — количество квадратных метров обоев первого типа на складе, стоимость квадратного метра обоев первого типа, количество квадратных метров обоев второго типа и стоимость квадратного метра обоев второго типа. В третьей строке вводится два числа A и B (1 6 A, B 6 10 000) — ширина и высота двери.
Формат выходных данных
Определите, сможет ли Дима оклеить кладовку обоями. Если это невозможно, то выведите -1. Иначе выведите минимальную сумму в рублях, которую Дима потратит на покупку обоев.
Система оценки
Решения, верно работающие при X = Y = Z, будут оцениваться не менее чем в 30 баллов.
Замечание
В первом примере Дима установит дверь в стену размером 5 × 10 и наклеит первый вид обоев на все стены. Во втором примере Дима установит дверь в стену 5 × 10, наклеит первый вид обоев на стены 6 × 10 и второй вид обоев на стены 5 × 10. В третьем примере высота двери слишком большая. В четвертом примере суммарная площадь доступных обоев меньше, чем площадь стен.
Задача B. Цветочный магазин
Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт.
Петя открыл цветочный магазин. Магазин Пети занимается изготовлением и продажей букетов. Всего существует n видов цветов, занумерованных от 1 до n. Каждый букет, чтобы быть гармоничным и красивым, должен состоять из цветов всех видов, по одной штуке каждого вида. В магазине уже есть ai штук цветов вида i. На цветочной базе можно купить цветок любого вида за 1 рубль. Определите, сколько букетов сможет собрать Петя, если потратит не более x рублей на покупку цветов на базе. Ответьте на q запросов с различными xi .
Формат входных данных
В первой строке входных данных находятся два целых числа n и q (1 6 n, q 6 105 ) — количество различных типов цветов и количество запросов. Во второй строке находятся n целых чисел a1, a2, · · · , an (0 6 ai 6 109 ) — количество цветов каждого вида, имеющихся в магазине. В третьей строке находятся q целых чисел x1, x2, · · · , xq (0 6 xi 6 109 ) — запросы Пети.
Формат выходных данных
Выходной файл должен содержать q чисел, где i-е число это максимальное количество букетов, которое можно собрать потратив не более xi рублей.
Система оценки
Задача состоит из 20 тестов, не считая тестов из условия. Все тесты можно разделить на следующие группы. В первом примере у Пети изначально есть 1 цветок первого типа и 0 цветов второго типа. В первом запросе у него есть 1 рубль, он покупает цветок второго типа и делает 1 букет. Во втором запросе у него есть 2 рубля, он не может сделать два букета за 2 рубля, поэтому ответ по прежнему 1. В третьем запросе у него есть 5 рублей, он покупает 2 цветка первого типа и 3 цветка второго типа и делает 3 букета.
Задача C. Операции с числом
Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт.
Дима работает на складе чисел. Он входит на склад с двоичным числом x = 0. Ему необходимо превратить свое число x в число s. Для этого на складе есть два автомата для увеличения чисел. Первый автомат увеличивает двоичное число x на 1 за a секунд. Он расположен слева от входа на склад, в p секундах ходьбы от входа. Второй автомат умножает двоичное число x на 2 за b секунд. Он расположен справа от входа на склад, в q секундах ходьбы от входа.
Таким образом, если Диме понадобится дойти от одного автомата до другого, он потратит p + q секунд. Исходно он находится у входа на склад. Помогите Диме узнать, за какое наименьшее количество секунд можно получить число x = s и вернуться ко входу на склад. Число в двоичной системе счисления из n цифр, представимое в виде: a1a2 . . . an (ai ∈ {0, 1}), равно 2 n−1 · a1 + 2n−2 · a2 + . . . + 2 · an−1 + an. (a1 = 1 при n > 1, то есть число не имеет ведущих нулей).
Формат входных данных
В первой строке даны два целых числа a и b в десятичной записи (1 6 a, b 6 109 ) — время, которое потребуется автоматам для увеличения числа. Во второй строке даны целые числа p и q в десятичной записи (0 6 p, q 6 109 ) — расстояние от входа на склад до первого и второго автоматов. В третьей строке дано число s в двоичной системе счисления без ведущих нулей (кроме случая s = 0). Длина числа s не превышает 100 000 цифр.
Формат выходных данных
Выведите минимальное количество секунд, которое потребуется, чтобы из x = 0 получить x = s, пользуясь автоматами, и вернуться ко входу на склад. Система оценки Задача состоит из 25 тестов, не считая тестов из условия. Каждый тест оценивается независимо в 4 балла. Все тесты можно разделить на следующие группы.
Замечание
В первом тесте необходимо получить число s = 32 + 8 + 2 + 1 = 43 в десятичной записи. Оптимальная последовательность действий: Дима идет к первому автомату (2 секунды), прибавляет к числу единицу 5 раз (5 секунд), потом идет ко второму автомату (2 + 3 = 5 секунд), умножает число 3 раза (3 · 2 = 6 секунд) и получает число 40, возвращается к первому автомату (3 + 2 = 5 секунд), прибавляет единицу 3 раза (3 секунды), и идет ко входу на склад (2 секунды). Всего потрачено 28 секунд. Во втором тесте у Димы с самого начала есть число x = 0.
Задача D. Караваны и Провинции
Далекая страна содержит n городов, соединенных n − 1 дорогами, при этом из любого города можно добраться до любого другого по дорогам страны. Известно, что каждый город относится ровно к одной провинции. Город v относится к провинции tv. Обратите внимание, что конкретная провинция может являться любым подмножеством городов, и возможно из одного города провинции нельзя добраться до другого этой же провинции, проходя только через города этой провинции. Столицей является город номер 1. Банда разбойников собирается грабить караваны, которые будут идти через города страны. У каждого города есть коэффициент того, насколько удобно в нем грабить.
В городе v он равен cv. Вам приходят запросы двух типов: 1. Изменить провинцию, к которой относится город v, на tnew 2. В k городах с номерами a1, a2, . . . , ak появляется по одному каравану, которые идут в столицу (город с номером 1) по кратчайшему пути. Разбойники выбирают один город, который находится в провинции t, после чего грабят все караваны, которые пройдут через этот город. Если разбойники ограбят караваны в городе с номером v, то они получат cv · numv, где cv — коэффициент города v, а numv это количество караванов, проходящих через этот город. Определите максимальный ущерб, равный количеству награбленного разбойниками, для каждого запроса второго типа. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен 0.
Формат входных данных
В первой строке даны два целых числа n и q (2 6 n 6 200 000, 1 6 q 6 200 000) — количество городов и количество запросов. Во второй строке дано n − 1 целое число p2, p3, . . . , pn (1 6 pi < i), где число pi означает, что существует дорога между городами i и pi . В третьей строке дано n целых чисел t1, t2, . . . , tn (1 6 ti 6 n) — номера провинций у городов. В четвертой строке дано n целых чисел c1, c2, . . . , cn (1 6 ci 6 109 ) — коэффициенты успешности грабежа.
Далее идет q строк описаний запросов. В начале каждой строки дано одно целое число xi (1 6 xi 6 2) — тип запроса. 1. Если xi = 1, то далее идет два целых числа v и tnew (1 6 v, tnew 6 n) — номер города, у которого меняется провинция, и номер его новой провинции. 2. Если xi = 2, то далее идут целые числа t и k, и k целых чисел a1, a2, . . . , ak (1 6 t, k, ai 6 n) — номер провинции, в городе которой можно грабить; количество городов, из которых выходят караваны; и номера городов, из которых входят караваны. Гарантируется, что в одном запросе все ai различны. Также гарантируется, что сумма k по всем запросам второго типа не превышает 200 000.
Формат выходных данных
На каждый запрос второго типа выведите одно число — максимальное число, которое разбойники смогут получить. Если в провинции, указанной в запросе, нет ни одного города, то ответ на этот запрос равен 0.
Другие олимпиады по информатике на сайте:
24-26 октября 2023 Олимпиада по информатике 5-11 класс ответы и задания школьного этапа ВСОШ