Задачи олимпиады "Личное первенство по программированию среди школьников и студентов ИКИТ СФУ"

Задача A. Простой шифр

Каким может быть самый простой способ зашифровать строку? Есть способы, для которых не требуется применять много усилий и обладать специальными познаниями. Одним из таких способов является простой сдвиг букв. Под сдвигом понимается замена буквы на предыдущую в алфавите. Если предыдущей буквы нет, она заменяется на последнюю букву алфавита (в этой задаче мы имеем дело с английским алфавитом).

Вам прислали секретное сообщение, зашифрованное способом, описанным выше и состоящее из строчных английских букв. Расшифруйте его и выведите.

Входные данные

Входной файл INPUT.TXT содержит строку S длиной от 1 до 100 символов, состоящую из строчных английских букв.

Выходные данные

В выходной файл OUTPUT.TXT выведите расшифрованную строку.

Пример

Задача B. Лягушка

По кругу расположены N камней, пронумерованных от 0 до N-1 в направлении по часовой стрелке. На i-ом камне написано число a_i.

Лягушка OSFrog начинает своё путешествие с камня под номером x и хочет совершить h прыжков. На j-ом прыжке (0 ≤ j ≤ h-1), находясь на i-ом камне, она прыгает на a_i камней по или против часовой стрелки. Направление определяется следующим образом: если количество единиц в двоичной записи j чётно, то она прыгает по часовой, иначе – против.

Дано M запросов с изначальным положением лягушки и количеством прыжков, которое она совершит. Определите номер камня, на котором она закончит прыжки.

Входные данные

В первой строке входного файла INPUT.TXT содержится целое число N – количество камней (1 ≤ N ≤ 2 × 10⁵). Во второй строке содержатся N целых чисел a_i, написанных на камнях (0 ≤ a_i ≤ 10⁹). В третьей строке содержится целое число M – количество запросов (1 ≤ M ≤ 2 × 10⁵). В следующих M строках содержатся запросы в виде пары чисел x_k и h_k (0 ≤ x_k ≤ N-1; 0 ≤ h_k ≤ 10⁹).

Выходные данные

В выходной файл OUTPUT.TXT для каждого запроса в отдельной строке выведите номер камня, на котором лягушка закончит путешествие.

Пример

Задача C. Электронная очередь

В отделении Битбанка используется электронная очередь. Клиенты банка, пользуясь специальным терминалом, получают талоны в зависимости от выбранной ими операции. После этого номера талонов отобразятся на информационном табло, и клиенты проходят к указанной на нём стойке. Завершив дела, клиенты оставляют талоны в специальной корзине у выхода.

Каждый талон содержит следующую информацию: уникальный идентификатор талона, время выдачи и тип операции. Уникальные идентификаторы присваиваются талонам не по порядку, при этом никакие два талона не могут иметь одинаковый идентификатор. Тип операции может быть одним из пяти вариантов: «card», «deposit», «loan», «transfer», «withdrawal». При этом клиенты по операциям «deposit» и «transfer» обслуживаются у стойки номер 1, по операциям «loan» и «withdrawal» – у стойки номер 2, а по операциям типа «card» – у стойки номер 3.

Руководство банка пригласило вас для отладки нового информационного табло. У вас в распоряжении имеется корзина с использованными талонами после рабочего дня банка, в которой все талоны беспорядочно перемешались. Требуется восстановить последовательность информационных сообщений, выводимых на табло, в порядке очереди.

Рабочий день банка начинается в 08:00 и заканчивается в 20:00. Поскольку автомат электронной очереди в отделении всего один, гарантируется, что на всех талонах указана различная метка времени.

Входные данные

В первой строке входного файла INPUT.TXT указано целое положительное число N – количество талонов в корзине (1 ≤ N ≤ 43200).

В следующих N строках содержатся описания талонов в формате «ID TIME TYPE», где ID – строка длины не более 10 символов, составленная из цифр и строчных букв английского алфавита, TIME – метка времени формата «ЧЧ:ММ:СС» в пределах рабочего дня банка: от 08:00:00 до 20:00:00, TYPE – один из возможных типов операций: «card», «deposit», «loan», «transfer», «withdrawal» (без кавычек).

Выходные данные

