|
Олимпиады прошлых лет
|
||||||||||||||||||||||||||||||
|
Олимпиада проводится при поддержке Компьютерного супермаркета "НИКС" и компании Genius
Информационная поддержка:
журнал "Мир ПК"
II Всероссийская заочная олимпиада школьников по информатике, 2007/08 учебный год
Задача H. Лампочки (OFF-LINE проверка)
| Имя входного файла: | h.in |
| Имя выходного файла: | h.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Есть прямоугольная таблица размером NxM клеток. В каждой клетке таблицы находится лампочка. Изначально все лампочки выключены.
Разрешается за одну операцию выбрать какую-нибудь прямоугольную область этой таблицы, один из углов которой находится в клетке (1,1) и изменить состояние всех лампочек в этой области (включенные лампочки - выключаются, выключенные - включаются).
Требуется сделать так, чтобы лампочки в этой таблице горели в шахматном порядке. При этом допускается получить любой из вариантов: как тот, в котором лампочка в клетке (1,1) выключена, так и тот, в котором она включена.
Напишите программу, которая по размерам таблицы определит минимальное количество операций, за которое можно получить требуемую конфигурацию.
Формат входных данных
Во входном файле записаны два числа N и M, задающие размеры таблицы. 1≤N≤100000, 1≤M≤100000.
Формат выходных данных
В выходной файл выведите одно число - минимальное количество операций, с помощью которого из всех выключенных лампочек можно получить конфигурацию, когда лампочки горят в шахматном порядке.
Примеры
| h.in | h.out |
1 2 |
1 |
2 2 |
2 |
Пояснение ко второму примеру (показан один из возможных вариантов):
 |
 |
 |
| Начальное состояние - все лампочки выключены | Первая операция - переключаются все лампочки в выделенном прямоугольнике | Вторая операция - переключаются все лампочки в выделенном прямоугольнике. В итоге получается "шахматная" конфигурация. |