Полуфинал XIX Всероссийской командной олимпиады школьников по программированию (Восточно-Сибирский регион)

Задача A. Книги

На полке в ряд стоят N книг, по W листов каждая (как на фотографии). Книги пронумерованы слева направо начиная с единицы. Книжный червь Костян решил ползти слева направо, сгрызая все листы на своём пути, пока не встретит первый лист K-й книги, который грызть он не собирается.

Сколько листов прогрызёт герой этой задачи?

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

Входной файл INPUT.TXT содержит три целых числа N, W и K (1 ≤ N, W ≤ 10³; 1 ≤ K ≤ N).

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

В выходной файл OUTPUT.TXT выведите единственное число – количество листов, которые прогрызёт Костян.

Пример

Задача B. Рейд-Босс

В одной компьютерной RPG-игре проходит ивент, на который собралось N игроков. Каждый из них имеет одного персонажа с уровнем L_i, являющимся целым числом.

Для того, чтобы начать бой с рейд-боссом, уровень каждого игрока должен являться точной D-степенью. Число A является точной D-степенью, если A=X^D для некоторого целого X.

К счастью, во внутриигровом магазине продаются зелья изменения уровней. Зелье объёма S стоит S монет, где S – любое целое положительное число. Игрок может применить зелье на персонажа и, по своему усмотрению, уровень станет либо в S раз больше, либо в S раз меньше. При этом второй случай допустим только если уровень персонажа на момент принятия зелья делится на S.

Зелье каждого объёма находится в неограниченном количестве. Игрок до начала боя может применить на персонажа сколько угодно зелий.

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

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

Первая строка входного файла INPUT.TXT содержит два целых числа: N – количество игроков (1 ≤ N ≤ 10⁵) и D – требуемую степень (0 ≤ D ≤ 10⁹).

Во второй строке содержатся N целых чисел L_i, разделённых пробелом (1 ≤ L_i ≤ 10⁶).

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

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

Пример

Задача C. Сапёр

Однажды Ромка поспорил с Виталькой, что сможет выиграть в игру Сапёр быстрее, чем за 5 секунд. Напомним, что в данной игре предлагается разминировать поле N×M клеток, в котором расположены мины. Когда игрок открывает какую-то клетку, он может увидеть в ней цифру, равную количеству мин в соседних клетках, саму мину или пустую клетку. В последнем случае соседние клетки открываются по таким же правилам. Клетки считаются соседними, если они имеют общую сторону или угол.

Виталька не доверяет компьютерам, поэтому сам нарисовал поле и расставил мины. А так как Виталька ещё и не умеет программировать, он просит вас написать программу, выводящую поле после первого хода Ромки.

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

Первая строка входного файла INPUT.TXT содержит целые числа N и M (10 ≤ N, M ≤ 100) – размеры игрового поля.

Следующие N строк содержат по M символов, описывающих поле: пустая клетка обозначается символом «.», а мина символом «*».

В последней строке заданы x и y – координаты первого хода (1 ≤ x ≤ N, 1 ≤ y ≤ M).

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

В выходной файл OUTPUT.TXT выведите поле после первого хода. Для обозначения мин и пустых клеток всё также используйте символы «*» и «.», соответственно. Для не открывшихся ячеек используйте символ «?». Для обозначения количества соседних мин, если они есть, используйте цифры от 1 до 8.

Примеры

Задача D. Стоунхендж 2077

«Крoмлех – древнее сооружение, как правило, позднего неолита или раннего бронзового века,
представляющее собой несколько поставленных вертикально в землю продолговатых камней,
образующих одну или несколько концентрических окружностей.»
(Материал из Википедии – свободной энциклопедии)

В будущем 2077-м году миру откроется заповедник «Стоунхендж 2077» – продвинутая версия легендарной английской достопримечательности. Он будет представлять из себя n камней, расположенных по кругу и образующих правильный n-угольник. Камни пронумерованы от 1 до n по часовой стрелке, если смотреть на конструкцию сверху.

Уже сейчас администрация заповедника планирует открытие первого туристического сезона. Планируется проведение экскурсий внутри заповедника. Каждая экскурсия будет соединять два различных камня. Между этими двумя камнями будет проложена прямая дорога, по которой будут ходить люди.

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

• «link a b» – запрос на создание экскурсии между камнями a и b (1 ≤ a, b ≤ n; a ≠ b). Если возможно создать такую экскурсию, то создать её и сообщить администрации её порядковый номер. Номера выдаются в порядке создания экскурсий, начиная с единицы. Если же создание невозможно из-за пересечения с какими-либо уже существующими экскурсиями – сообщить об ошибке и не создавать.
• «cut k» – запрос на отмену экскурсии с порядковым номером k. Гарантируется, что на момент запроса экскурсия с таким номером существует в программе заповедника.

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

В первой строке входного файла INPUT.TXT содержатся два целых числа n – количество камней, и m – количество команд (3 ≤ n ≤ 10⁹; 1 ≤ m ≤ 3×10⁵). В следующих m строках содержатся команды в формате, описанном выше.

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

В выходной файл OUTPUT.TXT для каждой операции первого типа в отдельной строке выведите «added as k», где k – номер экскурсии, если её можно проводить в данный момент, и «error», если невозможно.

Пример

Задача E. Новый будильник