В выходной файл OUTPUT.TXT выведите N строк – информацию по талонам, отсортированную по возрастанию времени выдачи талона. Каждая строка должна задавать один талон и иметь следующий формат: «Ticket : counter » (без кавычек), где ID – идентификатор талона, а C – номер стойки (1, 2 или 3).

Пример

Задача D. Производная

Дан многочлен. Требуется вычислить его производную и вывести с использованием алгебраических соглашений: пусть моном – это выражение типа cx^p, где c - целое число, называемое коэффициентом, p – целое неотрицательное число, называемое показателем степени, тогда многочлен записывается как сумма мономов в соответствии со следующими правилами:

1. знак умножения между коэффициентом и x не выводится;
2. если коэффициент равен нулю, соответствующий моном не выводится;
3. если коэффициент равен единице или минус единице, при записи соответствующего монома единица не выводится;
4. если все коэффициенты равны нулю, выводится 0;
5. если показатель степени равен нулю, выводится только коэффициент;
6. если показатель степени равен единице, то единица и знак возведения в степень не выводятся;
7. если знак '+' предшествует отрицательному коэффициенту или стоит в начале выражения, знак '+' не выводится;
8. мономы выводятся строго в порядке убывания показателей степени.

Входные данные

Входной файл INPUT.TXT содержит строку длиной не более 1000 символов, описывающую многочлен. Коэффициенты многочлена целые, по модулю не превосходящие 10⁴. Показатели степени – целые неотрицательные числа, не превосходящие 10⁴. Гарантируется, что входной многочлен записан в соответствии с пунктами 1-7 правил, указанных в условии задачи.

Выходные данные

В выходной файл OUTPUT.TXT выведите производную многочлена в одну строку с использованием алгебраических соглашений.

Примеры

Примечание

Вычисление производной многочлена сводится к вычислению суммы производных каждого его члена. Производная одного члена вычисляется как производная степенной функции по формуле (cx^p)' = cpx^p-1.

Задача E. Степени двойки

Найдите количество способов разложить число n на сумму слагаемых, являющимися степенями числа 2 (1, 2, 4, 8 и т.д.).

Способы, отличающиеся порядком слагаемых, считаются одинаковыми. Каждое число в разложении можно использовать не более k раз. Так как ответ может быть слишком большим, выведите его остаток от деления на число 10⁹+7.

Входные данные

Входной файл INPUT.TXT содержит два целых числа n и k (1 ≤ n ≤ 10¹⁸; 1 ≤ k ≤ 500).

Выходные данные

В выходной файл OUTPUT.TXT выведите остаток от деления количества способов на 10⁹ + 7.

Примеры

Примечание

6 = 2 + 4

5 = 1 + 4 = 1 + 2 + 2

4 = 1 + 1 + 2 = 2 + 2 = 4

Задача F. Сыграем?

– Что имеем?

– Всего лишь два предмета:

1. Шахматная доска размера N на M, в каждой клетке которой записана цифра ноль;
2. Кубик, на каждой грани которого записана одна цифра, причём никакие две грани не содержат одинаковых цифр. Также известно, что грань кубика идеально совпадает с клеткой доски.

– А где кубик?

– Изначально кубик находится в верхнем левом углу доски.

– Что можем делать? И сколько раз?

– Всего лишь одно действие: перекатывать кубик на соседнюю клетку по горизонтали и вертикали с той, на которой кубик стоит нижней гранью. Перекатывать кубик можно бесконечное число раз!

– А цифры? При чем тут цифры?

– Когда кубик стоит на какой-то клетке, цифра с нижней грани кубика переписывается на клетку доски.

– А как победить?

– Докатив кубик до правого нижнего угла доски, добиться того, чтобы число на шахматной доске было максимальным из возможных.

– Число на шахматной доске?

– Цифры с шахматной доски переписываются в следующем порядке: сначала выписываются друг за другом слева направо цифры с первой строки доски, затем в продолжение этой же строки выписываются цифры из второй строки в том же порядке, затем из третьей и так далее. Выведите максимальное число, которое можно получить вышеописанным способом.

Входные данные

Входной файл INPUT.TXT содержит В первой строке содержатся два целых положительных числа N и M (1 ≤ N•M ≤ 10⁶, N ≤ M) - количество строк и столбцов шахматной доски соответственно.

