Задача №1104. Лампочки
Есть прямоугольная таблица размером NxM клеток. В каждой клетке таблицы находится лампочка. Изначально все лампочки выключены.
Разрешается за одну операцию выбрать какую-нибудь прямоугольную область этой таблицы, один из углов которой находится в клетке (1,1) и изменить состояние всех лампочек в этой области (включенные лампочки – выключаются, выключенные – включаются).
Требуется сделать так, чтобы лампочки в этой таблице горели в шахматном порядке. При этом допускается получить любой из вариантов: как тот, в котором лампочка в клетке (1,1) выключена, так и тот, в котором она включена.
Напишите программу, которая по размерам таблицы определит минимальное количество операций, за которое можно получить требуемую конфигурацию.
Во входном файле записаны два числа N и M, задающие размеры таблицы. 1≤N≤100000, 1≤M≤100000.
В выходной файл выведите одно число – минимальное количество операций, с помощью которого из всех выключенных лампочек можно получить конфигурацию, когда лампочки горят в шахматном порядке.
Пояснение ко второму примеру (показан один из возможных вариантов):
| ∙ | ∙ |
| * | ∙ |
| ∙ | * |
| ∙ | ∙ |
| * | ∙ |
| * | ∙ |
| Начальное состояние – все лампочки выключены |
| Первая операция – переключаются все лампочки в выделенном прямоугольнике |
| Вторая операция – переключаются все лампочки в выделенном прямоугольнике. В итоге получается «шахматная» конфигурация. | |||
1 2
1
2 2
2