Тренировка S07

Тренировка S07
Время тестирования приведено для Intel Celeron 400.
Решения должны быть представлены на Turbo Pascal 7.0. Объём памяти, предоставляемый программе, составляет 500 кб.

Задача A. Упорядоченные дроби

Вывести в порядке возрастания все несократимые дроби, заключённые между 0 и 1, знаменатели которых не превышают N.
Ограничения: 2 <= N <= 255, время 1 с.
Ввод из файла ordfrac.in. В первой строке находится единственное число N.
Вывод в файл ordfrac.out. В каждой строке выводится дробь.
Примеры

Ввод 1
5
Вывод 1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5

Задача B. Сообщение

В сообщении, состоящем из одних русских букв и пробелов, каждую букву заменили её порядковым номером в русском алфавите (А - 1, Б - 2, ..., Я - 33), а пробел - нулем. Требуется по заданной последовательности цифр найти количество исходных сообщений, из которых она могла получиться.
Ограничения: цифр не более 100, время 1 с.
Ввод из файла message.in. В первой строке содержится последовательность цифр.
Вывод в файл message.out. Вывести одно число.
Примеры

Ввод 1
1025
Вывод 1
4

Задача C. Игра умножения

Слава и Оля играют в игру умножения - умножают целое число P на одно из чисел от 2 до 9. Слава всегда начинает с P = 1, делает умножение, затем число умножает Оля, затем Слава и т.д. Перед началом игры им задают случайное число N, и победителем считается тот, кто первым получит P >= N. Определить, кто выиграет при заданном N, если оба играют наилучшим образом.
Ограничения: 2 <= N <= 4 294 967 295, время 1 с.
Ввод из файла multgame.in. В первой строке находится единственное число N.
Вывод в файл multgame.out. Выводится одна строка - "Stan wins.", если победит Слава, или "Ollie wins.", если победит Оля.
Примеры

Ввод 1       Ввод 2       Ввод 3
162          17           34012226
Вывод 1      Вывод 2      Вывод 3
Stan wins.   Ollie wins.  Stan wins.

Задача D. Прямая и квадраты

В прямоугольной декартовой системе координат прямая задана двумя принадлежащими ей точками (0, W) и (100N, E). Также заданы N² квадратов со сторонами, параллельными осям координат. Квадрат S_{i, j} имеет координаты углов (100i, 100j) и (100i - 100, 100j - 100), i, j = 1, 2, ..., N. Требуется найти количество квадратов, имеющих общую точку с прямой.
Ограничения: 1 <= N <= 100, 0 <= W, E <= 100N, все числа целые, время 1 с.
Ввод из файла sqline.in. В первой строке находятся три целых числа, N, W и E, разделённых пробелами.
Вывод в файл sqline.out. Вывести одно число - количество квадратов.
Примеры

Ввод 1
3 150 50
Вывод 1
4

Задача E. Lines (2)

В таблице из N строк и N столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и если возможно, то найти путь из наименьшего количества шагов.
Ограничения: 2 <= N <= 250, время 1 с.
Ввод из файла lines2.in. В первой строке находится число N, в следующих N строках - по N символов. Символом точки обозначена свободная клетка, латинской заглавной O - шарик, @ - исходное положение шарика, который должен двигаться, латинской заглавной X - конечное положение шарика.
Вывод в файл lines2.out. В первой строке выводится Y, если движение возможно, или N, если нет. Если движение возможно, далее следует N строк по N символов - как и на вводе, но X, а также все точки по пути заменяются плюсами +.
Примеры

Ввод 1    Ввод 2    Ввод 3
5         5         5
....X     ..X..     ...X.
.OOOO     .....     .....
.....     OOOOO     O.OOO
OOOO.     .....     .....
@....     ..@..     ....@
Вывод 1   Вывод 2   Вывод 3
Y         N         Y
+++++               ..++.
+OOOO               .++..
+++++               O+OOO
OOOO+               .++++
@++++               ....@

Задача F. Удаление клеток

Из прямоугольного листа клетчатой бумаги (M строк, N столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.
Ограничения: 1 <= M, N <= 100, время 1 с.
Ввод из файла remsquar.in. В первой строке находятся числа M и N, в следующих M строках - по N символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка.
Вывод в файл remsquar.out. Вывести одно число.
Примеры

Ввод 1
4 8
#.##.#.#
......##
#.###.##
##.##.##
Вывод 1
6