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

Задача A. Переполох у турникетов

Чтобы пройти в ИКИТ, нужно позволить охране осмотреть вещи, с которыми вы приходите. В день олимпиады пришло p человек с портфелями и b с сумками. Чтобы проверить портфель, охране требуется t_p секунд, а чтобы проверить сумку – t_b секунд.

Сколько секунд охранникам понадобится на проверку всех вещей?

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

Во входном файле INPUT.TXT записаны четыре числа, разделенных пробелами. Первые два числа p и b – количество участников с портфелями и сумками соответственно . Вторые два числа t_p и t_b – количество секунд для проверки портфеля и сумки соответственно. (0 ≤ p, b, t_p, t_b ≤ 1000)

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

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

Примеры

Задача B. Поездка в кино

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

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

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

Получилось так, что всего в кинотеатр поехало n человек, все они стоят в ряд и только им осталось заплатить за проезд. Для удобства пронумеруем ребят натуральными числами от 1 до n слева направо. Известно, что Петя имеет номер k, также известно, что слева от Пети p человек с картой, a справа — q, сам же мальчик платит за проезд наличными.

Зная эту информацию, помогите Пете найти ответ на его вопрос.

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

Входной файл INPUT.TXT содержит четыре целых числа n, k, p, q (1 ≤ n ≤ 10⁹; 1 ≤ k ≤ n; 0 ≤ p < k; 0 ≤ q ≤ n − k) — количество человек, которые поехали в кинотеатр, номер Пети, количество человек с картой левее Пети и количество человек с картой правее Пети, соответственно.

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

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

Примеры

Задача C. Баобаб

«Элементарными называются такие истины, которые человек открывает последними.»
(с) Альбер Камю

Одним осенним вечером Егор прогуливался по ботанической оранжерее Мебибайтного Гибибайтного Универститета. Он повстречал на своём пути недавно открытое особенное дерево – баобаб. Он сразу заметил несколько свойств этого чудесного дерева и сформулировал важную для дальнейших исследований задачу.

Формально, вам дан неориентированный взвешенный граф без кратных ребер и петель, который называется баобабом. Баобаб представляет из себя один или более простых путей, имеющих общее начало в вершине 1 и общий конец в вершине n. Других общих вершин ни у каких двух путей нет. Каждый такой путь состоит из двух или более вершин. Каждое ребро описывается тремя числами u, v и c, которые обозначают ребро весом c между вершинами u и v.

Вам нужно ответить на q запросов — найти минимальный по весу путь от одной вершины до другой. Помогите Егору решить эту непростую задачу!

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

В первой строке входного файла INPUT.TXT записано три целых числа n, m и q (2 ≤ n ≤ 10⁵; 1 ≤ m < 2×10⁵; 1 ≤ q ≤ 2×10⁵) — количество вершин, ребер и запросов.

В следующих m строках записано по три целых числа u, v, c (1 ≤ u, v ≤ n; 1 ≤ c ≤ 10⁹), описывающие ребра графа.

В следующих q строках записано по два числа x, y (1 ≤ x, y ≤ n), задающие очередной запрос

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

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

Пример

№	INPUT.TXT	OUTPUT.TXT	Пояснение
1	8 9 5 1 2 2 2 3 2 3 4 1 4 8 1 1 5 3 5 6 1 6 8 1 1 7 2 7 8 1 4 7 2 5 4 1 1 8 2 4	2 5 4 3 3

Задача D. Очистка террасы

«Упади семь раз и восемь раз поднимись»
(с) Японская мудрость

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

Пол выстелен из n × m одинаковых квадратных плиток. Поликарп может поставить робота-пылесоса на любую из этих плиток и включить его. После включения робот в каждый свой шаг может совершить одно из нескольких действий:

1. Повернуться на 90^◦ влево и потратить a единиц энергии.
2. Повернуться на 90^◦ вправо и потратить b единиц энергии.
3. Переместиться в клетку, находящуюся перед ним (не выходя при этом за границы террасы), и потратить c единиц энергии.

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

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

Входной файл INPUT.TXT содержит пять целых чисел n, m, a, b и c (1 ≤ n, m ≤ 10⁶; 0 ≤ a, b, c ≤ 10⁶).

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

В выходной файл OUTPUT.TXT выведите одно число — ответ на поставленную задачу, выраженный в единицах энергии из условия.

Примеры

Задача E. Битва школ

Всем известно, что самая интересная часть Всероссийской Командной Олимпиады Школьников по Программированию – это «Битва школ». Ежегодно лучшие школьники сражаются за право называть свою школу самой сильной.

Рейтинг школ в этом мероприятии основывается на сумме баллов трёх её лучших участников (по количеству набранных баллов). Если у школы нет трёх участников, то она не участвует в рейтинге.

