Информатика

У Васи есть N свинок-копилок, свинки занумерованы числами от 1 до N. Каждая копилка может быть открыта единственным соответствующим ей ключом или разбита.

Вася положил ключи в некоторые из копилок (он помнит, какой ключ лежит в какой из копилок). Теперь Вася собрался купить машину, а для этого ему нужно достать деньги из всех копилок. При этом он хочет разбить как можно меньшее количество копилок (ведь ему еще нужно копить деньги на квартиру, дачу, вертолет…). Помогите Васе определить, какое минимальное количество копилок нужно разбить.

Входные данные
В первой строке содержится число N — количество свинок-копилок (1≤N≤100000). Далее идет N строк с описанием того, где лежит ключ от какой копилки: в i-ой из этих строк записан номер копилки, в которой находится ключ от i-ой копилки.

Выходные данные
Выведите единственное число: минимальное количество копилок, которые необходимо разбить.

Примечание
Ключи от первой и третьей копилки лежат в копилке 2, ключ от второй — в первой, а от четвертой — в ней самой.
Чтобы открыть все копилки, достаточно разбить, например, копилки с номерами 1 и 4.
 

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

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

Вам дан словарь, которым пользовался Вася и домашнее задание, сданное Петей. Ваша задача — определить количество ошибок, которое в этом задании насчитает Вася.

Входные данные
Вводится сначала число N — количество слов в словаре (0≤N≤20000).

Далее идет N строк со словами из словаря. Каждое слово состоит не более чем из 30 символов. Все слова состоят из маленьких и заглавных латинских букв. В каждом слове заглавная ровно одна буква — та, на которую попадает ударение. Слова в словаре расположены в алфавитном порядке. Если есть несколько возможностей расстановки ударения в одном и том же слове, то эти варианты в словаре идут в произвольном порядке.

Далее идет упражнение, выполненное Петей. Упражнение представляет собой строку текста, суммарным объемом не более 300000 символов. Строка состоит из слов, которые разделяются между собой ровно одним пробелом. Длина каждого слова не превышает 30 символов. Все слова состоят из маленьких и заглавных латинских букв (заглавными обозначены те буквы, над которыми Петя поставил ударение). Петя мог по ошибке в каком-то слове поставить более одного ударения или не поставить ударения вовсе.

Выходные данные
Выведите количество ошибок в Петином тексте, которые найдет Вася.

Примечание
1) В слове cannot, согласно словарю возможно два варианта расстановки ударения. Эти варианты в словаре могут быть перечислены в любом порядке (т.е. как сначала cAnnot, а потом cannOt, так и наоборот).
Две ошибки, совершенные Петей — это слова be (ударение вообще не поставлено) и fouNd (ударение поставлено неверно). Слово thE отсутствует в словаре, но поскольку в нем Петя поставил ровно одно ударение, признается верным.
2) Неверно расставлены ударения во всех словах, кроме The (оно отсутствует в словаре, в нем поставлено ровно одно ударение). В остальных словах либо ударные все буквы (в слове PAGE), либо не поставлено ни одного ударения.

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.




Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика).

Входные данные
Вводится число N — количество вагонов в поезде (1 ≤ N ≤ 2000). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N, каждое из которых встречается ровно один раз.

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

если нужно завезти с пути 1 в тупик K вагонов, должно быть выведено сначала число 1, а затем — число K (K≥1),
если нужно вывезти из тупика на путь 2 K вагонов, должно быть выведено сначала число 2, а затем — число K (K≥1).
Если возможно несколько последовательностей действий, приводящих к нужному результату, выведите любую из них.

Если выстроить вагоны по порядку невозможно, выведите одно число 0.

 

Примеры

№	Входные данные	Выходные данные
1	3 3 2 1	1 3 2 3
2	4 4 1 3 2	1 2 2 1 1 2 2 3
3	3 2 3 1	0

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

При этом если у школьника есть двойка, а следующая за ней оценка – не двойка, то двойка считается закрытой, и при вычислении среднего арифметического не учитывается.

Входные данные
Вводится десять натуральных чисел от 2 до 5 через пробел – оценки Васи.

Выходные данные
Выведите натуральное число (от 2 до 5) – его четвертную оценку.

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

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

Вводятся два натуральных числа N (высота доски) и M (ширина доски), не превышающие 100.

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

Выведите последовательность ходов в одном из возможных кратчайших путей. Каждый ход обозначается заглавной латинской буквой:
   U – вверх,
   R – вправо,
   D – вверх и вправо.
Буквы выводятся без пробелов в одной строке.

Требуется расставить в некоторые клетки таблицы 3 x 3 крестики так, чтобы в каждой строке и в каждом столбце было заданное количество крестиков.

Входные данные
Вводятся 6 чисел (от 0 до 3) – требуемое количество крестиков в первом, втором, третьем столбце, в первой, второй, третьей строке.

Выходные данные
Требуется выдать количество возможных таблиц или 0, если таких таблиц нет.

Рассмотрим последовательность целых чисел длины N. По ней с шагом 1 двигается “окно” длины K, то есть сначала в “окне” видно первые K чисел, на следующем шаге в “окне” уже будут находиться K чисел, начиная со второго, и так далее до конца последовательности. Требуется для каждого положения “окна” определить минимум в нём.

Входные данные
В первой строке входных данных содержатся два числа N и K (1 ≤  N ≤  150000, 1 ≤ K ≤ 10000, K ≤  N) – длины последовательности и “окна”, соответственно. На следующей строке находятся N чисел – сама последовательность.

Выходные данные
Выходые данные должны содержать N − K + 1 строк – минимумы для каждого положения “окна”.

Миша заполнял таблицу истинности функции (¬x /\ ¬y) \/ (x≡z) \/  w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				(¬x /\ ¬y) \/ (x≡z) \/ w
1	1			0
		1	0	0
