Олимпиадные задачи по информатике

[The Godfather]

2005-2006г., Школьная олимпиада, г.Н.Новгород

Задача 1. "Прямоугольник". 15 баллов

Прямоугольник, стороны которого выражены целыми числами m и n (m,n < 100), разделен на квадраты размером 1х1. Составить программу, которая находит число квадратов, пересекаемых диагональю прямоугольника (перескает, только тогда, когда делит его на две части).
Пример 1: m = 5 n = 3, ответ = 7.
Пример 2: m = 10 n = 6, ответ = 14.

Задача 2. "Делимость". 20 баллов

Два числа вводятся двоичным представлением своих цифр, причем первое содержит не более 72 двоичных знаков, а второе, меньшее, - не более 14. Проверить, делится ли первое число на второе.
Пример 1: 11100111000111000111111111:111 - делится
Пример 2: 1110010100011100011111111:1110 - не делится

Задача 3. "Кенгуру". 25 баллов

Перед кенгуру дорожка длиной k у.е., по которой она может двигаться прыжками только вперед. Длина прыжка кенгуру 1, 2, 3, 4, 5 или 6 у.е. Найти число различных вариантов преодоления дорожки, если k < 32.
Пример 1: k = 5, ответ = 8
Пример 2: k = 8, ответ = 125