Арсений уже совсем взрослый и самостоятельный. Мама решила оставить его на m дней в одиночестве и уехать отдыхать в тёплые страны. Перед этим она наготовила ему много еды, оставила достаточное количество карманных денег и постирала всю одежду.
Однако за десять минут до отъезда в тёплые страны ей пришла в голову мысль, что Арсению надо оставить точную инструкцию, какую одежду надевать в какой из дней её отсутствия. Арсений живёт в очень необычной семье, в которой вся одежда пронумерована: например, n носков Арсения имеют различными целые номера от 1 до n . Поэтому всё, что потребовалось его маме, это указать для каждого дня два числа l i и r i — номера носков, которые надо надеть в i -й день на левую и правую ногу соответственно (разумеется, l i не совпадает с r i ). Каждый носок покрашен в один из k цветов.
Уже после отъезда матери Арсений заметил, что в некоторые дни в соответствии с инструкцией ему придётся надеть носки разных цветов, что, конечно, является досадной оплошностью, вызванной спешкой перед отъездом при составлении инструкции. Но Арсений находчивый мальчик, и, по счастливому совпадению, он нашёл у себя дома банки с красками всех k цветов, которые встречаются среди его носков.
Арсений собирается перекрасить некоторые носки таким образом, чтобы, следуя инструкции, оставленной его мамой, на протяжении каждого из m дней носить одноцветные носки. Арсений уже запланировал деловые встречи в каждый день отсутствия мамы, в течение которых у него не будет возможности заниматься перекраской носков, поэтому он должен определиться с цветами и провести всю работу именно сейчас.
Он хочет как можно быстрее расправиться с этой задачей, чтобы отправиться играть в недавно вышедшую суперпопулярную игру Bota-3, поэтому он просит вас помочь определить минимальное количество носков, которое ему придётся перекрасить, чтобы в каждый день надевать два одноцветных носка.
В первой строке находится три целых числа n , m и k ( 2 ≤ n ≤ 200 000 , 0 ≤ m ≤ 200 000 , 1 ≤ k ≤ 200 000 ) — количество носков, количество дней отсутствия мамы и количество доступных цветов соответственно.
Во второй строке находится n разделённых пробелами целых чисел c 1 , c 2 , ..., c n ( 1 ≤ c i ≤ k ) — цвета носков Арсения.
В каждой из последующих m строк находится по два целых числа l i , r i ( 1 ≤ l i , r i ≤ n , l i ≠ r i ) — номера носков, которые Арсений должен надеть в i -й день на левую и правую ногу соответственно.
Выведите единственное целое число — минимальное количество носков, которые Арсений должен перекрасить, чтобы не насмешить людей разноцветными носками ни в один из дней отсутствия мамы.
В первом примере Арсений может, например, перекрасить первый и третий носки во второй цвет.
Во втором примере ничего перекрашивать не придётся.
3 2 3 1 2 3 1 2 2 3
2
3 2 2 1 1 2 1 2 2 1
0
Археологи, найдя секретный ход в подземелье одной из пирамид в Цикляндии, столкнулись с необычным замком на двери в сокровищницу. На замке было написано n слов, каждое из которых состоит из нескольких иероглифов. Рядом с замком на стене был обнаружен необычный круглый рычаг, поворот которого меняет иероглифы, из которых состоят слова на замке, по некоторому принципу. Также рядом с иероглифом была найдена надпись на древнецикляндском, которая гласит, что замок откроется, только если слова, написанные на замке, станут идти в лексикографическом порядке (определение дано в пояснении).
Несмотря на то, что археологи отлично знали весь древнецикляндский алфавит, который состоял из c иероглифов, они никак не могли определить закономерность, по которой меняются буквы. Наконец кто-то догадался позвать вас, главного мыслителя современной Цикляндии. Вам хватило одного взгляда, чтобы понять, что поворот рычага на одну позицию по часовой стрелке заменяет каждый иероглиф на следующий за ним по алфавиту, то есть x -й ( 1 ≤ x ≤ c - 1 ) иероглиф превращается в ( x + 1) -й, а c -й превращается в первый.
Помогите археологам определить, на сколько позиций по часовой стрелке надо повернуть рычаг, чтобы можно было открыть дверь, либо определите, что требуемого положения рычага не существует, и надо либо искать ещё какой-нибудь потайной рычаг, либо идти за динамитом.
В первой строке находится два числа n и c ( 2 ≤ n ≤ 500 000 , 1 ≤ c ≤ 10 6 ) — количество слов, написанных на замке, и количество иероглифов в древнецикляндском алфавите.
Каждая из последующих n строк описывает одно слово, написанное на замке. В i -й из последующих строк сначала находится целое число l i ( 1 ≤ l i ≤ 500 000 ), обозначающее длину i -го слова, после чего следует l i целых чисел w i , 1 , w i , 2 , ..., w i , l i ( 1 ≤ w i , j ≤ c ) — алфавитные номера иероглифов, составляющих i -е слово. Символ 1 является самым маленьким в древнецикляндском алфавите, а символ c — самым большим.
Гарантируется, что суммарная длина всех слов не превосходит 10 6 .
Если возможно открыть дверь, поворачивая рычаг, выведите число x ( 0 ≤ x ≤ c - 1 ), обозначающее, сколько раз его надо повернуть по часовой стрелке. Если подходящих значений x несколько, выведите любое из них.
Если, поворачивая рычаг, дверь открыть невозможно, выведите - 1 .
Слово a 1 , a 2 , ..., a m длины m лексикографически не превосходит слова b 1 , b 2 , ..., b k длины k , если выполняется одно из двух:
- либо в первой позиции i , такой что a i ≠ b i , символ a i идёт раньше по алфавиту, чем символ b i , то есть в первой различающейся позиции символ слова a меньше символа слова b ;
- либо (если такой позиции нет) m ≤ k , то есть второе слово начинается с первого либо совпадает с ним
Про последовательность слов говорят, что они идут в лексикографическом порядке , если каждое слово в нём (кроме последнего) лексикографически не превосходит следующего за ним.
В первом примере после поворота рычага на 1 позицию по часовой стрелке слова примут следующий вид:
1 3
2
3 1 2
3 1 2 3
Во втором примере слова уже идут в лексикографическом порядке.
Можно проверить, что в последнем примере, какой бы сдвиг мы ни применили, слова не станут идти в лексикографическом порядке.
4 3 2 3 2 1 1 3 2 3 1 4 2 3 1 2
1
2 5 2 4 2 2 4 2
0
4 4 1 2 1 3 1 4 1 2
-1
С древних времён ужасный крылатый Сфинкс подстерегает путников у Большого Камня по дороге в священный город Истины, задаёт им хитроумные загадки и съедает тех, кто не сумел дать правильный ответ. Турист Пётр тоже решил посетить город Истины и встретил чудовище.
Сфинкс задал ему такую загадку: «На Большом Камне написано число n . Найди наименьшее целое положительное число k , такое что сумма цифр числа k в десятичной системе счисления делится на n и сумма цифр числа k + 1 в десятичной системе счисления делится на n ».
Пётр догадался, что коварный Сфинкс задаёт всем путникам одну и ту же задачу, изменяя лишь число n , и загорелся желанием избавить мир от смертоносных загадок чудовища. Он решил написать на Большом Камне алгоритм, который позволит всем путникам давать правильный ответ на загадку. Помогите ему в этом.
В единственной строке находится целое число n ( 1 ≤ n ≤ 100 000 ).
В случае если искомого числа k не существует, выведите одно число 0 .
В противном случае выведите целое положительное число k , являющееся ответом на загадку Сфинкса. Ответ не должен содержать пробелов и ведущих нулей.
В первом примере суммы цифр чисел k и k + 1 должны делиться на 1. Это условие выполнено для любого целого положительного k , поэтому ответом является 1.
Во втором примере суммы цифр чисел k и k + 1 должны делиться на 4. Числа 39 и 40 удовлетворяют этому требованию, поскольку 3 + 9 = 12 и 4 + 0 = 4 . Нетрудно убедиться, что никакое меньшее число k не является ответом на эту загадку Сфинкса.
1
1
4
39
Где-то в Москве в очередной раз построили новый дом: красивый, современный и многоэтажный. Он состоит из ровно \(n\) жилых этажей, пронумерованных от \(1\) до \(n\) снизу вверх, и подземной парковки, являющейся нулевым этажом.
Дом уже был почти готов к сдаче в эксплуатацию, но вот незадача — в самый ответственный момент по всему зданию прорвало водопроводные трубы, в результате чего многие этажи залило водой. К моменту, когда все трубы были заделаны, на \(i\)-м этаже находилось \(w_i\) литров воды.
Также из-за того, что при строительстве дома все средства ушли на отделку фасада, а на перекрытия между этажами был пущен самый дешёвый материал, оказалось, что между этажами ощутимо протекают потолки. В частности, пропускная способность пола \(i\)-го этажа составляет \(v_i\) литров воды в час.
В рамках данной задачи считается, что скорость вытекания воды с этажа зависит только от пропускной способности пола и не зависит от количества воды на этаже. Временем падения воды с потолка этажа до пола также следует пренебречь. Считайте, что все этажи достаточно объёмные, чтобы вместить всю воду, скопившуюся в здании.
Владельцы стройки интересуются, через сколько часов вся вода вытечет на парковку, и они смогут начать продажи квартир?
В первой строке записано единственное целое число \(n \ (1 \le n \le 200 000\)) — количество жилых этажей здания.
Вторая строка содержит n целых чисел \(w_1, \ w_2, \dots, \ w_n \ (0 \le w_i \le 1000)\), задающих количество воды в литрах на каждом из жилых этажей здания.
Третья строка содержит \(n\) целых чисел \(v_1, \ v_2, \dots, \ v_n \ (1 \le v_i \le 200 000\)), задающих скорость протекания пола каждого из жилых этажей здания в литрах в час.
Выведите единственное число — время в часах, через которое вся вода стечёт на подземную парковку.
Ваш ответ будет засчитан, если его абсолютная или относительная погрешность не превосходит \(10^{−4}\) , а именно: если ваш ответ — \(p_{ans}\), а ответ жюри — \(j_{ans}\), то ваш ответ будет засчитан, если \(\frac{|p_{ans} \ − \ j_{ans}|}{max\{1, \ |j_{ans}|\}} \le 10^{−4}\) .
В первом примере на первом этаже изначально 10 литров воды, а на втором — 20 литров, все полы текут со скоростью 5 литров в час. Через 2 часа после начала 10 единиц воды перетечёт с первого этажа на парковку, а также со второго этажа на первый, значит, на первом этаже количество воды не изменится, а на втором этаже станет на 10 литров меньше. По прошествии ещё двух часов на первом этаже по-прежнему будет 10 литров воды, а второй этаж опустеет. А ещё через 2 часа вся вода с первого этажа стечёт на подземную парковку.
2 10 20 5 5
6.0000000000
3 0 0 100 45 40 50
2.5000000000
Около полугода назад было доказано, что проверка возможности прохождения уровня в классической игре Super Mario Bros. лежит в классе сложности PSPACE и, более того, является PSPACE -полной задачей. Мы не предлагаем вам понять, что это значит, но предлагаем почувствовать, насколько сложно бывает программно играть в компьютерные игры. Для этого мы опишем упрощённый вариант игры и предложим проверить, возможно ли пройти уровень в нашем варианте «Марио» или нет (для понимания задачи необязательно быть знакомым с оригинальной игрой).
Наш вариант игры происходит на клетчатом поле, состоящем из n строк на m столбцов. Каждая клетка поля может принадлежать одному из следующих видов:
- пустая клетка, обозначается символом подчёркивания ' _ ';
- клетка с землёй, обозначается решёткой ' # ';
- клетка, содержащая монетку, обозначается строчной английской буквой ' c ';
- клетка, в которой находится Марио, обозначается строчной английской буквой ' m ';
- клетка, в которой находится Принцесса, обозначается строчной английской буквой ' p '.
Пронумеруем строки сверху вниз числами от 1 до n и столбцы слева направо целыми числами от 1 до m . Где-то в m -м столбце находится Принцесса (в клетке, обозначенной буквой ' p '). А в одной из клеток первого столбца стоит Марио (в клетке, обозначенной ' m '). Конечно, и Принцесса, и Марио стоят на земле, то есть в клетках, под каждым из них находится земля.
Также в некоторых столбцах от второго до ( m - 1) -го, возможно, находятся монетки. В одном столбце находится не более одной монетки, а также любая монетка лежит на земле, то есть в клетке под монеткой обязательно находится земля.
Марио, как и в классическом варианте игры, нужно добраться до Принцессы, но еще ему необходимо собрать все монетки, которые есть на поле. Марио может перемещаться только посредством прыжков.
Прыжок Марио состоит из двух частей: сначала он летит вертикально вверх, а потом горизонтально вправо. Вертикальная часть прыжка может иметь длину y от 0 до a клеток, а горизонтальная может иметь длину x от 0 до b клеток. В частности, Марио может прыгнуть вертикально вверх, не перемещаясь по горизонтали, а также прыгнуть горизонтально вправо, не смещаясь при этом по вертикали. Естественно, Марио не может пролетать сквозь клетки, содержащие землю. Обратите внимание, в отличие от оригинальной игры Марио не может перемещаться влево.
Если после окончания прыжка Марио оказывается в клетке, под которой нет земли, он падает вниз, пока под ним не окажется земля. В случае, если Марио долетает до n -й (самой нижней) строки, он проваливается вниз за экран и погибает, а игра заканчивается. Также Марио не может выпрыгивать за границы поля сверху или справа.
Если Марио оказывается в клетке с монеткой (возможно, в процессе прыжка), то он её подбирает.
Определите, возможно ли добраться до клетки с Принцессой, подобрав все монетки.
В первой строке содержится 4 целых числа n , m , a , b ( 2 ≤ n , m ≤ 100 , 1 ≤ a , b ≤ 10 ) — размеры поля и ограничения на длину прыжка Марио.
Далее следуют n строк по m символов, описывающих уровень. Каждый символ является одним из следующих: ' _ ', ' # ', ' c , ' m ', ' p ' (см. описание клеток в основной части условия).
Гарантируется, что на поле находятся единственная клетка с Марио и единственная клетка с Принцессой.
Гарантируется, что в каждом столбце от второго до ( m - 1) -го включительно находится не более одной монетки, а в первом и последнем столбце монеток нет.
Гарантируется, что Марио, Принцесса и монетки находятся в клетках, непосредственно под которыми есть клетки с землёй, в частности, Марио, Принцесса и монетки не находятся в n -й строке.
Выведите слово « YES » (без кавычек), если Марио может собрать все монетки с поля и оказаться в клетке с Принцессой, в противном случае выведите слово « NO » (без кавычек).
В первом примере Марио должен сделать два прыжка. Первым прыжком на 1 клетку вправо Марио подберёт монетку, а вторым на одну клетку вверх и две клетки вправо доберётся до принцессы.
Во втором примере Марио не может добраться до принцессы. Обратите внимание, Марио не может находиться в последней строке, так как он проваливается вниз за экран и погибает.
В четвёртом примере Марио не может сразу прыгнуть к Принцессе, потому что он должен подобрать монетку, но если он прыгнет вправо и вниз к монетке, то он не сможет потом вернуться обратно к Принцессе (обратите внимание, Марио не может вернуться обратно в стартовую точку, потому что он не умеет прыгать влево), поэтому ответ на этот тест — « NO ».
3 4 1 2 ___p mc_# ##_#
YES
4 5 10 3 __#_p mc__# ##___ _____
NO
5 3 3 2 ___ _#_ _#p m_# ##_
YES
4 4 1 3 m__p #__# _#c_ __#_
NO