К содержимому

Алгоритм Евклида 02

Опубликована · Обновлена: 12.10.2026 02:18

Автор: Александр Смирнов · Редакторы: Юрий Карпенко

Условие

У Кирилла есть клетчатый лист бумаги $6 \times 39$ клеточек. 6 по вертикали, 39 по горизонтали. За один ход Кирилл вертикальным разрезом отрезает от своего листа $a \times b$, где $a<b$ квадрат со стороной $a$. Он повторяет ходы, пока у него не останется прямоугольник, у которого вертикальная сторона больше горизонтальной, или квадрат. В первом случае Кирилл поворачивает прямоугольник и продолжает ходы. Во втором заканчивает игру. Сколько ходов сделает Кирилл до тех пор, пока первый раз не перевернет прямоугольник?