Как-то раз Саша решил завести напоминание на своём телефоне. Он зашёл в приложение, отвечающее за время и обнаружил, что там уже есть N ранее установленных будильников. Его заинтересовал вопрос: за какое наименьшее количество действий он сможет выставить новый будильник?

Саша может совершать любое из следующих действий:

• создать будильник на время 00:00;
• увеличить или уменьшить время в любом будильнике на один час. При уменьшении 0-го часа, он переходит в 23-й, и наоборот, при увеличении 23-го, он переходит в 0-й;
• увеличить или уменьшить время в любом будильнике на одну минуту. Аналогично часам ведут себя 0-я и 59-я минуты.

Заметим, что изменение минут в будильнике не влияет на изменение часов так же, как и изменение часов не влияет на изменение минут.

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

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

Первая строка входного файла INPUT.TXT содержит целое число N – количество ранее установленных будильников (1 ≤ N ≤ 100). В каждой из следующих N строк содержится время очередного будильника. В последней строке задано время напоминания, которое хочет установить Саша. Каждое время задаётся в формате hh:mm. Минуты заданы от 0 до 59, часы от 0 до 23.

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

В выходной файл OUTPUT.TXT выведите минимальное количество действий.

Пример

Задача F. Тепло

Вы сидите в холодной волшебной избе, в которой находится волшебная печь. Рядом с вами расположены N волшебных камней, на i-м камне высечено целое число A_i.

Камни можно кидать в печь, но особым образом – по два камня. Иначе произойдёт непоправимое. Не будем вдаваться в подробности, так написано в инструкции. После броска в печь камень нельзя использовать повторно.

После того как в печь будет кинута пара камней, на которых написаны числа X и Y, к температуре в избе добавится X×Y градусов. Изначально температура равна нулю.

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

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

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

Вторая строка содержит N целых чисел A_i, разделённых пробелами (|A_i | ≤ 10⁹).

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

В первой строке выходного файла OUTPUT.TXT выведите целое число M – количество пар камней в найденном вами способе получения максимальной температуры.

В следующих M строках выведите по два числа, записанных на очередной паре камней.

Если вариантов ответа несколько, разрешается вывести любой из них.

Пример

Задача G. Очень длинный корень

Маленький Виталик только начал заниматься олимпиадным программированием. Так как он ещё не знает алгоритмов, то решил начать c задач, в которых они не требуются.

Сегодня ему попалась задача, в которой нужно вычислить целочисленный корень из длинного целого числа N, то есть необходимо найти максимальное целое X такое, что X² ≤ N.

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

Виталик понял, что не умеет вычислять размер массива, в который запишет ответ, и просит вас о помощи.

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

Входной файл INPUT.TXT содержит целое число N (1 ≤ N ≤ 10¹⁰⁰⁰⁰⁰).

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

В выходной файл OUTPUT.TXT выведите длину требуемого массива.

Пример

Задача H. Плохой хеш

Вам знакомо понятие хеширования? Это способ представления какого-либо объекта в виде целого числа – хеша. Одинаковые объекты должны иметь одинаковый хеш, а вот разные не обязательно: их хеш может совпадать. Но чем чаще такое происходит, тем хуже метод хеширования.

Маша придумала свой способ хеширования целых чисел: за хеш числа X она принимает S(X) – сумму всех циклических сдвигов числа X.

Например, S(47) = 47 + 74 = 121, а S(9090) = 9090 + 909 + 9090 + 909 = 19998.

Ваша задача – взломать хеш: для данного H найти количество таких X, что S(X) = H.

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

Первая строка входного файла INPUT.TXT содержит целое число T – количество тестов (1 ≤ T ≤ 50).

Следующие T строк содержат по одному целому числу H (1 ≤ H ≤ 10¹⁸).

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

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

Пример

Задача I. Максимальное число

Думаете, числам не могут сниться сны? Ещё как могут, да и к тому же коллективные!

Вот и сейчас целым числам с отрезка [L, R] снится, как они попали в зазеркалье. При этом каждое число в таком сне становится перевёрнутым. Например, 8273682736 становится 6372863728, а 1774017740 становится 47714771.

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

Окажите услугу, определите это число как можно скорее.

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

Входной файл INPUT.TXT содержит два целых числа: в первой строке число L, во второй – R (0 < L ≤ R < 10¹⁰⁰).

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

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

Примеры

Задача J. Дроны фермера Джона

Фермер Джон решил освоить современные технологии и приобрёл двух дронов-поливальщиков. Дрон может поливать участок поля, являющийся квадратом. Первому дрону Джон установил полить удобрениями квадрат со стороной A, второму – со стороной B.

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

Но что-то пошло не так, и второй дрон полил участок не там, где ему было указано. Он полил квадрат, центр которого совпадает с центром участка первого дрона, и при этом второй квадрат повёрнут на 45 градусов относительно первого.

Теперь Джону интересно, всё ли так плохо, как кажется? Посчитайте площадь поля, удобренную хотя бы одним дроном.

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

Единственная строка входного файла INPUT.TXT содержит два целых числа A и B (1 ≤ A, B ≤ 10⁴).

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

В выходной файл OUTPUT.TXT выведите площадь, политую дронами с абсолютной или относительной погрешностью, не превосходящей 10^-6.

Примеры

№	INPUT.TXT	OUTPUT.TXT	Пояснение
1	2 2	4.6862915
2	3 1	9