images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
24/04/2024 13:07:36

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

2230. Чехарда пингвинов

Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Ущелье прорезает полосу торосов между морем и площадкой, на которой живут пингвины. Ущелье настолько узкое, что пингвинам приходится перепрыгивать друг через друга, чтобы разминуться.
Однажды стая из `n` пингвинов, возвращаясь с рыбалки, встретила в ущелье стаю из `m` пингвинов, которая только собиралась поужинать. Между стаями оказалось небольшое пространство, на котором мог поместиться только один пингвин. Между пингвинами в стаях свободного пространства нет.
За одно действие пингвин может либо перейти на свободное пространство перед собой, либо перепрыгнуть через пингвина впереди себя, если за ним есть свободное пространство. Пятиться и прыгать назад пингвины не умеют.
Напишите программу, вычисляющую минимальное количество действий, за которое две стаи пингвинов могут разминуться в ущелье. После выполнения действий между стаями должно быть пустое пространство. Также пингвины не должны выходить за пределы участка ущелья, на котором две стаи встретились, так как там могут находиться другие стаи пингвинов.
Ввод содержит два целых числа `n` и `m` (`1\ ≤\ n,\ m\ ≤\ 100000`) – количество пингвинов в стаях.
Вывести одно целое число – минимальное количество действий.

Пример ввода

2 3

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

11
Минимальная последовательность из 11 ходов, которая позволяет пингвинам разойтись в ущелье:
AA.BBB
A.ABBB
ABA.BB
ABAB.B
AB.BAB
.BABAB
B.ABAB
BBA.AB
BBABA.
BBAB.A
BB.BAA
BBB.AA
loading