Организаторы олимпиады написали программу, которая зная результаты олимпиады, выводит рейтинг для «Битвы школ». А сможете ли вы написать такую программу?

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

В первой строке входного файла INPUT.TXT находится целое число n (1 ≤ n ≤ 1000) — количество участников олимпиады.

В следующих n строках находятся результаты участников в формате «l_i p_i s_i», где:

l_i — логин участника, строка, длина которой от 1 до 10 символов.

p_i — количество баллов участника, задающееся целым числом (0 ≤ p_i ≤ 10000).

s_i — название школы участника, строка, длина которой от 1 до 100 символов.

Логины и названия школ состоят из символов с ASCII-кодами от 33 до 127.

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

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

Пример

Задача F. Этажи

К 4096 году земное притяжение перестало существовать и земляне стали жить в многоэтажных космических кораблях. На каждом этаже такого корабля располагается единственная квартира. У каждой квартиры есть номер.

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

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

Программы для роботов-строителей писали неопытные программисты, поэтому от вас требуется проконтролировать процесс строительства одного такого корабля.

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

Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 10⁵) — количество действий роботов-строителей.

Следующие n строк описывают эти действия — каждая строка содержит знак «+» или «-» (обозначающий добавление или удаление этажа соответственно) и слово «top» или «bottom» (обозначающее, что этаж достраивается сверху или снизу соответственно), разделённые пробелом.

В случае добавления, через пробел также записано целое число k (1 ≤ k ≤ 10⁹) — номер квартиры в достраиваемом этаже.

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

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

В выходной файл OUTPUT.TXT выведите n строк. В i-й строке выведите YES, если после последовательного выполнения первых i действий корабль находится в корректном состоянии, иначе выведите NO.

Примеры

Задача G. Космическое сновидение

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

Во сне девочка увидела систему из планет и чёрных дыр, местоположение которых можно представить на оси Ox. Как известно, чёрные дыры могут поглощать другие космические тела, в данной системе это свойство также сохраняется, причём каждая чёрная дыра действует на расстояние w_i и имеет мощность p_i. Пусть d − расстояние между планетой и чёрной дырой, равное модулю разности их координат. Чёрная дыра будет оказывать воздействие на эту планету только в том случае, если d ≤ w_i, при этом она будет поглощать планету с силой p_i - d. Может оказаться так, что на планету воздействует несколько чёрных дыр, в таком случае считается, что планета будет поглощена той чёрной дырой, которая действует на неё с наибольшей силой, при наличии нескольких таких чёрных дыр, планета может быть поглощена любой из них, в таком случае считается, что заранее предсказать исход невозможно.

Аня недавно начала заниматься олимпиадным программированием, поэтому, когда она проснулась, она захотела узнать для каждой планеты, какая чёрная дыра её поглотит.

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

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

Первая строка входного файла INPUT.TXT содержит число n (1 ≤ n ≤ 2·10⁵) − количество небесных тел. Каждая из следующих n строк содержит информацию об очередном небесном теле:

• планета задаётся в формате «1 x_i», где x_i − координата i-й планеты (-10⁹ ≤ x_i ≤ 10⁹).
• чёрная дыра описывается в формате «2 x_j p_j w_j», где параметрам соответствуют − координата j-й черной дыры, мощность и дальность её воздействия (-10⁹ ≤ x_j ≤ 10⁹; 1 ≤ w_j < p_j ≤ 2·10⁹).

Все числа во входных данных являются целыми. Гарантируется, что существует хотя бы одна планета и в каждой точке может находиться не более чем один космический объект.

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

В первой строке выходного файла OUTPUT.TXT выведите одно число k − количество планет во входных данных.

Во второй строке выведите k чисел, разделённых пробелами, где каждое число обозначает номер чёрной дыры, которая поглотит очередную планету, или же -1, если планете ничего не угрожает. Если подходящих чёрных дыр несколько, то разрешается вывести номер любой из них.

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

Примеры

№	INPUT.TXT	OUTPUT.TXT	Пояснение
1	5 1 4 2 2 6 3 2 -1 10 5 1 5 1 -4	3 2 1 2
2	4 1 3 2 6 4 3 2 1 3 2 1 -2	2 1 -1

Задача H. Неумолкающий Янпул

Ян — большой любитель поговорить. Он хочет сказать Давиду что-то очень важное. Известно, что Давид готов слушать Яна в течение следующих n минут. Яну нужно ровно t минут, чтобы высказать все, что он думает. Он также знает, что если заговорит в минуту i, то потратит энергию равную величине b_i, а Давид будет раздражаться на величину a_i. Обратите внимание, что если в минуту i Ян молчит, то он не тратит энергию, а Давид не раздражается.

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

