Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2221. Разбиение на квадраты
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 29/03/2015 | Открытые командные соревнования по спортивному программированию ( 9) |
| 31/03/2015 | Занятие 19 (дорешивание соревнований PRIME TIME) ( 9) |
| 10/07/2019 | Лето 2019 - 5 (E) |
| 05/03/2024 | Динамическое программирование 2 (проводит BOGAT) (E) |
| 29/11/2024 | ICPC Bedolagi (проводит BOGAT) (G) |
Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
При создании макета сайта Тим предпочитает разбивать страницу на квадратные области.
Определите, на какое наименьшее количество квадратных областей с целыми размерами можно разбить страницу
заданного размера, если необходимо, чтобы для найденного разбиения выполнялось свойство разделяемости.
Разбиение части или всей страница обладает свойством разделяемости, если выполняется одно из двух условий:
- часть (или вся) страница имеет форму квадрата и соответствует одной квадратной области;
- существует горизонтальная или вертикальная линия, проходящая полностью по границам областей, расположенных в этой части (или всей) страницы, которая делит её на две части, разбиение которых также обладает свойством разделяемости.
Макет сайта, обладающего свойство разделяемости, можно определить, задавая только размеры, выравнивание и вложенность частей страницы, т. е. более простым образом, чем макет сайта, не обладающего таким свойством.
Формат ввода
Ввод содержит два целых числа `W` и `H` (`1\ ≤\ W,\ H\ ≤\ 400`) – размеры страницы.
Формат вывода
Вывести одно целое число – наименьшее количество квадратных областей.
Пример ввода
12 10
Пример вывода
5