Вторая строка содержит шесть цифр от '0' до '9', которые написаны на гранях кубика, гарантируется, что никакая цифра не встречается два раза. Порядок перечисления граней следующий: нижняя, передняя, верхняя, задняя, левая и правая.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число без ведущих нулей – ответ на задачу.

Примеры

Задача G. Вася и отрезки

Вася очень любит решать задачи на геометрию, поэтому он был очень счастлив, когда мама подарила ему на день рождения отрезок AB. Он начал с ним играть, и вскоре у него возник вопрос, можно ли найти точки D и E, которые будут лежать на равном расстоянии от точки C – середины отрезка AB, при этом отрезок DE должен быть перпендикулярен AB, проходить через точку C, а |CD|/|AB| = k.

Помогите Васе найти ответ на его вопрос.

Входные данные

Входной файл INPUT.TXT содержит координаты двух точек: A_x, A_y, B_x, B_y, k (0.01 ≤ k ≤ 1). Все координаты являются целыми числами и не превосходят 1000 по абсолютному значению, k задано не более, чем с двумя знаками после десятичной точки.

Выходные данные

В выходной файл OUTPUT.TXT выведите координаты самой высокой точки. Если обе точки находятся на одинаковой высоте, выведите координаты самой левой из них. Координаты следует выводить с абсолютной или относительной погрешностью не хуже 10^-4.

Пример

Задача H. Различные префиксы

Вася придумал задачу, в которой требовалось реализовать три операции:

1. добавить строку s в словарь (словарь может содержать одинаковые строки);
2. удалить строку s из словаря (гарантируется, что такая строка уже была ранее добавлена);
3. определить количество различных префиксов длины k.

Петя, прочитав условие, сказал, что это «баян» и многие олимпиадники знают, как решить данную задачу. Попробуйте и Вы решить её (ну или вспомнить решение).

Входные данные

Первая строка входного файла INPUT.TXT содержит целое число N – количество операций (2 ≤ N ≤ 10⁵).

В следующих N строках описаны сами операции. В начале каждой строки содержится целое число type (1 ≤ type ≤ 3), обозначающее тип операции. Если тип операции равен 1 или 2, то далее дана строка s (|s| ≤ 10⁵) состоящая из строчных английских букв, которую нужно добавить или удалить соответственно. Если тип равен 3, то далее следует одно целое число 1 ≤ k ≤ 10⁵ - длина префикса.

Гарантируется, что суммарная длина всех строк в запросах не превышает 10⁶.

Выходные данные

В выходной файл OUTPUT.TXT для каждой операции 3 типа выведите в отдельной строке количество различных префиксов длины k.

Пример

Задача I. Взрывчатка

На территории базы противника расположены N арсеналов, которые нужно уничтожить. Вы, Агент-070, имеете запас взрывчатки, достаточный для того, чтобы взорвать все N арсеналов по одному. Но при этом велик риск обнаружения.

Однако Вам известно, что при взрыве каждого арсенала создаётся взрывная волна, которая может достичь других арсеналов и спровоцировать их взрыв. Эти арсеналы тоже будут создавать свои взрывные волны. В Центре вам выдали таблицу, в которой для каждого арсенала указано, какие другие арсеналы попадут под его взрывную волну.

Так как на минирование одного арсенала требуется время, а оно очень дорого, Вам нужно заминировать как можно меньше арсеналов, чтобы, взорвав их, гарантированно уничтожить все арсеналы на базе.

Входные данные

В первой строке входного файла INPUT.TXT содержится число N – количество арсеналов на территории базы (1 ≤ N ≤ 100).

Далее дана таблица отношений: в N строках содержится по N символов, j-ый символ i-ой строки равен «1», если при взрыве i-го арсенала j-ый попадёт под его взрывную волну и «0» иначе.

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число – минимальное количество арсеналов, которое требуется заминировать для уничтожения всех арсеналов на базе.

Примеры

Задача J. Перестановка

Сегодня вам предстоит очутиться в шкуре хакера и взломать сверхсекретный компьютер потенциального противника. Система защиты у него не простая, а сортировочная.

