| Входной файл: | in | Ограничение времени: | 1 сек | |
| Выходной файл: | out | Ограничение памяти: | 256 Мб | |
| Максимальный балл: | 80 |
Молодожены Аня и Вася решили устроить ремонт на кухне. На семейном собрании было решено, что лучшим половым покрытием для кухни является плитка.
Кухня Ани и Васи представляет собой прямоугольник со сторонами A на B метров. Посетив строительный магазин, Аня и Вася выбрали плитку с интересным узором. Каждая плитка имеет фиксированный размер x на y метров. Для того чтобы пол выглядел аккуратно и красиво, плитку надо класть так, чтобы каждая сторона плитки граничила максимум с одной плиткой и была параллельна одной из сторон кухни. Выбранный узор оказался очень специфическим, поэтому плитки нельзя поворачивать, даже все одновременно – сторона кухни длиной A должна быть всегда параллельна стороне плитки длиной x.
Возможно, плитки придется разрезать на меньшие части с помощью прямолинейных разрезов, параллельных одной из сторон, при этом получившиеся кусочки также можно разрезать на меньшие части.
Аня и Вася хотят сэкономить семейный бюджет и замостить кухню так, чтобы было использовано минимально возможное количество плиток и их частей. Помогите молодоженам выяснить, какое количество плиток размером x на y нужно приобрести, чтобы замостить кухню.
| № | Входной файл (in) |
Выходной файл (out) |
|---|---|---|
| 1 |
|
|
| 2 |
|
|
| 3 |
|
|