ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Вузовско-академическая олимпиада по информатике 2019

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

F. Он вам не конь

Ограничение времени: 1.0 секунды
Ограничение памяти: 256 МБ
Оказывается, шахматные кони не очень любят ходить друг к другу в гости. Обычно дорога проходит окольными путями. Прийти с подарком тоже не получится, ведь его негде взять. А если гости всё-таки пришли, то они занимают собой весь дом, и владельцу нужно куда-то уйти на то время, пока в его доме гости.
Недавно конь Остап задался вопросом переезда на другую доску размером N × N. Переезжать одному ему не хочется, поэтому он хочет найти как можно больше единомышленников. Единственная причина переезда в том, что сейчас к нему постоянно приходят гости, поэтому, чтобы такое не повторялось, ему хочется узнать максимальное количество единомышленников, которые поместятся на новой доске так, что никто не сможет ходить друг к другу в гости.
Дом каждого коня находится в одной из клеток. Один конь может сходить в гости к другому, если существует путь, состоящий из произвольного количества ходов коней, который идёт из дома первого коня в дом второго. Известно, что кони передвигаются только буквой «Г»: сначала на B клеток вперед, а затем на A клеток в сторону.
Вот так выглядят все варианты одного хода шахматного коня при A = 1, B = 2:
Problem illustration

Исходные данные

В первой строке указывается размер доски N (1 ≤ N ≤ 109). Во второй и третьей строках указываются параметры ходов коней — A и B (0 ≤ AB ≤ 3).

Результат

В единственной строке выведите, сколько коней может переехать на новую доску. В это количество должен входить Остап.

Примеры

исходные данныерезультат
2
1
1
2
3
0
1
1
Автор задачи: Кирилл Девяткин
Источник задачи: Вузовско-академическая олимпиада по информатике 2019
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2116. Он вам не конь