10970. Большая шоколадка

Необходимо разломать шоколадку размером m ´ n на единичные плитки, сделав при этом минимальное число разломов.

Вход. Каждая строка содержит два числа m и n (1 £ m, n £ 300) – размеры шоколадки.

Выход. Для каждого теста вывести минимальное число разломов, которое требуется для разлома шоколадки на единичные плитки.

Пример входа

2 2

1 1

1 5

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

3

0

4

РЕШЕНИЕ

математика, инвариант

Анализ алгоритма

В процессе разломов шоколадки инвариантным является соотношение:

число кусков = число разломов + 1,

так как при разломе любого куска число разломов и число кусков увеличивается на 1.

Изначально число кусков равно 1 (одна полная шоколадка), число разломов равно нулю. В процессе разломов их число увеличивается на столько же, на сколько увеличивается число кусков. Поэтому для получения m * n единичных кусков необходимо совершить m * n – 1 разломов не зависимо от порядка их совершения.

	число кусков	число разломов
начало	1	0
конец	m * n	m * n – 1

Реализация алгоритма

Для каждой шоколадки размером m на n выводим ответ m * n – 1.

while(scanf("%d %d",&m, &n) == 2)

printf("%d\n",m * n - 1);