#1657

НОД

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2005, Задача F ]

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

Ваша задача найти наибольший общий делитель (НОД) элементов i-й строки, стоящих между единицами.

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

Задано единственное число i (1 < i < 2³¹).

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

Вывести НОД элементов.

Примеры

Входные данные

Выходные данные

Входные данные

Выходные данные

#1658

Гонки

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2005, Задача G ]

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

Двигаться можно только в соседнюю по горизонтали или вертикали свободную клетку (одно перемещение – это переход на соседнюю клетку).
Передвижение осуществляется поочередно: сначала ходит соперник, затем вы.
Не допускаются нахождение обоих участников в одном квадрате одновременно.
Ходы соперников обязательны.
Если ходы соперника закончились, то он останавливается в последней достигнутой им клетке. Но заранее известно, что он при этом не заблокирует возможный путь до финиша. Если соперник достиг финиша, то он исчезает с поля.

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

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

В первой строке размер поля: два числа через пробел 0 < N, М ≤ 150. Далее идет N строк в каждой из которых по M символов, описывающих поле: точка (.) – клетка свободна, решетка (#) – непроходимая клетка. В следующей строке два числа – номер строки и столбца, где находится ваш соперник. Далее следует строка с описанием пути соперника: R – движение вправо, L – влево, U – вверх, D - вниз. Количество ходов соперника не более 32000.

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

Содержит единственное число – минимальное число шагов, необходимое для достижения финиша, в случае невозможности вывести –1.

Примеры

Входные данные

3 5
.....
.#...
.#...
1 4
R

Выходные данные

Входные данные

3 5
.....
.#...
.#...
1 4
LLLRLRRR

Выходные данные

#1659

Клетки

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2005, Задача H ]

На прямоугольной доске назовем непустое множество клеток группой, если они все являются соседями какой-нибудь одной и той же клетки не входящей в это множество. Две клетки соседние, если у них есть хотя бы одна общая точка (то есть по стороне или по диагонали). Таким образом, на доске 1x1 - нет ни одной группы, на доске 1x2 - две группы, на доске 2х2 - 14 групп (рис. 1). Пример множества клеток на доске 3x3, не являющегося группой, приведен на рис. 2. Напишите программу, подсчитывающую количество различных групп на доске

Входные данные

В первой строке заданы числа \(N\) и \(M\). 1 ≤ \(N\) ≤ 1000, 1 ≤ \(М\) ≤ 1000.

Выходные данные

Вывести одно число – количество различных групп для заданной доски.

Примеры

Входные данные

2 2

Выходные данные

Входные данные

1 1

Выходные данные