Вам известно, что изначально в памяти компьютера хранится матрица A, которая содержит N строк и 3 столбца. А так же что компьютер может выполнять команды, состоящие из двух аргументов str1 и str2 (str1 не равно str2), по следующему алгоритму:

1. Циклически сдвинуть строку str1 на один элемент вправо;
2. Циклически сдвинуть строку str2 на один элемент вправо;
3. Поменять местами строки str1 и str2.

Для взлома компьютера вам нужно ввести такую последовательность команд, чтобы 1-й столбец матрицы был упорядочен по неубыванию, то есть A[1][1] ≤ A[2][1] ≤ ... ≤ A[N-1][1] ≤ A[N][1].

Входные данные

В первой строке входного файла INPUT.TXT содержится натуральное число N (1 ≤ N ≤ 1000). Далее следует N строк, каждая из которых содержит по три целых числа: A_i1, A_i2, A_i3 - элементы исходной матрицы (-10⁹ ≤ A_i1, A_i2, A_i3 ≤ 10⁹).

Выходные данные

Первая строка выходного файла OUTPUT.TXT должна содержать целое число M – число запросов к компьютеру (0 ≤ M ≤ 10⁴).

Далее должно идти M строк, каждая из которых описывает одну команду и должна состоять из двух различных чисел str1_i и str2_i (1 ≤ str1_i, str2_i ≤ N).

Примеры

Примечание

После циклического сдвига на один элемент вправо строка матрицы «1, 2, 3» будет иметь вид «3, 1, 2».

Задача K. Многословие

Поликарп приехал в столицу Байтландии, чтобы как следует осмотреть Байтландский Музей. В музее все экспонаты выстроены в ряд и пронумерованы от 1 до N. Он решил провести в столице Q дней. Каждый день он планирует посещать музей, просматривая отрезок экспонатов, начиная с экспоната L_k и заканчивая экспонатом R_k.

Просматривая экспонаты, Поликарп записывает свои впечатления в блокнот. Так как просмотр начинается с утра, то вначале Поликарп не многословен и записывает всего одни эпитет про первый просмотренный экспонат. Далее Поликарп чувствует прилив эмоций и записывает всё больше слов об очередном экспонате. Формально, на i-ом просмотренном экспонате Поликарп записывает i² эпитетов в описание этого экспоната в свой блокнот.

После приезда домой Поликарп решил структурировать свои записи, но их было так много, что он попросил вас написать программу, считающую количество эпитетов для каждого экспоната. Единственное, что Поликарп запомнил, это какие отрезки он посещал в музее каждый день. Эту информацию он и предоставил вам. Помогите Поликарпу, он в долгу не останется!

Входные данные

В первой строке входного файла OUTPUT.TXT содержатся два целых числа N и Q (1 ≤ N, Q ≤ 500 000). В следующих Q строках следуют параметры отрезков в виде пары чисел L_k и R_k (1 ≤ L_k, R_k ≤ N, 1 ≤ k ≤ Q).

Выходные данные

В выходной файл OUTPUT.TXT выведите N строк, в i-ой из которых должно содержаться количество эпитетов, записанных для i-го экспоната.

Пример

Задача L. Подготовка к ЕГЭ

Николай Петрович хочет, чтобы его ученики как можно лучше сдали ЕГЭ по информатике. Поэтому он специально усложняет некоторые задания, требуя, чтобы ребята предлагали решения для произвольных входных данных. Сейчас Николай Петрович изменил условие очередной задачи, которое теперь выглядит следующим образом.

Есть робот, который последовательно выполняет k операций. Каждая операция заключается или в прибавлении к x заданного целого числа a или вычитании из x заданного целого числа b. Изначально x равен 0. Требуется определить, сколько различных чисел может получить робот после k операций.

Так как Николай Петрович сомневается, не перестарался ли он в этот раз со сложностью, то решил вначале проверить, сколько людей смогут решить данную задачу на личном первенстве.

Входные данные

Входной файл INPUT.TXT содержит три целых числа k, a и b (1 ≤ k ≤ 10⁷; |a| ≤ 10⁷; |b| ≤ 10⁷).

Выходные данные

В выходной файл OUTPUT.TXT выведите одно число – ответ на задачу.

Примеры