Темы
Информатика(2656 задач)
--->
228 задач
<---
Археологи, найдя секретный ход в подземелье одной из пирамид в Цикляндии, столкнулись с необычным замком на двери в сокровищницу. На замке было написано 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 , если выполняется одно из двух:
Про последовательность слов говорят, что они идут в лексикографическом порядке , если каждое слово в нём (кроме последнего) лексикографически не превосходит следующего за ним.
В первом примере после поворота рычага на 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 стикеров в ряд на стене и написали на каждом стикере своё число. Далее они стали совершать ходы по очереди, причём Петя ходит первым.
В течение каждого хода происходит следующее. Пусть на стене сейчас висит m ≥ 2 стикеров. Игрок, которых ходит в данный момент, выбирает целое число k от 2 до m и забирает k стикеров с левого конца ряда себе. После этого он клеит новый стикер с левого конца ряда и пишет на нём число, равное сумме всех чисел на стикерах, которые он забрал себе на этом ходу.
Игра заканчивается, как только на стене остаётся один-единственный стикер. Счёт игрока определяется как сумма чисел, написанных на всех стикерах, которые он забрал себе. Каждый игрок стремится максимизировать разницу между своим количеством очков и количеством очков соперника.
Конечно же, Петя и Гена вкладывают другой смысл в понятие «играть в игру», нежели мы привыкли себе думать. Они уже разобрались, как по значению n и числам, написанным на каждом из стикеров исходно, определить разницу между Петиными и Гениными очками, если они будут играть оптимально. Справитесь ли вы с той же самой задачей?
В первой строке находится целое число n ( 2 ≤ n ≤ 200 000 ) — количество стикеров, которые исходно висят на стене.
Во второй строке находится n чисел a 1 , a 2 , ..., a n ( - 10 000 ≤ a i ≤ 10 000 ) — числа, написанные на стикерах в порядке слева направо.
Выведите одно число — разность между количеством очков у Пети и Гены в конце игры, если они играют оптимально.
В первом тесте из условия оптимальным ходом для Пети будет сразу взять себе все имеющиеся стикеры, в результате чего счёт Пети составит 14 , а счёт Гены — 0 .
Во втором тесте из условия оптимальная последовательность ходов для игроков выглядит следующим образом. На первом ходу Петя возьмёт себе первые три стикера и добавит слева от ряда стикер с числом - 8 . На втором ходу Гена возьмёт себе оставшиеся два стикера. Счёт Пети составит 1 + ( - 7) + ( - 2) = - 8 , а счёт Гены — ( - 8) + 3 = - 5 , значит разность очков Пети и Гены составит - 3 .
3 2 4 8
14
4 1 -7 -2 3
-3
С древних времён ужасный крылатый Сфинкс подстерегает путников у Большого Камня по дороге в священный город Истины, задаёт им хитроумные загадки и съедает тех, кто не сумел дать правильный ответ. Турист Пётр тоже решил посетить город Истины и встретил чудовище.
Сфинкс задал ему такую загадку: «На Большом Камне написано число 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 лет и n - 1 зим. И с того самого момента он вёл дневник на длинной полоске пергамента, в котором описывал лета и зимы, свидетелем которых он был.
Каждое лето он записывал цифру от 0 до 9 , характеризующую, насколько солнечным было это лето. Зимы же граф Бутер описывал проще: если снега зимой было много, значит зима удалась, если снега было мало, значит зима вышла неудачной. Каждую удачную зиму он рисовал в своём дневнике снежинку после последней записанной цифры, а каждую неудачную он не рисовал ничего. Снежинка при этом выглядела следующим образом: * .
Много лет спустя некто Артур Бабаев нашел эту полоску пергамента. На нём были написаны n цифр, и между некоторыми из них были нарисованы снежинки, которые он воспринял как знак умножения. Он быстро посчитал получившееся число, но это было слишком просто для него.
Артур принадлежит к обществу Любителей Квантовой Механики и знает, что наша вселенная не единственна. Более того, в каждой параллельной вселенной жило по такому же графу Бутер де Биту, и единственное, в чём отличалось существование разных де Битов, это удачность зим, которые они переживали. А именно, каждая из 2 n - 1 последовательностей удачных/неудачных зим встречалась ровно в одной вселенной. Аналогичным образом в каждой вселенной существовало по Артуру, нашедшему этот самый лист пергамента и посчитавшему значение выражения на нём.
Артур из нашей вселенной очень захотел посчитать сумму чисел, полученную Артурами из всех вселенных. Так как это число может быть очень большим, он будет доволен, если узнает только остаток от его деления на 10 9 + 7 .
Заметим, что ни одного из Артуров не смутит ситуация, в которой один из образовавшихся на полоске сомножителей содержит ведущие нули. Например, полоска пергамента, на которой написана строка 01 * 02 , задаёт корректное выражение, значение которого равняется 2 .
Первая и единственная строка входных данных содержит последовательность из n ( 1 ≤ n ≤ 200 000 ) цифр без пробелов, записанную де Битами во всех вселенных.
Выведите остаток от деления суммы всех чисел, посчитанных Артурами из всех вселенных, на 10 9 + 7 .
В первом примере есть 2 2 = 4 вселенные, и, соответственно, 4 полоски из пергамента. На них написаны выражения 1 * 2 * 3 , 12 * 3 , 1 * 23 , 123 , значит, соответствующие Артуры вычислили результаты 6 , 36 , 23 и 123 , дающие в сумме 188 .
123
188
0102
124
Осенью в одной провинциальной средневековой общине на юго-востоке Уэльса проходит делёж собранного урожая яблок. Эта община имеет внутреннюю иерархию, согласно которой каждый из n человек имеет ранг, являющийся целым положительным числом от 1 до n , причём все люди имеют разные ранги.
Процесс дележа урожая проходит следующим образом:
Вам стало интересно, насколько данная процедура дележа яблок является честной. Определите, какое минимальное количество яблок может оказаться у человека после участия в описанной процедуре.
В единственной строке находится два целых числа n и k ( 3 ≤ n ≤ 10 000 , 1 ≤ k ≤ 10 9 ) — число людей и число яблок соответственно.
Выведите единственное целое число — минимальное количество яблок, которые могут оказаться у человека в результате описанной процедуры.
В первом примере община состоит из трёх людей, а урожай состоит из восьми яблок. Рассмотрим, например, следующий порядок рангов: 3, 1, 2.
Таким образом, человеку с рангом 1 достанется одно яблоко. С другой стороны, вне зависимости от порядка людей в кругу каждому человеку достанется хотя бы одно яблоко, потому что первых шести яблок хватит на всех троих людей при любом порядке раздачи. Значит, минимальное возможное количество яблок у человека будет равно одному.
Во втором примере урожай состоит из одного-единственного яблока. В этом случае при любом порядке людей в кругу и любом выборе начинающего человека единственное яблоко достанется начинающему, а двум оставшимся людям яблок не достанется совсем. Значит, минимальное возможное количество яблок у человека будет равно нулю.
3 8
1
3 1
0