Областная олимпиада по информатике 2013-2014
Многие математические игры кажутся довольно странными для посторонних. Вот пример одной из них.
У вас имеется 2N − 1 карточек. Вначале в игре участвуют N карточек. На лицевой стороне каждой из них написано какое-то целое число. На обратной стороне этих же карточек написан 0 (ноль). Остальные N −1 карточек пустые с обеих сторон и пока не участвуют в игре. Вы загадываете какое-то число от 1 до N. Каждый ход игры игры заключается в следующих действиях:
Напишите программу, которая по исходному состоянию игры определяет число, которое будет написано на обратной стороне последней карточки.
после хода 2: (6 2), (4 0), (5 0)
после хода 3: (6 2), (9, 1)
после хода 4: (15, 3)
В 50% тестов $N ≤ 1000$.
посмотреть в олимпиаде
У вас имеется 2N − 1 карточек. Вначале в игре участвуют N карточек. На лицевой стороне каждой из них написано какое-то целое число. На обратной стороне этих же карточек написан 0 (ноль). Остальные N −1 карточек пустые с обеих сторон и пока не участвуют в игре. Вы загадываете какое-то число от 1 до N. Каждый ход игры игры заключается в следующих действиях:
- выбрать карточку с наименьшим числом на лицевой стороне. Если таких карточек несколько — выбрать ту, на обратной стороне которой число минимально. Пусть выбрана карточка с числом A на лицевой стороне и B на обратной стороне. Убрать эту карточку из игры.
- еще раз выбрать карточку с наименьшим числом на лицевой стороне. Если таких карточек несколько — выбрать ту, на обратной стороне которой число минимально. Пусть выбрана карточка с числом C на лицевой стороне и D на обратной стороне. Убрать эту карточку из игры.
- взять пустую карточку. На лицевой стороне написать число, равное A + C, а на обратной — максимальное из чисел B + 1 и D + 1. Добавить эту карточку в игру.
Напишите программу, которая по исходному состоянию игры определяет число, которое будет написано на обратной стороне последней карточки.
Входные данные
Первая строка входного файла содержит число $N$ ($1 ≤ N ≤ 105$). Следующая строка содержит $N$ целых чисел — числа, написанные на лицевой стороне карточек. Каждое число лежит в промежутке от $−10^9$ до $10^9$ включительно.Выходные данные
Выведите одно целое число — ответ к задаче.Примеры:
Вход:5 1 2 3 4 5Ответ:
3
Примечание:
Описание ходов игры: исходное состояние: (1 0), (2 0), (3 0), (4 0), (5 0) после хода 1: (3 1), (3 0), (4 0), (5 0)после хода 2: (6 2), (4 0), (5 0)
после хода 3: (6 2), (9, 1)
после хода 4: (15, 3)
В 50% тестов $N ≤ 1000$.
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.