25/04/2024 15:56:22

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

2221. Разбиение на квадраты

Ограничения: время – 1000ms/2000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

При создании макета сайта Тим предпочитает разбивать страницу на квадратные области. Определите, на какое наименьшее количество квадратных областей с целыми размерами можно разбить страницу заданного размера, если необходимо, чтобы для найденного разбиения выполнялось свойство разделяемости.

Разбиение части или всей страница обладает свойством разделяемости, если выполняется одно из двух условий:

часть (или вся) страница имеет форму квадрата и соответствует одной квадратной области;
существует горизонтальная или вертикальная линия, проходящая полностью по границам областей, расположенных в этой части (или всей) страницы, которая делит её на две части, разбиение которых также обладает свойством разделяемости.

Макет сайта, обладающего свойство разделяемости, можно определить, задавая только размеры, выравнивание и вложенность частей страницы, т. е. более простым образом, чем макет сайта, не обладающего таким свойством.

Формат ввода

Ввод содержит два целых числа `W` и `H` (`1\ ≤\ W,\ H\ ≤\ 400`) – размеры страницы.

Формат вывода

Вывести одно целое число – наименьшее количество квадратных областей.

Пример ввода

12 10

Пример вывода

29/03/2015	Открытые командные соревнования по спортивному программированию ( 9)
31/03/2015	Занятие 19 (дорешивание соревнований PRIME TIME) ( 9)
10/07/2019	Лето 2019 - 5 (E)
12/11/2021	Контест №4* Базовая подготовка (проводит BOGAT) (D)
07/02/2022	Тренировка (динамическое программирование) (проводит BOGAT) (D)
02/03/2023	Базовый уровень: динамическое программирование 2 (проводит BOGAT) (E)
05/03/2024	Динамическое программирование 2 (проводит BOGAT) (E)