Олимпиады по программированию

olympiads.ru

Олимпиады прошлых лет
2020/21
2019/20
2018/19
2017/18
2016/17
2015/16
2014/15
2013/14
2012/13
2011/12
2010/11
2009/10
2008/09
2007/08
2006/07

II Всероссийская заочная олимпиада школьников по информатике (2007/08)
Документы
Информация об олимпиаде
Обращение к организаторам региональных олимпиад
Регионы, участвующие в олимпиаде
Задачи и результаты
Задачи
Результаты олимпиады
Проверка решений на похожесть
Информация о проверке
Регистрация, изменение регистрационных данных
Персональная страничка участника
Текущие результаты
FAQ по работе с тестирующей системой
Связаться с оргкомитетом

Олимпиада проводится при поддержке Компьютерного супермаркета "НИКС" и компании 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 

Пояснение ко второму примеру (показан один из возможных вариантов):

Начальное состояние - все лампочки выключены Первая операция - переключаются все лампочки в выделенном прямоугольнике Вторая операция - переключаются все лампочки в выделенном прямоугольнике. В итоге получается "шахматная" конфигурация.