Их знакомый перспективный олимпиадник Егор очень хочет помочь им в этом. Но у него куча дел! К тому же, вот-вот начнется ВКОШП 2019 Восточно-Сибирского региона, который Егор никак не может пропустить. Взвесив все за и против, Егор поручает эту задачу вам.

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

Первая строка входного файла INPUT.TXT содержит два целых числа n и t — количество минут, в течение которых Давид готов слушать Яна, и сколько минут нужно Яну, чтобы высказать Давиду все, что он думает (1 ≤ t ≤ n ≤ 10⁵).

Следующие n строк содержат по два целых числа a_i и b_i (0 ≤ a_i, b_i ≤ 10⁹) — величина раздражения Давида, и потраченная энергия Яна, если Ян заговорит в минуту i (1 ≤ i ≤ n).

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

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

Пример

Задача I. ЦПСП

Министерство образования великой страны N планирует открыть Центр Подготовки Спортивных Программистов в одном из своих городов. Города страны пронумерованы целыми числами от 1 до n и соединены друг с другом n-1 трассой, между любыми двумя городами существует путь по трассам. На каждой трассе разрешено движение в обе стороны.

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

Некоторые города в стране являются тупиковыми — те, которые соединены трассой только с одним городом. Министерство образования запретило строить Центр в тех и только в тех городах, которые соединены трассой хотя бы с одним тупиковым городом, ведь школьники из тупикового города не смогут совершить переезд для поступления, а близость тупиковых детей будет негативно влиять на работу Центра.

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

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

В первой строке входного файла INPUT.TXT записано целое число n (1 ≤ n ≤ 10⁵) — количество городов в стране. В каждой из следующих n−1 строк записаны по два целых числа x_i и y_i (1 ≤ x_i, y_i ≤ n; x_i ≠ y_i), означающие, что города с этими номерами соединены трассой. В последней строке через пробел записано n целых чисел a_i — количество школьников из i-го города, интересующихся олимпиадами по программированию (1 ≤ a_i ≤ 10⁶).

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

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

Примеры

Задача J. Стреляй!

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

Игра проходит на бесконечном экране, состоящем из клеток. Утка находится в определенной клетке, которая неизвестна игроку.

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

После выстрела вы не узнаете клетку, куда перелетела утка, но узнаете ее смещение по каждой оси. Ваша задача выиграть, но на это вам дается не более 50 выстрелов.

Протокол взаимодействия

Каждый выстрел нужно выводить в отдельной строке в виде двух целых чисел i и j через пробел, означающих номер строки и столбца соответственно. Несмотря на то, что поле игры бесконечное, координаты выстрела не должны превышать 10⁹ по абсолютному значению.

После каждого вашего выстрела на ввод подаются два целых числа d_i и d_j, означающие изменение строки и столбца координат утки соответственно.

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

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

Пример

Примечание

Для корректной работы программы после каждой операции вывода данных выводите перевод строки, а также очищайте буфер вывода. Очистка буфера вывода производится следующим образом:

• В языке Pascal: flush(output)
• В С/С++: fflush(stdout) или cout.flush()
• В Java: System.out.flush()
• В Python: sys.stdout.flush() из библиотеки sys
• В C# и Basic: Console.Out.Flush()

Задача K. Отряд Стёпы

«Опасность мудрого в том, что он больше всех подвержен соблазну влюбиться в неразумное»
(с) Фридрих Ницше

Но сейчас перейдем к насущной проблеме материального мира. Когда на улице светило солнце, Ян не опоздал, Бизон не проспал, а Давид обновил всю бухгалтерию, дружная компания под названием «Отряд Стёпы», которую возглавлял тот самый Степан, отправилась в один небезызвестный заповедник.

Похождения их продолжались до ночи, и Стёпа потерялся в лесу. Благо он имел с собой фонарик, который испускает свет в виде параболы, которая задана уравнением y = kx². Чтобы найти выход, Стёпе нужно навести фонарик на указатель, расположенный в точке (x, y), если считать, что сам Стёпа находится в точке (0, 0).

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

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

Единственная строка входного файла INPUT.TXT содержит три целых числа x, y и k (-1000 ≤ x, y ≤ 1000; 1 ≤ k ≤ 100) — координаты точки, в которую Стёпе нужно навести фонарик и коэффициент уравнения параболы, которая описывает, как испускается свет.

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

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

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

Примеры

Пояснение к примерам

Пример №1	Пример №2	Пример №3

Задача L. Swap optimization

«Задача почти ни о чём, на фиг ей легенда?»
(с) Андрей Титов

Даны три различных целых числа: a, b, c. Необходимо переставить их местами так, чтобы они стали упорядоченными по неубыванию. Выясните минимальное количество необходимых обменов.

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

Входной файл INPUT.TXT содержит целые числа a, b и c, каждое из которых по модулю не превосходит 100.

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

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

Примеры