Задачи из книги "Олимпиадные задачи по программированию"
Ф. Меньшиков

Шестая тренировка

содержание задачника

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

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

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

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

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

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

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

В прямоугольной декартовой системе координат прямая задана двумя принадлежащими ей точками (0, W) и (100N, E). Также заданы N² квадратов со сторонами, параллельными осям координат. Квадрат S_i,j имеет координаты углов (100i,100j) и (100i-100, 100j - 100), i,j= 1,2,...,N. Требуется найти количество квадратов ,имеющих общую точку с прямой.
Ограничения: 1 $\le$ N$\le$ 100, 0 $\le$ W,E$\le$ 100N, все числа целые, время 1 с.
Ввод из файла sqline.in. В первой строке находятся три целых числа, N, W и Е, разделенных пробелами. Вывод в файл sqline.out Вывести одно число — количество квадратов.
Пример
Ввод
3 150 50
Вывод
4

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

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

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

Из прямоугольного листа клетчатой бумаги (М строк, N столбцов) удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.
Ограничения: 1 $\le$ М, N$\le$ 100, время 1 с.
Ввод из файла remsquar.in. В первой строке находятся числа М и N, в следующих М строках — по N символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана — точка. Вывод в файл remsquar.out. Вывести одно число.
Пример
Ввод
4 8
#.##.#.#
......##
#.###.##
Вывод
6

содержание задачника