Задача 1. Кошачьи шпионы ≡

Условие

В кошачьем государстве завелись собаки-шпионы. Визуально их отличить сложно, они слишком хорошо маскируются. Однако кошачье мяуканье у них повторить не очень то и получается. Они всегда стараются, но допускают ошибки.

Мяуканье представляет из себя набор из букв m, e, o, w, причем этих букв может быть много, но одинаковые буквы всегда идут подряд.

Вы, как член службы безопасности кошачьего государства, допросили n особей, и каждого попросили издать звук мяуканья. От вас требуется ответить на вопрос: сколько среди опрошенных вами особей являются шпионами.

Настоящие коты никогда не ошибаются и издают правильно мяуканье, а вот собаки-шпионы всегда допускают хотя бы одну ошибку.

Формат входных данных

Первая строка входного файла содержит одно целое число: n - количество допрошенных особей.

В следующих n строках содержится целое число m_i и строка s_i длинны m_i.

Формат выходных данных

Выходной файл должен содержать одно целое число - количество шпионов.

Ограничения

0 < N ≤ 10⁵

0 < m_i ≤ 10⁵

0 < ∑m_i ≤ 4 * 10⁵

Примеры тестов

5
4 meow
11 meeeeooooow
4 miow
4 myau
5 hello

3

7
7 bonjour
7 alaykum
8 dobryden
2 ep
9 reverence
4 iiti
8 konishua

7

Задача 2. Мускулистый Василий ≡

Условие

Программист Вася осознал что не может целыми днями сидеть за компьютером, и решил пойти в спортзал. Однако его тренер, когда узнал, что Вася программист, решил сделать ему особенную тренировку. Он сообщает Васе целое число n - количество повторений, а Вася в свою очередь должен рассчитать сколько подходов ему надо сделать.

Выносливость Васи оценивается одним целый числом m и означает сколько повторений он сделает за первый подход. Каждый следующий подход Вася немного устает, и сможет сделать на k повторений меньше, чем в предыдущий подход.

Помогите Васе выяснить, за какое наименьшее количество подходов он выполнит поручение тренера. Если Вася окончательно устанет прежде, чем справится с задачей, выведите -1.

Формат входных данных

Первая строка входного файла содержит 3 числа: n - количество повторений, m - количество повторений в первом подходе, k - снижаемое количество повторений.

Формат выходных данных

Выходной файл должен содержать одно единственное число - минимальное количество подходов или -1, если такое невозможно.

Ограничения

0 < N ≤ 10¹⁸

0 ≤ K ≤ M ≤ 10⁹

Система оценки и описание подзадач

Баллы за подзадачи начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

Примеры тестов

10 4 1

4

100 50 20

-1

Задача 3. Lines 1 ≡

Условие

Поле для игры в Lines представляет собой квадрат размером 10 × 10 клеток. В каждой клетке может находиться шарик одного из шести цветов. Ход игрока состоит в перемещении одного из шариков на другую клетку. Разрешены только перемещения, которые можно сделать путём последовательности шагов на одну свободную клетку по горизонтали или вертикали.

После каждого хода все шарики, входящие в горизонтальные, вертикальные и диагональные ряды одноцветных шариков длиной 5 и более, удаляются с поля. Перед ходом на поле таких рядов нет.

Требуется по данному описанию поля найти такой ход, после которого с поля будет удалено максимальное количество шариков, и вывести это количество

Формат входных данных

Формат выходных данных

Примеры тестов

........3.
....2..3..
....2.3...
....23....
..22.222..
.....2....
..55..2...
..25...2..
..2.....2.
..........

10

Задача 4. Секретный секрет ≡

Условие

У Артема есть очень важный секрет. А так как Артем ещё и программист, то компьютерам свою тайну он не доверяет и хранит её в сейфе с особым замком.

Недавно Артем проговорился о том, как устроен этот сейф. Чтобы открыть замок сейфа нужен секретный ключ, ключ называется секретным так как состоит из нескольких других ключей.

Вы пришли к Артему в гости и пока он заваривает вам чай решили осмотреть его комнату. Там вы обнаружили ключницу с N ключами. Немного покрутив эти ключи, вы поняли, что каждый из них может трансформироваться в 4 формы.

Именно вам Артем до этого проговорился про устройство своего сейфа. Поэтому вы знаете, что для его открытия нужно объединить K ключей и порядке в котором это нужно сделать.

Попробуйте “чисто теоретически” понять, возможно ли этими ключами открыть сейф. И если это возможно, то как нужно скомбинировать эти ключи.

Формат входных данных

На вход программе в первой строке подаются два целых числа N, K.

Во-второй идут K целых чисел - формы ключей, которые нужно сложить, чтобы открыть сейф.

В следующих N строках перечисляются ключи, каждая строка - 4 целых числа - 4 формы, которые может принять ключ. F₀, ..., F₃

Формат выходных данных

Выходной файл должен содержать последовательность из K различных целых чисел от 1 до N задающих номера ключей для каждого составляющего секретного ключа.

Если решения нет, выходной файл должен содержать единственное число -1.

Ограничения

1 ≤ N, K ≤ 12

0 ≤ F_i ≤ 128

Примеры тестов

5 4
84 69 83 84
65 66 67 68
84 84 84 84
83 84 83 84
67 82 69 84
69 79 82 83

4 5 3 2

9 7
66 97 100 101 114 105 107
72 101 108 108 111
32 116 111 32
97 108 108 32
109 121 32 32
102 97 110 115
32 97 110 100
32 116 111 32
100 117 99 107
102 117 110 115

-1

Задача 5. Супергерой ≡

Условие

Юный супергерой Вася однажды выяснил, что на один из небоскрёбов его города планирует напасть группа из N злодеев. Небоскрёб состоит из M этажей, пронумерованных от 1 до M. Вася прибыл на первый этаж непосредственно перед началом нападения злодеев и приготовился его отражать.

Злодей номер i появляется на этаже f_i через t_i секунд после начала нападения, и начинает творить зло со скоростью одно злое дело в секунду.

Каждую секунду Вася проделывает следующие действия:

1. Если на текущем этаже находятся злодеи, обезвреживает их.
2. Сдвигается вниз или вверх на один этаж по направлению к ближайшему злодею.
3. Если расстояния равны, Вася предпочитает подниматься вверх.
4. Если в текущий момент ни одного активного злодея в небоскрёбе нет, Вася остаётся на текущем этаже.

Требуется определить, сколько злых дел успеют совершить все злодеи в сумме.

Формат входных данных

Входной файл содержит целые числа M N, за которыми следует N пар целых чисел t_i f_i.

Формат выходных данных

Выходной файл должен содержать единственное целое число — количество злых дел.

Ограничения

1 ≤ N ≤ 10⁶

1 ≤ f_i ≤ M ≤ 10⁹

1 ≤ t_i ≤ t_i + 1 ≤ 10⁹

Примеры тестов

3 3
1 2
2 3
5 1

4

100 1
1 100

99

1 1
1 1

0