Артем наконец написал свою дипломную работу! Теперь ее надо напечатать и отдать коммисии на проверку. Правда кризис ударил в самый неподходящий момент — бумага формата А4 для печати стала неоправданно дорогой!
Артем расстроился, ведь без бумаги ему никак не получить свой диплом. Но унывал он недолго. Артем увидел в магазине, что бумаги других форматов стоят дешевле! У него появилась гениальная идея — разрезать листы других форматов и получить А4. Он знал, что если разрезать бумагу формата А0, получится два листа формата А1, если А1, то получится два листа А2, и так далее до долгожданного А4!
В магазине ему разъяснили правила покупки бумаги — нельзя покупать бумагу разных форматов, можно выбрать только один, но в неограниченных количествах, мол, так магазин борется с кризисом.
Артем начал считать в уме, сколько ему нужно денег и какой формат лучше взять, но его одногруппники тоже попросили напечатать свои дипломные работы, поэтому ему нужна помощь!
Помогите Артему посчитать минимальную стоимость необходимой бумаги, чтобы напечатать диплом!
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^9$$$) — количество листов в дипломной работе, которую необходимо напечатать.
Следующие пять строк содержат пять целых чисел $$$A_0$$$, $$$A_1$$$, $$$A_2$$$, $$$A_3$$$, $$$A_4$$$ ($$$1 \le A_0, A_1, A_2, A_3, A_4 \le 10^9$$$) — стоимости одного листа бумаги формата A0, A1, A2, A3 и A4 соответственно.
Выведите единственное число — миниальную стоимость купленной бумаги.
10 150 80 25 20 100
75
1 10 20 30 40 50
10
Влад не любил геометрию. Ему не нравились сложные выпуклые фигуры, поэтому он пытался пропускать занятия по этому предмету.
Однажды ему все-таки пришлось посетить урок геометрии, где его тут же вызвали к доске. Учитель попросил нарисовать на доске выпуклый $$$n$$$-угольник. Влад справился с этим, хотя и не без помощи одноклассников. Далее последовал вопрос, на который Влад ответить был не готов — теперь необходимо посчитать сумму внешних углов этого $$$n$$$-угольника. «Это невозможно посчитать без компьютера!» — воскликнул Влад.
Внешним углом выпуклого многоугольника при данной вершине называется угол между первой стороной и продолжением второй стороны. Таким образом, внешний угол является смежным внутреннему, и их сумма равна $$$180^\circ$$$.
Учитель разрешил написать ему программу, считающую сумму внешних углов.
Помогите Владу реализовать решение этой задачи!
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 10^5$$$) — количество вершин многоугольника.
Следующие $$$n$$$ строк содержат по два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$-10^9 \le x_i, y_i \le 10^9$$$) — координаты $$$i$$$-й вершины многоугольника. Вершины заданы в порядке обхода по часовой стрелке.
Гарантируется, что заданный многоугольник является строго выпуклым.
Выведите единственное вещественное число — сумму внешних углов многоугольника в градусах.
Ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит $$$10^{-9}$$$.
4 1 2 4 2 6 0 2 -1
360.000000000
Графическое представление примера изображено на рисунке $$$1$$$
Рисунок 1
Влад подготовил абсолютно новый проект корпуса для Факультета Вычислительной Техники. Согласно ему, здание будет парить в воздухе, благодаря современным технологиям строительства.
Однако почти сразу же эйфорию Влада нарушили $$$n$$$ архитектурных отделов организации ПанамГорстройУправление. Каждое из них выставило установку на то, в какой зоне города можно строить объект.
Каждая из зон представляет собой Кубоид — трехмерную фигуру, у которой шесть граней, являющихся прямоугольниками.
Несмотря на недовольство, Влад обязан удовлетворить требования всех отделов, хотя зданию он хотел бы отдать как можно больше места, причем объем под строительство должен быть ненулевым.
Первая строка входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество установок.
Следующие $$$n$$$ строк содержат шесть целых чисел $$$x_1$$$, $$$y_1$$$, $$$z_1$$$, $$$x_2$$$, $$$y_2$$$, $$$z_2$$$ ($$$-10^9 \le x_1, y_1, z_1, x_2, y_2, z_2 \le 10^9$$$, $$$x_1 \lt x_2$$$, $$$y_1 \lt y_2$$$, $$$z_1 \lt z_2$$$) — описание двух углов $$$(x_1, y_1, z_1)$$$ и $$$(x_2, y_2, z_2)$$$ кубоида, внутри которого можно построить здание.
Выведите шесть чисел $$$x_s$$$, $$$y_s$$$, $$$z_s$$$, $$$x_e$$$, $$$y_e$$$, $$$z_e$$$ — описание двух углов $$$(x_s, y_s, z_s)$$$ и $$$(x_e, y_e, z_e)$$$ кубоида наибольшего объема, внутри которого можно построить здание. Учтите, что должны выполняться неравенства $$$x_s \lt x_e$$$, $$$y_s \lt y_e$$$, $$$z_s \lt z_e$$$. Выведите «PROHIBITED» (без кавычек), если невозможно построить здание, не нарушая установок.
2 0 0 0 2 2 2 1 1 1 3 3 3
1 1 1 2 2 2
3 -2 0 -1 3 4 0 -1 2 -2 2 5 0 -4 1 -1 3 3 1
-1 2 -1 2 3 0
2 -2 -2 -2 -1 -1 -1 1 1 1 2 2 2
PROHIBITED
Графическое представление первого примера изображено на рисунке $$$1$$$
Рисунок 1
Вы попали на одно поле с тиграми, которые так и хотят Вас съесть. Поле представляет собой прямоугольную таблицу $$$n \times m$$$. Некоторые клетки поля являются стенами и через них нельзя пройти.
Единственное, что Вас спасает на данный момент — все действия, Ваши и тигров, происходят пошагово. За один шаг Вы или тигр можете переместиться в соседнюю клетку вверх, вниз, влево, вправо или остаться на месте. Вы и тигры ходите по очереди. Сначала Вы совершаете один шаг, затем все тигры совершают по одному шагу.
Чтобы спастись, Вам необходимо добраться до любого края поля, не попавшись в лапы цепких тигров — именно там Вы видите телепорт в безопасное место. Тигры прекрасно Вас видят и всегда Вас преследуют. Самое главное не допустить коварного просчета, когда Вы окажетесь на одной клетке с тигром!
Формально, Вы сможете спастись, если существует маршрут к краю поля, такой что ни в один момент времени Вы и тигр не могли бы оказаться в одной ячейке. Краем поля считается любая ячейка, которая находиться на первой или последней строке поля, или на первом или последнем столбце.
Понимая безысходность ситуации, Вы пытаетесь просчитать возможный путь до любого из телепортов. Через некоторое время, известное лишь автору этой задачи, телепорты закроются, поэтому среди доступных для побега маршрутов, выбрать надо кратчайший. Есть возможность, что такого пути вообще не существует, поэтому единственным решением будет подавать сигналы $$$SOS$$$, пока Вас кто-нибудь не услышит.
Сможете ли Вы решить эту головоломку?
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 10^3$$$) — размеры поля.
Следующие $$$n$$$ строк содержат по $$$m$$$ символов: '.' обозначает пустую клетку, '#' обозначает стену, 'P' обозначает клетку, в которой вы находитесь, 'T' обозначает клетку с тигром. Гарантируется, что поле содержит ровно один символ 'P'.
Если Вы смогли решить головоломку, выведите $$$YES$$$ и отметьте маршрут на поле символами $$$P$$$. Если существует несколько маршрутов минимальной длины, по которым можно спастись, выберите любой. Если Ваши попытки оказались тщетными, выведите $$$SOS$$$.
4 5 ...T. ..#.# #.P.# .####
YES ...T. PP#.# #PP.# .####
4 5 ..T.. ..#.# #.P.# .####
SOS
3 2 T# P# ##
YES T# P# ##
3 3 T## .P# ###
SOS
После продолжительного и изнурительного рабочего дня Нурбек заснул прямо на работе, а проснулся он в совершенно неожиданном месте. Перед ним открывался красивейший вид на город, вот только спуститься на землю он не мог. На этот раз Нурбек застрял на дереве.
Если в прошлом году Артем помог Нурбеку спуститься с высокой башни, в этот раз нужно будет действовать самостоятельно — с собой не было телефона. Зато у него в руках был топор. Откуда он у него взялся — он не помнит...
Нурбек, ничего лучше не придумав, решил попробовать рубить ветки под собой, чтобы спуститься вниз. Он заметил, что на этом дереве есть по две ветки с левой и правой стороны от ствола, длиной $$$l_i$$$ и $$$r_i$$$ соответственно. Эти ветки встречаются каждый метр $$$n$$$—метрового дерева, падать достаточно невысоко. Таким образом, Нурбек может совершать три возможные действия — перепрыгнуть на правую ветку 'R', перепрыгнуть на левую ветку 'L' или срубить ветку под собой 'S'. Изначально Нурбек сидит на левой ветке.
Нурбеку очень жалко бедное дерево, но придется рубить ветки. Помогите минимизировать ущерб дереву, срубив наименьшую сумму длин веток при спуске Нурбека на землю. Кроме того, Нурбек не хочет сидеть на дереве слишком долго. Если существует несколько способов минимизировать ущерб дереву, Нурбек хочет сделать это за минимальное количество действий.
Первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — размер дерева в метрах.
Следующие $$$n$$$ строк содержат два числа $$$l_i$$$ и $$$r_i$$$ ($$$1 \le l_i, r_i \le 10^9$$$) — длина левой и правой ветки на высоте $$$i$$$ метров соответственно.
Выведите строку из символов 'L', 'R' и 'S', которая покажет такой алгоритм действий Нурбека, при котором можно минимизировать ущерб дереву. Если таких строк несколько, выберите среди них любую строку с минимальным количеством действий.
5 1 3 4 8 9 1 3 3 7 5
RSSSLSS
В первом примере Нурбек сначала перепрыгнет на правую ветку. Затем срубит правые ветки длиной $$$5$$$, $$$3$$$ и $$$1$$$ метр. На высоте два метра от земли Нурбек перепрыгнет на левую ветку и срубит оставшиеся ветки длинной $$$4$$$ и $$$1$$$ метр.
Четыре друга, Артём, Юджин, Евгений и Влад, решили сыграть партию в шахматы. Как мы знаем, вчетвером в обычные шахматы сыграть нельзя, поэтому компания решила сыграть партию в «Безумные шахматы».
Смысл игры прост — игроки делятся на пары и играют в обычные шахматы, но с одним условием. Фигуры, выигранные вашим союзником, передаются вам. Чтобы их выставить на поле, необходимо потратить ход. Эти фигуры можно размещать в любом месте на доске.
Друзья разделились на пары. Юджин играет против Евгения в одной команде с Владом, а Артем играет против Влада в одной команде с Евгением.
Влад безумно хорош в шахматах, поэтому он уже победил Артема и передал все его фигуры Юджину. Теперь перед Юджином стоит задача победить своего противника. Для этого необходимо обменять все фигуры Евгения. Обмен фигур возможен, только если сила фигуры Юджина превосходит силу фигуры Евгения на $$$D$$$ или более.
Помогите Юджину победить Евгения за минимальное количество ходов. За один ход Юджин может обменять одну свою фигуру на фигуру оппонента или выставить одну из фигур Артёма.
Да начнется шахматное безумие!
Первая строка входных данных содержит четыре целых числа $$$n$$$, $$$m$$$, $$$k$$$ и $$$D$$$ ($$$1 \le n, m, k \le 10^5, 1 \le D \le 10^9$$$) — количество фигур у Юджина, количество фигур у Евгения, количество фигур у Артёма и количество очков $$$D$$$.
Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$) — сила фигур Юджина.
Третья строка содержит $$$m$$$ целых чисел $$$b_i$$$ ($$$1 \le b_i \le 10^9$$$) — сила фигур Евгения.
Четвертая строка входных данных содержит $$$k$$$ целых чисел $$$c_i$$$ ($$$1 \le c_i \le 10^9$$$) — сила фигур Артёма.
Выведите единственное число — минимальное количество ходов, которое нужно сделать Юджину, чтобы победить Евгения. Если Юджин не может победить, выведите $$$-1$$$.
3 4 2 3 5 4 12 14 1 2 8 6 17
5
3 1 2 1 5 7 5 8 3 2
-1
Антон решил создать свою тестирующую систему, так как та, которая использовалась на соревнованиях в его школе, ему категорически не нравилась. И всё шло хорошо, пока не настал черёд подсистемы аутентификации пользователей.
Для реализации этой системы, ему нужно найти способ хэшировать пароли пользователей, так как реальные пароли в Базе Данных хранить нельзя.
Для хэширования какой-либо строки $$$s$$$, Антон решил использовать составной хэш - два числа: длина строки $$$n=|s|$$$, и сумма кодов символов $$$h=\sum_{i=1}^n ord(s_i)$$$. Однако в своей системе для использования в паролях он решил разрешить лишь строчные латинские буквы, для которых кодом будет являться их позиция в алфавите. Так, для строки $$$abacaba$$$, он запомнит числа $$$n=7$$$ и $$$h=11=1+2+1+3+1+2+1$$$.
Однако теперь его друг Марат, воспользовавшись информацией о том, как Антон спроектировал свою систему, хочет подобрать пароль-коллизию для того, чтобы незаметно проникать в систему с правами администратора.
Коллизией называется явление, при котором несколько различных по содержимому данных имеют одинаковое значение хэш-функции. Например, для строки $$$abacaba$$$ коллизией может являться строка $$$abbabba$$$, потому что их длины совпадают так же, как и их суммы кодов символов.
Марат уже завладел информацией о том, каким паролем пользуется Антон. Помогите ему найти коллизию
Первая строка входных данных содержит строку $$$s$$$ $$$(1 \le |s| \le 10^5)$$$, состоящую из строчных латинских букв — пароль, используемый Антоном для администрирования его тестирующей системы
В первой строке выведите число $$$h$$$, которое будет получено при хэшировании пароля Антона. Во второй строке выведите сгенерированный пароль-коллизию. В случае, если такого пароля не существует, оставьте вторую строку пустой
admin
41 xcede
abacaba
11 abbabba
Городок Еловый славится своими двумя вещами — здесь каждую неделю Новый год и везде очень узкие дороги. Если с первым еще можно как-то бороться, то со вторым городу очень тяжело. Именно поэтому жителям нужна Ваша помощь!
Вам дана карта города Еловый. Как ни странно, он очень похож по форме на елку. Елью в данной задаче будем называть неориентированный граф, состоящий из цикла, к которому присоединён черенок, представляющий собой несколько последовательно связанных рёбер. Самую отдалённую от цикла вершину черенка будем называть корнем ели. В корне находится выезд из города. На некоторых улицах города с последнего Нового года лежат ёлки, которые надо вывезти из города.
Необходимо помочь уборочной машине убрать все елки из городка, пока не наступил Новый год! Ведь начинать новую неделю Нового года со старой елкой является плохой приметой в этом городе. Вы можете выбрать любую вершину графа в качестве стартовой точки, но главным условием является закончить сбор елок на выезде из города, иначе елки вывезти не удастся, ведь разворачиваться на узкой дороге нельзя, не правда ли? Так же, вы не можете посещать одну вершину несколько раз — мэр города, который построил такие дороги точно уверен, что есть более оптимальный маршрут для сбора елок!
Елки ждут!
Первая строка входных данных содержит одно целое число $$$n$$$ ($$$4 \le n \le 10^3$$$) — количество вершин в ёлке.
Во второй строке входных данных содержится $$$n$$$ целых чисел $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$) — количество ёлок в каждой вершине.
В следующих $$$n$$$ строках содержится по два целых числа $$$v$$$, $$$u$$$ ($$$1 \le v, u, \le n, v \ne u$$$), описывающих ребро между вершинами $$$v$$$ и $$$u$$$. Между каждой парой вершин существует не более одного ребра.
Гарантируется, что рёбра задают ёлку — граф, состоящий из цикла, к которому присоединены несколько последовательно связанных рёбер.
Выведите длину кратчайшего пути, пройдя по которому, можно собрать все ёлки.
5 0 0 0 0 18 1 2 2 3 3 4 4 5 5 2
2
4 3 1 6 3 4 1 1 2 2 4 2 3
3
Графическое представление примера показано на рисунке $$$1$$$.
Рисунок 1
Витя в прошлом году просил вас узнать, успеет ли он на пару, если будет стоять в очереди за вкуснейшей булочкой с маком. Теперь условия несколько изменились — в университете открылось целых два буфета, в которых есть лучшая в мире булочка с маком!
Помогите Вите узнать, в каком буфете он получит булочку быстрее, чтобы насладиться ей!
Первая строка входных данных содержит четыре целых числа $$$x$$$, $$$n$$$, $$$y$$$ и $$$m$$$ ($$$0 \le x, y \le 100, 1 \le n, m \le 100$$$) — количество человек в очереди в первом буфете, время обслуживание одного человека в первом буфете, количество человек в очереди во втором буфете и время обслуживания одного человека во втором буфете соответственно.
Выведите номер буфета ($$$1$$$ или $$$2$$$), в котором можно быстрее получить булочку с корицей. Первый буфет Вите нравится больше, поэтому если не имеет значения, какой буфет выбрать, выведите $$$1$$$.
6 3 3 5
2
1 2 0 6
1
3 4 3 4
1