Задача 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. Lines 1 ≡

Условие

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

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

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

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

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

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

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

10

Задача 3. Урок ИЗО ≡

Условие

Петя пришел в на урок изобразительного искусства. Там ему выдали 3 100-миллилитровых банки с красками разных цветов. Цвет краски задается 3 целыми числами r, g и b- ее насыщенностью красного, зеленого и синего соответственно. Учительница задала Пете смешать краски так, чтобы получить 100мл краски цвета r_x, g_x, b_x.

Краски смешиваются следующим образом:

Пусть есть a₁ миллилитров краски цвета r₁, g₁, b₁ и a₂ миллилитров краски цвета r₂, g₂, b₂. Тогда новая краска будет иметь объем a₁ + a₂ мл, а ее красный цвет будет вычисляться по формуле a₁ r₁ + a₂ r₂a₁ + a₂. Зеленый и синий цвета вычисляются аналогично.

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

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

В первой строчке располагаются 3 целых числа - r₁, g₁, b₁ - цвета первой краски.

Во второй - r₂, g₂, b₂ - цвета второй краски

В третьей - r₃, g₃, b₃ - цвета четвертой краски

В последней строчке располагаются три целых числа r_x, g_x, b_x - цвет результирующей краски.

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

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

Ограничения

Все числа целые и неотрицательные.

r₁ + g₁ + b₁ = 255

r₂ + g₂ + b₂ = 255

r₃ + g₃ + b₃ = 255

r_x + g_x + b_x = 255

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

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

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

255 0 0
0 255 0
0 0 255
100 55 100

39 21 39

255 0 0
0 255 0
0 0 255
255 0 0

100 0 0

55 100 100
100 55 100
100 100 55
80 80 95

44 44 11

55 100 100
100 55 100
100 100 55
80 60 115

-1

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

Условие

Юный супергерой Вася однажды выяснил, что на один из небоскрёбов его города планирует напасть группа из 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

Задача 5. Забытое число ≡

Условие

Денис перед сном придумал очень замечательное число, но на утро забыл его. Он помнит лишь, что наибольший общий делитель всех цифр числа равен d, а наименьшее общее кратное всех цифр числа равно k. Также, Денис себя хорошо знает и уверен, что он бы выбрал наименьшее число, которое больше l. Помогите Денису вспомнить это число.

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

В строке записано три целых числа d, k и l — наибольший общий делитель всех цифр числа, наименьшее общее кратное все цифр числа и число-ограничение соответственно.

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

Выведите единственное число — наименьшее число, большее l, которое имеет наибольший общий делитель цифр числа равный d и наименьшее общее кратное равное k.

Ограничения

1 ≤ d ≤ 9

1 ≤ k ≤ 2520

1 ≤ l ≤ 10⁷

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

1 42 441

617