Первый тур

Всем участникам даётся 80 минут и 9 попыток на решение данного набора задач. Объём памяти, предоставляемый программе, составляет 64M, время на выполнение одного теста - 1 секунда.
Задачи первого тура подобраны Фёдором Меньшиковым (Вологда).


        Задача 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) и (100NE). Также заданы N 2 квадратов со сторонами, параллельными осям координат. Квадрат Si, j имеет координаты углов (100i, 100j) и (100i - 100, 100j - 100), ij = 1, 2, ..., N. Требуется найти количество квадратов, имеющих общую точку с прямой.
Ограничения: 1 <= N <= 100, 0 <= WE <= 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 <= MN <= 100, время 1 с.
Ввод из файла remsquar.in. В первой строке находятся числа M и N, в следующих M строках - по N символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка.
Вывод в файл remsquar.out. Вывести одно число.
Примеры
Ввод 1
4 8
#.##.#.#
......##
#.###.##
##.##.##
Вывод 1
6