Астронавты выполняют сложный трюк в космосе в рамках сверхсекретной миссии по заказу управления сверхсекретными миссиями Галактической Федерации. Каждый из них имеет две руки и держится каждой из них независимо за ногу другого астронавта. Астронавт может держаться за двух разных астронавтов, обеими руками за одного, но не может держаться за свои ноги. При этом за ноги одного астронавта может держаться сколько угодно других.
Внезапно в момент времени 0 из ниоткуда возникает Сверхмассивная Черная Дыра и поглощает астронавта с номером S. Каждую следующую секунду Дыра поглощает максимальное по включению множество не поглощённых ранее астронавтов, каждый из которых:
- обязательно держался хотя бы за одного астронавта, поглощённого ранее (на предыдущих секундах);
- может держаться за астронавтов из поглощаемого в данную секунду множества;
- не держится за остальных астронавтов.
Когда Дыра не может никого больше поглотить, она схлопывается и оставшиеся астронавты остаются невредимыми.
Для каждого астронавта необходимо определить, будет ли он поглощён Сверхмассивной Черной Дырой в процессе выполнения миссии и, если да, то в какой момент времени.
В первой строке задано количество астронавтов N (2 ≤ N ≤ 105) и номер астронавта S (1 ≤ S ≤ N), поглощаемого в момент времени 0.
В следующих N строках записаны пары чисел Li и Ri (1 ≤ Li, Ri ≤ N) — номера астронавтов, за которых астронавт номер i держится своей левой и правой руками соответственно.
Выведите N чисел Ti, каждое из которых будет соответствовать моменту времени, когда астронавт под номером i будет поглощён Дырой, или равняться - 1, если он останется невредим.
7 1
2 7
1 1
2 4
2 3
4 6
4 7
5 1
0 1 2 2 3 3 3
7 1
2 7
1 1
2 4
2 3
4 6
7 7
5 1
0 1 2 2 -1 -1 -1
3 1
2 3
1 1
1 2
0 1 1
У земного космического агентства есть традиция: каждое утро для экипажа космического корабля, находящегося на орбите, с Земли по спутниковой связи транслируют один или несколько музыкальных фрагментов. Однако, в последнее время астронавты стали жаловаться, что транслируемая музыка плохо сочетается с космосом. Поэтому агенство решило нанять популярную в Галактической Федерации рок-группу Abuse специально для сочинения космической музыки.
Музыканты долго трудились и выпустили композицию «Гипермузыка». Но, как часто бывает, заказчик остался недоволен результатом. Музыкальные эксперты космического агенства обнаружили, что в нотной записи композиции совершенно отсутствуют паузы, а сумма длительностей нот в такте не везде равна размеру такта. Музыканты объяснили это тем, что такова задумка, так как космос у них ассоциируется с беспрерывностью и бесконечностью. Но заказчик всегда прав, поэтому необходимо помочь группе добавить в такты минимальное количество пауз так, чтобы сумма длительностей нот и пауз в каждом такте была равна размеру такта.
Размеры всех тактов композиции одинаковы и задаются в условных единицах в виде обыкновенной дроби A / B. Длительности пауз и нот задаются в тех же условных единицах в виде обыкновенной дроби 1 / X. При этом знаменатели в размере такта и длительностях нот и пауз являются степенями двойки.
В первой строке задан размер такта в формате A / B, где 1 ≤ A, B ≤ 1024. Во второй строке задано количество тактов T (1 ≤ T ≤ 100). В каждой из следующих T строк задано описание одного такта.
В начале описания такта номер i задано количество нот в этом такте Ni (1 ≤ Ni, 
), далее через пробел заданы длительности нот, каждая из которых соответствует формату 1 / X (1 ≤ X ≤ 1024).
Гарантируется, что:
- сумма длительностей нот в каждом такте не превышает его размера;
- все числители и знаменатели во вводе являются натуральными числами;
- все знаменатели являются целыми степенями двойки.
Выведите T строк, по одной для каждого такта. Строка номер i должна содержать количество добавляемых пауз в такт номер i и их длительности. Паузы должны соответствовать формату 1 / Y, где Y — натуральное число, которое является целой степенью двойки.
Количество пауз должно быть минимально возможным, а длительности необходимо выводить в порядке убывания. Сумма длительностей нот и пауз в каждом такте в итоге должна быть равна размеру такта.
4/4
4
2 1/8 1/8
1 1/1
1 1/16
2 1/4 1/2
2 1/2 1/4
0
4 1/2 1/4 1/8 1/16
1 1/4
3/4
2
1 1/4
2 1/8 1/16
1 1/2
2 1/2 1/16
24/16
2
2 1/8 1/1
2 1/8 1/4
2 1/4 1/8
2 1/1 1/8
Мэд — фронтмен известной рок-группы. На последнем выступлении он разбил все свои гитары об ударную установку своего же барабанщика и теперь задумывается над покупкой новой гитары.
В магазине Галактической Федерации продаются N различных гитар, гитара номер i стоит Ki галактических долларов. Однако Мэд живет в Соединенном Королевстве Берляндии, поэтому в наличии у Мэда только бурли. Курс галактического доллара относительно бурля абсолютно непредсказуем и меняется каждый день, в день j он равен Xj бурлей за доллар. При этом курс может быть нулевым или отрицательным. Если Мэд будет покупать гитару номер i в день j, то ему нужно будет заплатить Ki·Xj бурлей.
Мэд подозревает, что некоторые производители занижают цены на свои гитары, а другие завышают. И все это — часть глобального политического заговора с целью управления массами. Поэтому он посчитал цену, за которую, как он считает, было бы справедливо продавать каждую гитару. Для гитары номер i справедливая цена равна Bi бурлей.
Привлекательность гитары номер i в день j для Мэда равна разности справедливой и фактической цены в этот день, то есть Bi - Ki·Xj.
Мэд не торопится с выбором, так как до следующего выступления группы еще целых Q дней. Необходимо каждый день до следующего выступления определять, какая гитара наиболее привлекательна для Мэда. Если в какой-то день несколько гитар обладают максимальной привлекательностью, разрешается выбрать любую.
В первой строке задано количество различных гитар N (1 ≤ N ≤ 105) в магазине Галактической Федерации.
Каждая из последующих N строк содержит пару целых чисел: цену гитары номер i в галактических долларах Ki (0 ≤ Ki ≤ 1000) и справедливую цену этой гитары в бурлях Bi (0 ≤ Bi ≤ 105). Цены на разные гитары могут совпадать.
В следующей строке задано количество дней до следующего выступления группы Q (1 ≤ Q ≤ 105).
В следующей строке задано Q целых чисел Xj ( - 105 ≤ Xj ≤ 105), каждое из которых соответствует курсу галактического доллара относительно бурля в день j.
В единственной строке через пробел выведите Q чисел Pj, где Pj — это номер наиболее привлекательной гитары в день j.
3
1 5
2 1
2 2
5
-5 -4 -3 0 3
3 3 1 1 1
Привлекательности гитар по дням равны соответственно: 
, 
, 
, 
, 
.
Фронтмэн известной рок-группы Мэд, заработав на выпуске своего последнего альбома целое состояние, купил себе особняк с колоннами и видом на оживленную улицу. Однако в первое же утро в новом доме он столкнулся с тем, что проезжающие мимо на автомобилях фанаты начинают снимать его на камеры своих телефонов, как только он покажется из-за колонн.
Утром Мэд начинает движение из точки (0, - 1) и движется параллельно оси OX со скоростью 1 в течение времени T.
На оси OX расположены N колонн, представляющих собой отрезки шириной W. Для каждого отрезка задана X-координата левой точки Si, x. Отрезки не пересекаются, не касаются друг друга и все концы отрезков находятся в сегменте [0, T] по X-координате.
Бесконечная дорога расположена вдоль координаты Cy параллельно оси OX. По дороге движутся K машин со скоростью Cv. Для каждой машины известна X-координата Ci, x в начальный момент времени.
Колонны — непрозрачные. В некоторый момент времени Мэд попадает в кадр видеокамеры, находящейся в машине, если точку, в которой он находится, можно соединить отрезком с точкой, в которой находится машина, не касаясь и не попадая внутрь ни одного из отрезков, соответствующих колоннам.
В каждой машине находится ровно один фанат с камерой, запись он производит тогда и только тогда, когда Мэд попадает в кадр. Таких периодов может быть несколько, в этом случае и записей у фаната будет несколько. Вечером все фанаты, конечно, выкладывают все свои записи в сеть. Необходимо определить, какое суммарное время будут занимать видеоролики с Мэдом, снятые утром.
В первой строке задано время движения Мэда T (1 ≤ T ≤ 106), ширина колонн W (1 ≤ W ≤ 106), Y-координата дороги Cy (1 ≤ Cy ≤ 106) и скорость машин Cv ( - 106 ≤ Cv ≤ 106).
Во второй строке задано количество колонн N (1 ≤ N ≤ 2000).
В третьей строке заданы N чисел Si, x (0 ≤ Si, x ≤ T - W, Si, x + W < Si + 1, x) — упорядоченные по возрастанию X-координаты левых точек отрезков, соответствующих колоннам. Гарантируется, что отрезки не пересекаются и не касаются друг друга.
В четвёртой строке задано количество машин K (1 ≤ K ≤ 2000).
В пятой строке заданы K чисел Ci, x ( - 1012 ≤ Ci, x ≤ 1012) — упорядоченные по возрастанию X-координаты машин.
Все числа во входных данных целые.
Выведите суммарную длительность всех видеороликов, которые попадут в сеть. Ответ считается правильным, если абсолютная или относительная погрешность не превосходит 10 - 9.
10 1 2 -1
4
0 2 5 9
3
-1 4 11
18
5 2 3 -3
2
0 3
5
-1 0 8 9 12
10
8 3 2 3
2
1 5
3
-3 0 4
13.400000000000
Взаиморасположение и вектора скоростей Мэда, машин и колонн в начальный момент времени, соответствующие первому тестовому примеру, продемонстрированы на рисунке.
В первом тестовом примере хронометраж видеороликов, снятых в машинах, равен соответственно 
.
Во втором тестовом примере — 
.
В третьем тестовом примере — 
.
В галерее наночастиц Галактической федерации проводится выставка электронов. Каждому купившему входной билет разрешается понаблюдать за полётом одного электрона и сделать один снимок на свой нанофотоаппарат.
Полёт электрона начинается в точке (0, 0), далее он перемещается по прямой в точку (1, 1), затем в точку (3, - 1), затем в точку (6, 2), затем в точку (10, - 2) и т. д. Таким образом, на i-м шаге X-координата электрона увеличивается на i, а Y-координата увеличивается на i, если шаг нечётный, и уменьшается на i, если шаг чётный. Электрон летит по описанной траектории бесконечно.
Из-за того, что электрон движется очень быстро, на снимок попадает не вся траектория, а только точки, в которых электрон меняет своё направление. Вам необходимо посчитать количество таких точек, находящихся строго внутри прямоугольника с координатами левой нижней точки (Lx, Ly) и правой верхней точки (Rx, Ry). Точка начала движения электрона не считается точкой смены направления.
В первой строке задано количество тестов T (1 ≤ T ≤ 10000).
В следующих T строках заданы тесты в виде координат прямоугольника Lx, Ly, Rx, Ry ( - 1018 ≤ Lx < Rx ≤ 1018, - 1018 ≤ Ly < Ry ≤ 1018).
Для каждого теста выведите количество точек смены направления электрона внутри прямоугольника.
5
0 -3 8 4
0 0 7 3
1 1 6 2
-1 -2 5 0
1 -3 11 0
3
2
0
1
2
Галактическая федерация проводит национальный конкурс на должность самого великого министра. В конкурсе участвуют N министров, каждый из которых оценивается в судьями в баллах в зависимости от степени величия.
Участники конкурса распределяются в таблице по местам от 1-го до N-го в порядке убывания набранных баллов. Если какие-то K участников набрали одинаковые баллы, то есть заняли в таблице места X, X + 1, ..., X + K - 1, то всем им назначается место равное X, а следующим свободным местом в таблице становится X + K.
Рассмотрим пример из шести участников. Пусть участники 1 и 2 набрали по 10 баллов, участник 3 — 9 баллов, участники 4, 5 и 6 — по 8 баллов. Тогда места в таблице распределятся следующим образом: 
.
Посчитайте, сколько существует различных распределений мест в таблице. Два распределения с одинаковым набором мест, но разными участниками на этих местах, считайте одинаковыми.
Единственное число N (1 ≤ N ≤ 50) — количество участников конкурса.
Искомое количество различных распределений мест в таблице результатов.
3
4
1
1
В первом тесте места участников могут распределиться так: 
; 
; 
; 
.
Во втором тесте единственное возможное распределение: 
.
Фронтмен известной рок-группы Мэд построил в своем новом особняке оранжерею, которая представляет собой клеточное поле N × M. В оранжерее Мэд хочет посадить дронов двух моделей: «Бабочка» и «Ураган», при этом он хочет, чтобы дроны заняли все пространство оранжереи.
Каждый дрон имеет четыре ноги, которые при посадке занимают по одной клетке так, что эти клетки ограничивают квадрат со сторонами, параллельными границам оранжереи, а сам дрон занимает весь этот квадрат. При этом ноги дрона обязательно должны занимать разные клетки и могут быть расставлены как угодно широко.
Чтобы рассадка не выглядела слишком хаотично, Мэд хочет, чтобы дроны занимали квадраты одинаковых размеров, однако, чтобы внести разнообразие, никакие два дрона одной модели не должны касаться друг друга стороной, но могут касаться углами.
Необходимо помочь Мэду посадить как можно больше дронов.
В единственной строке заданы размеры оранжереи в особняке Мэда N и M (1 ≤ N, M ≤ 100).
Если невозможно посадить дронов по описанным правилам, выведите в единственной строке NO.
Если решение существует, в первой строке выведите YES, а в N последующих строках по M символов выведите искомую расстановку дронов. Каждая клетка должна определять модель дрона, который ее занимает. Дрон модели «Бабочка» обозначается латинской буквой B, а дрон модели «Ураган» — латинской буквой X.
Рассадка должна соответствовать следующим условиям:
- все дроны должны занимать квадраты одного размера со стороной больше единицы;
- дроны одной модели могут соприкасаться только углами;
- каждая клетка оранжереи должна быть занята каким-либо дроном;
- в левом верхнем углу оранжереи должен сидеть дрон модели «Бабочка».
8 4
YES
BBXX
BBXX
XXBB
XXBB
BBXX
BBXX
XXBB
XXBB
6 9
YES
BBBXXXBBB
BBBXXXBBB
BBBXXXBBB
XXXBBBXXX
XXXBBBXXX
XXXBBBXXX
5 5
YES
BBBBB
BBBBB
BBBBB
BBBBB
BBBBB
1 3
NO
Специальная подземная тюрьма Галактической федерации для участников Сопротивления состоит из N уровней, пронумерованных от 0 до N - 1 от верхнего к нижнему. Уровни расположены последовательно друг под другом, каждый из них имеет форму круга, центры кругов находятся на одной вертикальной оси, а их диаметры увеличивается с увеличением номера уровня. Уровень номер i делится на 2i одинаковых секторов — камер с номерами от 2i до 2i + 1 - 1.
Каждая камера, кроме камер последнего уровня, имеет две двери с кодовыми замками — левую и правую, если смотреть на двери изнутри камеры. Каждая из дверей на уровне i ведет в камеру на уровне i + 1, находящуюся ровно под этой дверью. Когда вводится верный код доступа к какой-либо двери, каждый уровень тюрьмы независимо от других поворачивается равновероятно влево или вправо вокруг своей оси на один сектор, то есть на угол 360 / 2i градусов по или против часовой стрелки. Только после этого дверь открывается.
Схема взаимного расположения камер и дверей изображена на рисунке (вид сверху), стрелкой показано направление взгляда в камере номер 1:
Лидерам Сопротивления, находящимся в заключении в камере 1 на нулевом уровне, удалось добыть секретные коды доступа ко всем дверям тюрьмы. Также им стало известно, сколько заключенных находится в каждой камере и что ровно в полночь уровни будут расположены друг относительно друга так, как показано на рисунке, то есть из камеры s левая дверь будет вести в камеру 2s, а правая — в камеру 2s + 1.
Лидеры собираются начать побег ровно в полночь. Они будут перемещаться по камерам, начиная со своей, каждый раз спускаясь в одну из камер следующего уровня и забирая с собой всех заключенных на своем пути. Когда лидеры окажутся в одной из камер последнего уровня, союзники на воле отследят их местоположение, проделают подкоп и вызволят всех из этой камеры.
Времени на раздумья в процессе побега не будет, поэтому необходимо помочь лидерам Сопротивления заранее составить план открывания дверей при побеге таким образом, чтобы математическое ожидание освобожденных в итоге человек было максимальным. План должен состоять из N - 1 символов, i-й символ определяет, какую из дверей открывать, находясь на уровне i - 1: L означает левую дверь, а R — правую. Торопитесь, до полуночи осталось меньше пяти часов...
В первой строке задано число уровней N (2 ≤ N ≤ 16).
Следующие N строк содержат описание уровней, начиная с нулевого. Описание уровня i содержит 2i целых положительных чисел, которые соответствуют количеству участников Сопротивления в каждой камере этого уровня в порядке по часовой стрелке, начиная с камеры с меньшим номером. Другими словами, если не считать число N, то число номер k во вводе соответствует количеству заключенных в камере k.
Количество заключенных ни в какой из камер не превышает 106.
Выведите план побега в виде строки из N - 1 символов L и R. Если несколько планов позволяют достичь максимального математического ожидания, разрешается вывести любой из них.
4
1
10 4
8 2 7 3
8 6 2 1 1 8 2 9
RLL
После успешного побега из здания подземной тюрьмы Галактической федерации соратники Сопротивления захватили бронированный автомобиль и теперь они должны добраться из точки P = (0, 0) в точку Q = (0, Yq).
Задача усложняется тем, что вокруг тюрьмы возведено множество стен, и чтобы покинуть тюрьму необходимо проехать последовательно через N ворот, которые представляет собой параллельные оси OX отрезки.
Вам необходимо посчитать длину кратчайшего пути из точки P в точку Q при условии, что путь должен проходить последовательно сквозь каждые ворота.
В первой строке задано число ворот N (1 ≤ N ≤ 105).
Во второй строке задана Y-координата конечной точки Yq (2 ≤ Yq ≤ 109).
В следующих N строках заданы координаты ворот в виде троек чисел Yi, Xil, Xir (0 < Yi < Yq, Yi < Yi + 1, - 109 ≤ Xil < Xir ≤ 109).
Все числа во входных данных целые.
Выведите длину кратчайшего пути. Ответ считается правильным, если абсолютная или относительная погрешность не превосходит 10 - 6.
3
5
1 -1 1
3 1 2
4 -2 -1
6.812559200041
Кратчайший путь для теста из примера показан на рисунке:
Институт по изучению дронов в естественных условиях при правительстве Галактической Федерации занимается изучением дронов в естественных условиях. В настоящий момент институт проводит исследования по влиянию на дронов различной музыки. Пока ученым удалось установить, что если транслировать дронам в естественных условиях звуковые волны определенной частоты, то в зависимости от возраста некоторые дроны засыпают, другие — перегорают, а остальные ведут себя естественно.
Предположим, возраст некоторого дрона равен A и ему транслируется звуковая волна частотой B. Тогда, судя по экспериментальным данным, если 
, то дрон засыпает, а если 
, то перегорает. Если ни одно из условий не выполняется, дрон ведет себя естественно.
— это операция побитового сложения по модулю два, также известная как XOR и побитовое исключающее «ИЛИ». Результатом такой операции будет число, каждый бит которого зависит от значений битов в соответствующих разрядах двоичной записи операндов. Если биты в разряде k операндов равны, то в разряде k результата будет стоять 0, в противном случае — 1.
Чтобы не выводить лишний раз дронов из спячки и не менять предохранители, ученые хотят теоретически определить, сколько дронов при воздействии той или иной звуковой волны заснут, а сколько перегорят.
В первой строке задано количество дронов N (1 ≤ N ≤ 105).
Следующая строка содержит N целых чисел Ai (1 ≤ Ai ≤ 109) — возраста дронов, участвующих в экспериментах. По ходу моделирования всех экспериментов можно считать, что возраста дронов не меняются.
В следующей строке задано количество экспериментов, которые необходимо промоделировать Q (1 ≤ Q ≤ 105).
Последняя строка содержит Q целых чисел Bj (1 ≤ Bj ≤ 109) — частоты звуковых волн, транслируемые в разных экспериментах.
Выведите Q строк — результатов экспериментов.
Каждый результат должен содержать два числа — количество заснувших и количество перегоревших дронов в соответствующем эксперименте.
3
6 10 2
8
1 2 3 4 5 6 7 8
0 3
1 0
1 0
1 2
1 2
1 1
1 1
1 2
В первом эксперименте перегорают дроны 1, 2 и 3. Во втором и третьем засыпает дрон 3. В четвертом и пятом засыпает дрон 1, а перегорают дроны 2 и 3. В шестом и седьмом засыпает дрон 1, а перегорает 2. В последнем эксперименте засыпает дрон 2, а перегорают дроны 1 и 3.