|
Полцарства в приданое
(Время: 1 сек. Память: 32 Мб Сложность: 48%)
У одного царя было много дочерей. И вот пришло время выдавать замуж старшую. По стародавнему обычаю он должен обеспечить свою родную дочь достатком, поэтому, хочешь не хочешь, а пришлось ему в приданое отдавать полцарства. Далее пришёл черёд выдавать замуж вторую дочь. И этой дочери от оставшегося своего владения он отдал половину. А там уж и пришёл черёд третьей дочери, и так далее...
Исходно, всё его царство имело вид прямоугольника со сторонами n × m единиц, разделённого на клетки со стороной один. Дабы не нарушать кадастровую отчётность, царь имеет право разделить своё царство только по прямой линии от одного края до другого края, линия должна проходить по линии сетки. Образованные два новых прямоугольника должны иметь целые стороны.
Если пополам делится чётная по длине сторона, то есть полученные половины равны, то царь просто отдаёт одну из них в приданное. Однако, если появляется желание (или необходимость) разделить царство по нечётной стороне, то царь делит прямоугольник на как можно более близкие части, отдаёт меньшую часть в приданное, а большую оставляет себе. При этом, он доплачивает в приданное за оставленный у себя излишек сумму, равную этому излишку.
Для примера, если у него было царство 13 × 10, то он может разделить его по чётной стороне на два равных полцарства 13 × 5 и 13 × 5, отдать одну из них в приданное, а вторую оставить себе. Либо разделить по нечётной стороне на два примерно равных прямоугольника 7 × 10 и 6 × 10 и оставить себе большую часть 7 × 10, но тогда он обязан доплатить в приданное разницу, равную 10 единицам, так как эти две части отличаются на эту величину.
Сказка имеет счастливый конец: царь достойно выдал всех своих дочерей замуж и у него даже осталось маленькое царство размера 1 × 1. Но ему и этого хватило. И я там был, мёд-пиво пил...
А вот вам нужно помочь царю: найти минимальную возможную величину, которую он суммарно был должен доплатить в процессе дележа.
Входные данные
В первой строке входного файла INPUT.TXT записаны два целых числа N и M через пробел — размеры исходного царства (1 ⩽ N, M ⩽ 250).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число — минимальную сумму, которую придётся доплатить царю для обеспечения справедливости дележа.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 13 10 | 12 |
| 2 | 17 7 | 19 |
Замечание
В первом примере из условия царю следует действовать следующим образом:
- выдавая первую дочь, разделить своё царство 13 × 10 ровно пополам и отдать половину 13 × 5, доплата 0;
- выдавая вторую дочь, разделить своё царство 13×5 на два 7×5 и 6×5, отдать второе и доплатить разницу 5;
- выдавая третью дочь, разделить своё царство 7×5 на два 4×5 и 3×5, отдать второе и доплатить разницу 5;
- выдавая четвёртую дочь, разделить своё царство 4 × 5 ровно пополам и отдать половину 2 × 5, доплата 0;
- выдавая пятую дочь, разделить своё царство 2 × 5 ровно пополам и отдать половину 1 × 5, доплата 0;
- выдавая шестую дочь, разделить своё царство 1 × 5 на два 1 × 3 и 1 × 2, отдать второе и доплатить разницу 1;
- выдавая седьмую дочь, разделить своё царство 1 × 3 на два 1 × 2 и 1 × 1, отдать второе и доплатить разницу 1;
- выдавая восьмую дочь, разделить своё царство 1 × 2 ровно пополам и отдать половину 1 × 1, доплата 0.
В итоге у царя останется царство размерами 1 × 1 и он суммарно доплатит 12. Можно показать, что это минимально возможная доплата.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
