хой. Задания. Задача B. Лепрекон Имя входного файла стандартный ввод Имя выходного файла стандартный вывод Ограничение по времени 2 секунды Ограничение по памяти 256 мегабайт в сериале Американские боги
 Скачать 54.22 Kb.
|
|
Высшая проба, информатика Заключительный этап, 4 февраля 2019 Задача A. Сквозь вселенные Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Рик и Морти путешествуют по мультивселенной. В мире Рика и Морти существуют n вселенных. Недавно Морти захотел узнать, сколько вообще существует вариантов их с Риком путешествий по мультивселенной (путешествие — обход всех вселенных в каком-то порядке). Так как Морти не очень умный, а число вселенных большое, он ограничится количеством путешествий по модулю m. Более того, как вы знаете существуют клоны Морти. Поэтому за помощью к вам пришел не один Морти, а целых три. Помогите им в их тяжелом занятии. Формат входных данных На вход поступают три строки, каждая из которых содержит два целых числа n, m (1 ⩽ n ⩽ 10 18 , 1 ⩽ m ⩽ 10 6 ). Формат выходных данных Вывести 3 числа — ответ для каждого из Морти. Система оценки Решения, работающие при n ⩽ 10 6 , будут получать не менее 40 процентов баллов. Пример стандартный ввод стандартный вывод 1 2 3 7 3 6 1 6 0 Замечание Пояснение к тесту из условия. Для n = 1 существует только один обход — посетить первую вселенную, для n = 3 существует 6 различных обходов (123, 132, 213, 231, 321, 312), поэтому по модулю 6 это 0, а по модулю 7 — 6. Страница 1 из 5 Высшая проба, информатика Заключительный этап, 4 февраля 2019 Задача B. Лепрекон Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт В сериале «Американские боги», внезапно, существуют боги и подвластные им существа. Сума- сшедший Суини — лепрекон и, как у каждого уважающего себя лепрекона, у него есть горшочек с золотыми монетами, притом некоторые из золотых монет являются счастливыми. У него n монет и для каждой счастливой известно, что ее номинал равен ⊕ (операция побитового исключающего или — «XOR») номиналов всех монет, кроме нее. Суини доверил вам свой горшок с монетами, но теперь у него есть q просьб к вам. Просьбы бывают трех типов: 1. Удалить из горшочка монету номинала x, при этом гарантируется, что монета такого веса присутствует на данный момент. 2. Добавить в горшочек монету номинала x. 3. Найти количество счастливых монет. Формат входных данных В первой строке даны два целых числа n и q (1 ⩽ n ⩽ 5 · 10 5 , 1 ⩽ q ⩽ 5 · 10 5 ) — изначальное число монет и количество запросов. Во второй строке даны n целых чисел a i (1 ⩽ a i ⩽ 2 · 10 9 ), где a i — номинал i-й монеты. В следующих q строках сначала задан тип запроса t (1 ⩽ t ⩽ 3) и, если запрос первого или второго типа, затем дан номинал монеты x (1 ⩽ x ⩽ 2 · 10 9 ). Типы запросов и номиналы монет — целые числа. Формат выходных данных Для каждого запроса третьего типа выведите количество счастливых монет. Система оценки Решения, работающие при n ⩽ 100, будут набирать не менее 20 процентов баллов. Решения, работающие при n ⩽ 10000, будут набирать не менее 50 процентов баллов. Пример стандартный ввод стандартный вывод 1 3 1 3 2 1 3 0 2 Замечание i-й бит побитового исключающего или чисел a и b равен 1, если и только если i-е биты чисел a и b различны. Рассмотрим «XOR» чисел 4 и 5, 4 = 100 2 , а 5 = 101 2 , так их побитовое исключающее или равно 001 2 , то есть 1 в десятичной системе счисления. Разберем пример из условия. Изначально есть только одна монета, следовательно «XOR» всех монет, кроме нее, равен 0, а следовательно счастливых монет нет. Затем добавляется еще одна монета весом 1. «XOR» множества из одной монеты равен ее весу, следовательно обе монеты счастливые. Страница 2 из 5 Высшая проба, информатика Заключительный этап, 4 февраля 2019 Задача C. Даша и сериалы Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт Даша очень любит сериалы. Недавно у Netflix вышел новый эпизод «Черного зеркала». Но это не обычный эпизод, а интерактивный. Всего в нём есть n моментов, какие-то моменты — развилки сюжета: для них существует выбор, в какой момент пойти следующим. В нашей версии гаранти- руется, что до одного финала можно добраться из начала только одним способом. Друзья Даши рассказали ей про k классных моментов. Так как Даша готовится к олимпиаде по информатике, она не хочет тратить много времени на сериалы, поэтому она уже узнала порядок моментов, а также перематывает уже просмотренные моменты. Помогите Даше найти минимальное количество моментов, которые она должна посмотреть, что- бы дойти до всех интересных моментов. Формат входных данных Первая строка содержит два целых числа n и k (2 ⩽ n ⩽ 5 · 10 5 , 1 ⩽ k ⩽ n) — количество возможных моментов и количество моментов, интересных Даше. Вторая строка содержит n − 1 целое число a i (1 ⩽ a i ⩽ i), где a i — момент, в котором надо сделать выбор, чтобы добраться до (i + 1)-го момента. Последняя строка содержит k целых чисел — индексы нужных Даше моментов. Индексы инте- ресных моментов различны. Формат выходных данных Выведите одно число — минимально возможное количество просмотренных Дашей моментов. Система оценки Программы, работающие для всех n ⩽ 20, будут набирать не менее 40 процентов от полного балла. Программы, работающие в случае a i = i, для всех i получат не менее 10 процентов от полного балла. Примеры стандартный ввод стандартный вывод 3 2 1 2 2 3 3 5 2 1 1 1 4 1 2 2 Замечание В первом тесте Даше требуется посмотреть все моменты, так как они все интересны Даше. Во втором примере Даша может не посещать 4 и 5 моменты, так как Даша может добраться до 2 момента, обойдя только 1 и 2, а до 3 — только 1 и 3. Страница 3 из 5 Высшая проба, информатика Заключительный этап, 4 февраля 2019 Задача D. Король Ночи Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт В преддверии выхода 8 сезона «Игры престолов» Глеб пересмотрел все предыдущие сезоны и так увлекся, что решил создать свою армию в борьбе против Короля Ночи. В игре престолов есть 7 королевств, но для усложнения задачи он построил свою вселенную с n королевствами, где в каждом королевстве живет по m человек. Для красоты и разнообразия он решил, что возьмет по человеку из каждого королевства и поставит их в ряд так, чтобы сумма модулей разности роста соседних в ряду людей была минимальна ( ∑ n −1 i=1 |a i − a i+1 |). Глеб не смог решить данную задачу, поэтому просит вас помочь ему. Формат входных данных В первой строке задано два натуральных числа n и m (1 ⩽ n · m ⩽ 10 5 ) — количество королевств и количество жителей в каждом королевстве. Следующие n строк описывают королевства. Каждая из этих строк содержит m натуральных чисел a i (1 ⩽ a i ⩽ 10 9 ), где a i — рост i-го человека в этом государстве. Формат выходных данных Выведите последовательность чисел длины n — рост каждого выбранного человека. Если ответов несколько, выведите ответ с минимальной суммой всех чисел. Система оценки Решения, верно работающие при n · m ⩽ 10 3 будут получать не менее 40% баллов. Примеры стандартный ввод стандартный вывод 3 2 2 2 6 7 99 1 1 2 6 2 2 9 9 6 3 9 6 Замечание Комментарий к 1 тесту: человек с ростом 1 из 3 королевства, с ростом 2 из 1, с ростом 6 из 2. Комментарий ко 2 тесту: человек с ростом 6 из 2 королевства, с ростом 9 из 1. Страница 4 из 5 Высшая проба, информатика Заключительный этап, 4 февраля 2019 Задача E. Щелчок Имя входного файла: стандартный ввод Имя выходного файла: стандартный вывод Ограничение по времени: 2 секунды Ограничение по памяти: 256 мегабайт Как вы уже знаете, Танос завладел всеми камнями бесконечности. Теперь он перешел к своему коварному плану. Изначально во вселенной было n героев, пронумерованных от 1 до n, некоторые из них были живыми, а некоторые уже погибли. Щелчок пальцами берет всех персонажей на четных позициях и либо оживляет мертвых, либо убивает живых. Как многие фанаты знают Стэн Ли является одним из богов вселенной и он решил поиграть с Таносом и дал ему q запросов двух видов. 1. Щелкнуть пальцем на отрезке с l по r. В ходе этого запроса, для всех героев с индексами вида l + 2k ⩽ r делается следующая операция: мертвые оживают, а живые умирают. 2. Найти количество все еще живых персонажей на отрезке с l по r. Формат входных данных В первой строке даны два целых числа n и m (1 ⩽ n, m ⩽ 300000) — количество героев и количество запросов Стэна Ли. В следующей строке даны n целых чисел a i , a i = 1, если персонаж жив и 0, если мертв. В следующих m строках даны три целых числа t, l, и r (1 ⩽ t ⩽ 2, 1 ⩽ l ⩽ r ⩽ n) — тип запроса и его левая и правая границы. Формат выходных данных Для каждого запроса второго типа выведите одно число — количество живых на отрезке с l по r. Пример стандартный ввод стандартный вывод 3 4 1 0 1 1 1 3 2 1 3 1 1 3 2 1 3 0 2 Страница 5 из 5 |