Страница: << 1 2 Отображать по:
#113648
Археология 80-го уровня
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Археологи, найдя секретный ход в подземелье одной из пирамид в Цикляндии, столкнулись с необычным замком на двери в сокровищницу. На замке было написано 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
#113649
Загадка Сфинкса
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes

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

Сфинкс задал ему такую загадку: «На Большом Камне написано число 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
#113650
У вас течёт!
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Где-то в Москве в очередной раз построили новый дом: красивый, современный и многоэтажный. Он состоит из ровно \(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 часа вся вода с первого этажа стечёт на подземную парковку.

Во втором примере через два часа после начала на третьем этаже совсем не останется воды. За это же время из 100 литров, притёкших на второй этаж, останется только 20, а 80 литров, перетёкших со второго этажа на первый, сразу окажутся на парковке, потому что пропускная способность пола на первом этаже выше, чем пропускная способность потолка (являющегося полом второго этажа). За полчаса оставшийся объём воды на втором этаже перетечёт на первый этаж и сразу окажется на парковке, таким образом, ответ — 2.5 часа.

Примеры
Входные данные
2
10 20
5 5
Выходные данные
6.0000000000
Входные данные
3
0 0 100
45 40 50
Выходные данные
2.5000000000
#113651
Марио
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Около полугода назад было доказано, что проверка возможности прохождения уровня в классической игре 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
Страница: << 1 2 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест