На бумаге нарисовали клетчатое поле NxM клеток. В каждой клетке нарисовали стрелочку в одном из четырех направлений «вправо», «вверх», «влево» или «вниз».
| ← | → | → | ↓ | ↑ |
| → | ↑ | ↓ | ← | → |
| ↓ | ↑ | → | → | ↓ |
| → | ↑ | ← | ← | ← |
| ← | → | ↓ | ↓ | ↓ |
| ↑ | ↑ | ← | ↓ | ↑ |
Дальше в некоторую клетку этого поля ставят фишку. Затем эту фишку сдвигают в соседнюю клетку в направлении стрелочки, нарисованной в клетке, где стоит фишка. Затем ее снова сдвигают по стрелке, нарисованной в той клетке, где она оказалась. Так продолжается до тех пор, пока фишка не окажется за пределами поля. Однако возможно, что фишка будет бесконечно ходить по полю и никогда не выйдет за его пределы.
Напишите программу, которая по заданному полю определит количество клеток, начав с которых фишка никогда не покинет пределы поля.
Во входном файле заданы сначала размеры поля – число строк N и число столбцов M (1≤N≤1000, 1≤M≤1000). Далее идет N строк по M чисел в каждой, задающих направления стрелочек в клетках. Число 1 обозначает стрелочку вправо, 2 – вверх, 3 – влево, 4 – вниз. Числа в строке разделяются пробелами.
В выходной файл выведите одно число – количество клеток, начав с которых фишка никогда не покинет пределы поля.
Комментарии к примерам тестов.
Пример №1.Соответствует приведенному рисунку. Клетки, начавс которых, фишка никогда не покинет пределов поля на рисунке выделены серым цветом.
6 5 3 1 1 4 2 1 2 4 3 1 4 2 1 1 4 1 2 3 3 3 3 1 4 4 4 2 2 3 4 2
23
2 2 1 2 3 4
0
На плоскости дано N горизонтальных отрезков. Будем говорить, что прямая пересекает отрезок, если у этой прямой и этого отрезка есть хотя бы одна общая точка (в том числе прямая пересекает отрезок, если она проходит через один из его концов). Требуется найти прямую, пересекающую все отрезки, или установить, что такой нет.>
В первой строке входного файла находится единственное число N. В каждой из следующих N строк содержатся по три целых числа Pi, Qi, Ri, описывающих отрезки: соответствующий отрезок соединяет точки (Pi, Ri) и (Qi, Ri). Никакие два отрезка не лежат на одной прямой.
1≤N≤10000, Pi<Qi, все числа по модулю не превосходят 10000.
В случае, если искомая прямая существует, выведите в выходной файл коэффициенты ее уравнения (будем задавать прямую уравнением вида A∙x+B∙y+C=0, где x, y – координаты точек прямой, A, B, C – такие коэффициенты, что указанному уравнению удовлетворяют все точки прямой, и только они; соответственно, чтобы задать прямую, нужно задать три числа – A, B, C).
Коэффициенты уравнения должны быть целыми и не должны превосходить по модулю 109 (гарантируется, что при наличии решения такие A, B, C существуют).
Если прямой не существует, выведите в выходной файл сообщение “No solution” (без кавычек).
3 0 1 0 0 1 1 0 1 2
1 0 0
5 0 2 0 2 4 1 1 3 2 1 3 -1 1 3 -2
3 -1 -5
3 0 1 0 1 2 1 -2 -1 2
No solution
Заданы целые числа X, Y, P, Q (–10100 <= X, Y, P, Q <= 10100). Требуется проверить равенство XY = PQ. Напомним, что ab определяется следующим образом:
Во входном файле записаны числа X, Y, P, Q, каждое в отдельной строке.
Выведите слово correct, если данное равенство для полученных входных данных выполняется, или incorrect, если равенство не выполняется, или хотя бы одна из степеней не определена.
2 4 4 2
correct
2 3 3 2
incorrect
Вася и Петя играют в увлекательную игру. Вася выписал подряд числа от 1 до N. А Петя выписал P пар чисел (Ai, Bi).
Теперь Вася преобразует имеющуюся последовательность чисел - он меняет местами числа в этой последовательности. Если некоторая пара чисел (Ai, Bi) выписана Петей, то Вася имеет право в любой момент взять числа из последовательности, стоящие на местах Ai и Bi и поменять их местами.
Например, если N=5. Тогда изначально Васей выписана последовательность
1 2 3 4 5
Пусть Петя написал две пары чисел: (1,2) и (2,5). Тогда Вася в любой момент может менять числа, стоящие на 1 и 2 местах, или же числа, стоящие на 2 и 5 местах.
Например, он может последовательно получить следующие последовательности:
2 1 3 4 5 (поменяв числа на 1 и 2 местах)
2 5 3 4 1 (поменяв числа на 2 и 5 местах)
5 2 3 4 1 (поменяв числа на 1 и 2 местах).
Пете не показываются промежуточные последовательности, а выписывается лишь полученная на последнем шаге.
От Пети требуется проверить, мог ли Вася получить такую последовательность не нарушая правил игры, и если мог, то указать, в результате какой последовательности обменов (при этом не требуется, чтобы число обменов было минимально возможным).
Напишите программу, которая поможет Пете справиться с этой задачей.
Сначала записано число N (1≤N≤100) – количество чисел в последовательности. Дальше идет N чисел – последовательность, полученная Васей (в последовательности каждое из чисел от 1 до N встречается ровно один раз).
Далее идет число P (0≤P≤10000) – количество пар чисел, выписанных Петей. Далее записано P пар чисел (каждое число пары – из диапазона от 1 до N).
В первую строку выходного файла выведите сообщение YES (если такая последовательность могла быть честно получена Васей) и NO (если такую последовательность Вася не мог получить, не нарушая правил игры).
В случае, если такая последовательность могла быть получена, далее выведите способ ее получения (если вариантов несколько, выведите любой из них). Сначала выведите число K – количество операций обмена (оно не должно превышать 100000), а затем K пар чисел, задающих номера мест, на которых стоят обмениваемые элементы (числа в паре могут быть выданы в любом порядке). Гарантируется, что если решение существует, то существует решение с числом обменов, не превышающим 100000.
5 5 2 3 4 1 2 1 2 2 5
YES 3 1 2 2 5 1 2
5 2 3 4 5 1 2 1 2 2 5
NO
SMS-сообщения на мобильном телефоне марки MOBILO набираются только заглавными английскими буквами. Для набора буквы нужно нажать кнопку, на которой эта буква написана, при этом если эта буква написана первой, то кнопку нужно нажать один раз, если второй – то два раза и т.д. Устройство клавиатуры телефона приведено на рисунке. 
Таким образом, чтобы набрать слово SMS, нужно нажать следующие кнопки:
<PQRS> <PQRS> <PQRS> <PQRS> <MNO> <PQRS> <PQRS> <PQRS> <PQRS>
Для набора двух букв, которые находятся на одной кнопке, при наборе нужно сделать паузу между их вводом. Например, чтобы набрать BA, нужно два раза нажать кнопку <ABC>, затем сделать паузу и затем нажать кнопку <ABC> еще раз.
Если на кнопке написано три буквы, то как только эта кнопка нажата три раза подряд, последняя из написанных на ней букв сразу же добавляется в сообщение, а дальнейшие нажатия на эту кнопку воспринимаются как ввод следующей буквы. То же самое, если на кнопке написано 4 буквы. Таким образом, 4-х кратное нажатие на кнопку <ABC>, затем пауза, и затем нажатие на эту кнопку еще раз приведет к вводу текста CAA.
К сожалению, в силу произошедшего глюка, телефон стал иногда игнорировать паузы при вводе, а, иногда, наоборот, вести себя так, как будто была пауза тогда, когда паузы не было. Например, при вводе слова MOSCOW могло в итоге (как один из вариантов) получиться слово OMSCMNW.
Вы получили SMS-сообщение, набранное на этом телефоне. Известно, что изначально оно состояло из N символов. Напишите программу, которая определит количество вариантов исходных сообщений, которые при вводе могли превратиться в то, что вы получили (если вариантов окажется 0, то это будет означать, что у телефона сломалось что-то еще).
Сначала записана длина исходного сообщения N (1≤N≤80). Вторая строка содержит полученное SMS-сообщение – последовательность не более чем из 80 заглавных латинских букв.
Выведите одно число – количество вариантов исходного сообщения.
4 MAMA
1
2 WWW
2
10 MAMA
0