0	1	1	0	0

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Если бы функция была задана выражением ¬x \/ y, зависящим
от двух переменных, а фрагмент таблицы имел бы вид

		¬x \/ y
0	1	0

то первому столбцу соответствовала бы переменная y, а второму столбцу – переменная x. В ответе следовало бы написать yx.
 

Миша заполнял таблицу истинности функции (x \/ ¬y) /\ ¬(x≡z) /\ w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				(x \/ ¬y) /\ ¬(x≡z) /\ w
		0	0	1
1	0	0	1	1
1	0			1

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Если бы функция была задана выражением ¬x \/ y, зависящим
от двух переменных, а фрагмент таблицы имел бы вид

		¬x \/ y
0	1	0

то первому столбцу соответствовала бы переменная y, а второму столбцу – переменная x. В ответе следовало бы написать yx.
 

Миша заполнял таблицу истинности функции (¬x \/ ¬y) /\ ¬(x≡z) /\ w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				(¬x \/ ¬y) /\ ¬(x≡z) /\ w
0	1	1	0	1
0				1
	1	0	0	1

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Если бы функция была задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имел бы вид

		¬x \/ y
0	1	0

то первому столбцу соответствовала бы переменная y, а второму столбцу – переменная x. В ответе следовало бы написать yx.
 

Миша заполнял таблицу истинности функции (¬x /\ ¬y) \/ (y≡z) \/ ¬w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				(¬x /\ ¬y) \/ (y≡z) \/ ¬w
0		0	1	0
	0		1	0
0	1	1		0

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Если бы функция была задана выражением ¬x \/ y, зависящим
от двух переменных, а фрагмент таблицы имел бы вид

		¬x \/ y
0	1	0

то первому столбцу соответствовала бы переменная y, а второму столбцу – переменная x. В ответе следовало бы написать yx.
 

Миша заполнял таблицу истинности функции (¬x \/ ¬y) /\ ¬(y≡z) /\ ¬w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				(¬x \/ ¬y) /\ ¬(y≡z) /\ ¬w
1		0	0	1
	1			1
1	0	1	0	1

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Если бы функция была задана выражением ¬x \/ y, зависящим
от двух переменных, а фрагмент таблицы имел бы вид

		¬x \/ y
0	1	0

то первому столбцу соответствовала бы переменная y, а второму столбцу – переменная x. В ответе следовало бы написать yx.
 

Миша заполнял таблицу истинности функции (¬x /\ ¬y) \/ (y≡z) \/  w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				(¬x /\ ¬y) \/ (y≡z) \/ w
	0	0	1	0
1		1		0
1	0		1	0

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Если бы функция была задана выражением ¬x \/ y, зависящим
от двух переменных, а фрагмент таблицы имел бы вид

		¬x \/ y
0	1	0

то первому столбцу соответствовала бы переменная y, а второму столбцу – переменная x. В ответе следовало бы написать yx.
 

Миша заполнял таблицу истинности функции (¬x /\ ¬y) \/ (x≡z) \/  ¬w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				(¬x /\ ¬y) \/ (x≡z) \/ ¬w
0	1		1	0
1		0	0	0
	1	0		0

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Если бы функция была задана выражением ¬x \/ y, зависящим
от двух переменных, а фрагмент таблицы имел бы вид

		¬x \/ y
0	1	0

то первому столбцу соответствовала бы переменная y, а второму столбцу – переменная x. В ответе следовало бы написать yx.
 

Миша заполнял таблицу истинности функции (¬x /\ ¬y) \/ (y≡z) \/  w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				(¬x /\ ¬y) \/ (y≡z) \/ w
		1		0
0	1		1	0
0	0	1	1	0

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Функция задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

		¬x \/ y
0	1	0

В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать yx.
 

Миша заполнял таблицу истинности функции (¬x /\ ¬y) \/ (x≡z) \/  w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				(¬x /\ ¬y) \/ (x≡z) \/ w
	0	1	1	0
1	0	0		0
1			1	0

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Функция задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

		¬x \/ y
0	1	0

В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать yx.
 

Миша заполнял таблицу истинности функции (x /\ ¬y) \/ (y≡z) \/  ¬w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				(x /\ ¬y) \/ (y≡z) \/ ¬w
		0	0	0
1	0		0	0
1	0	1		0

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Функция задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

		¬x \/ y
0	1	0

В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать yx.
 

Миша заполнял таблицу истинности функции (¬x \/ ¬y) /\ ¬(y≡z) /\ w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				(¬x \/ ¬y) /\ ¬(y≡z) /\ w
	0	0	1	1
0		0		1
1	0		1	1

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Функция задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

		¬x \/ y
0	1	0

В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать yx.
 

Миша заполнял таблицу истинности функции (¬x \/ ¬y) /\ ¬(y≡z) /\ ¬w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				(¬x \/ ¬y) /\ ¬(y≡z) /\ ¬w
	0	0	1	1
1		0		1
0	1		1	1

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Функция задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

		¬x \/ y
0	1	0

В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать yx.
 

Миша заполнял таблицу истинности функции (x \/ ¬y) /\ ¬(y≡z) /\ ¬w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

				(x \/ ¬y) /\ ¬(y≡z) /\ ¬w
1	0		0	1
1		1	0	1
	1	1		1

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы
в ответе пишите подряд, никаких разделителей между буквами ставить
не нужно.
Пример. Функция задана выражением ¬x \/ y, зависящим от двух переменных, а фрагмент таблицы имеет следующий вид.

		¬x \/ y
0	1	0

В этом случае первому столбцу соответствует переменная y, а второму столбцу – переменная x. В ответе следует написать yx.