Левые повороты(#1031) Прицельное метание помидор(#1033)
#1032

Задача g6_1032: Почти Крэг Туми (DOOI)
Составить программу, которая будет находить, на сколько квадратов, стороны котоых выражены натуральными числами, можно разрезать данный прямоугольник, если от него каждый раз отрезается квадрат максимально большой площади.
Формат входных данных:
Входной файл input.txt состоит из одной строки, содержащей два натуральных числа - стороны прямоугольника.
Формат выходных данных:
Выходной файл output.txt содержит одно число - количество квадратов
input.txt:
3 4
6 4
output.txt:
3
Решение g6_1032:
А вам слабо решить эту задачу с листом бумаги, ножницами, без компьютера и с завязанными глазами? А сделать тоже самое без ножниц и с компьютером?! Мне слабо.
Обозначим стороны прямоугольника за A и B. Сделаем так, чтобы A было больше B (например с помощью процедуры swap, как в задаче 1001. Теперь заведем переменную C, в которой будет храниться количество квадратиков. Будем повторять следующие действия пока одна из сторон (B) не станет равна 0:
1) B меньше чем A, следовательно надо откромсать сколько можем квадратов B*B от прямоугольника A*B. Т.е. C := C + A div B;
2) Вычислим размеры останков прямоугольника: A := A mod B (не смогли отрезать).
3) swap(A, B)!!!!!
Все!

Наверх