Задачи на моделирование

В новой модели сотового телефона разработчики предусмотрели только 5 кнопок: «стрелка вверх», «стрелка вниз», «стрелка вправо», «стрелка влево» и «Ok». Чтобы набрать номер телефона, на экран выводится виртуальная клавиатура в виде такой таблицы:
 

1	2	3
4	5	6
7	8	9
выход	0	звонок

По ячейкам этой таблицы пользователь телефона может перемещать курсор вверх, вниз, вправо или влево. Для выбора цифры необходимо нажать кнопку «Ok». После набора всех цифр пользователь должен подвинуть курсор на ячейку «звонок» и нажать «Ok». Таблица не «зациклена» (это означает, что нажатие кнопки «вправо», например, из ячейки с цифрой 6 не приведет к перемещению курсора).

При вызове экранной клавиатуры курсор находится на кнопке с надписью «выход».

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

Входные данные
Во входном файле задан номер телефона, содержащий ровно 7 цифр.

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

Примеры

№	Входные данные	Выходные данные
1	0800000	12
2	1234567	24

В этой задаче мы снова возвращаемся в младшую группу детского сада «Телепузики». Чтобы окончательно успокоить детей, воспитательница решила включить им мультик про Тома и Джерри. Серия, которую сейчас смотрят дети, довольно-таки незамысловата — в ней Джерри развесил по потолку комнаты наковальни на веревках. Когда Том оказывается под очередной наковальней, Джерри перерезает веревку. Наковальня падает на Тома, Тому больно, всем остальным весело, дети смеются. В общем, вполне обычная серия.

А вам нужно по кадру из этой серии определить, упадет ли наковальня на Тома, если Джерри перережет веревку.

Входные данные
Вам дана ASCII-арт картинка, то есть картинка, нарисованная символами. На ней есть наковальня, привязанная веревкой к потолку, и кот Том. В первой строке даны числа N, M (4≤N≤100, 1≤M≤100 ). Следующие N строк состоят из M символов каждая, и представляют собой саму картинку. Картинка устроена следующим образом:

• Первые K₁ строк в одной и той же позиции X₁ стоит символ «|», в остальных — пробел. Это веревка.
• Следующие K₂ строк в одних и тех же позициях с X₂ по X₃ стоит символ «#», в остальных — пробел. Это наковальня.
• 2×X₁=X₂+X₃, то есть наковальня подвешена за середину.
• Следующие K3 строк содержат только пробелы. Это пустота между наковальней и котом.
• Следующие N − K₁ − K₂ − K₃ строк содержат произвольные символы. Любой символ, кроме пробела — часть кота. Существует хотя бы один непробельный символ.

Числа K₁, K₂, K₃ и N − K₁ − K₂ − K₃  ненулевые.
Выходные данные
Выведите «YES», если при падении наковальня заденет Тома, в противном случае выведите «NO».
 

Примеры

№	Входные данные	Выходные данные
1	13 29 | | | ############# ############# ############# /\_/\ >^.^<.---. _'-`-' )\ (6--\ |--\ (`.`-. --' --' ``-'	YES
2	16 30 | ####### ####### ####### ####### , \)\_ / '. .---._ =P ^ ` '. `--. / \ .-'( \ | (.-' )-..__> , ; (_.--`` (__.-/ / .-.__.-'.' '-...-'	NO

В свободное от программирования время Вася увлекается экспериментами, и его любимый — переливание воды между колбами. У него есть две колбы размером a и b миллилитров соответственно, и неограниченное количество воды. Вася может производить с ними следующие действия:

•  Налить воду в первую колбу до края (после этого в ней будет a миллилитров воды)
•  Полностью вылить воду из первой колбы
•  Налить воду во вторую колбу до края (после этого в ней будет b миллилитров воды)
•  Полностью вылить воду из второй колбы
•  Перелить воду из первой колбы во вторую. В этом случае, если во второй колбе достаточно места, чтобы уместить всю текущую воду первой колбы, вода из первой колбы переливается полностью во вторую. Если же во второй колбе места недостаточно, вторая колба заполняется до предела (в ней после этого будет b миллилитров воды), а в первой колбе остается все остальное.

Состоянием колб Вася называет упорядоченную пару (x, y), где x — текущее количество воды в первой колбе, а y— во второй. Вася хочет изучить поставленную самим собой задачу и понять, сколько различных состояний он может получить описанными выше переливаниями.
Входные данные
В единственной строке входного  через пробел записаны два натуральных числа a и b (1 ≤ a, b ≤ 100) — емкости первой и второй колбы соответственно.
Выходные данные
В единственной строке выходного выведите одно число — число различных состояний, которое можно получить описанными в задаче переливаниями воды.
 

Ввод	Вывод
2 5	14

Лифт

GLaDOS приготовила для Челл новое, последнее испытание! В его рамках ей предстоит найти торт. Но всё не так-то просто — у неё отобрали портальную пушку и завязали глаза. Единственное, что Челл известно, — что она находится в прямоугольной комнате, выложенной квадратной плиткой, и что где-то в этой комнате расположен торт. Всё что остаётся делать Челл, — слепо переходить с плитки на плитку в поисках торта.

Кроме того, так как действие происходит в Лаборатории Исследования Природы Порталов, на каждой стене комнаты расположен портал, связанный с противоположной стеной. Формально: рас- смотрим комнату как прямоугольную сетку размера W × H и введем систему координат так, чтобы левая нижняя ячейка сетки имела координаты (0, 0), а правая верхняя — (W − 1, H − 1). За один шаг Челл может перейти в одну из четырёх соседних ячеек, причём попытка пройти сквозь стену приводит к тому, что Челл появляется с противоположной стороны комнаты. Например, шаг вниз из ячейки (x, 0) приведёт в ячейку (x, H −1), а шаг влево из ячейки (0, y) приведёт в ячейку (W −1, y).

Чтобы сделать испытание сложнее, GLaDOS не сообщила Челл ни размеры комнаты, ни коорди- наты её изначального положения, ни координаты торта. Более того, так как у Челл завязаны глаза, а портальная технология достигла совершенства в своём развитии, Челл даже не может определить, прошла ли она очередным ходом через портал или нет.

Челл может найти торт, только оказавшись в одной клетке с ним. Помогите ей пройти последнее испытание! Формат взаимодействия с тестирующей системой Это интерактивная задача. Ваша программа будет общаться с тестирующей системой по протоколу, описанному ниже. Вам разрешается произвести не более 200 000 ходов. Чтобы переместиться в соседнюю ячейку, выведите строку, содержащую ровно один символ, задающий направление перемещения: «U» — вверх; «D» — вниз; «L» — влево; «R» — вправо. Затем вы должны считать строку, в которой будет находиться ровно один символ, обозначающий результат перемещения: • «Y» — после произведённого хода Челл оказалась в клетке с тортом; • «N» — после произведённого хода Челл оказалась в клетке, не содержащей торт; • «E» — служебный символ, обозначающий, что после произведённого хода Челл всё ещё не нашла торт, а ваша программа превысила ограничение на количество ходов. Обратите внимание, после считывания символа «Y» или «E» вы обязательно должны сразу завершить вашу программу. В противном случае, вердикт тестирующей системы может быть некор- ректным! Гарантируется, что в клетке, в которой исходно находится Челл, нет торта. В точности соблюдайте формат выходных данных. После вывода каждой строки сбрасы- вайте буфер вывода — для этого используйте команды flush(output) на языке Паскаль или Delphi, fflush(stdout) или cout.flush() в C/C++, sys.stdout.flush() на языке Python, System.out.flush() на языке Java.