Олимпиада проводится при поддержке Московского физико-технического института, Благотворительного фонда "Династия", компьютерной компании НИКС, Компании Yandex, компании Genius
Информационная поддержка:
журнал "Мир ПК"
III Всероссийская заочная олимпиада школьников по информатике, 2008/09 учебный год
Задача D. Игра с фишками
| Имя входного файла: | d.in |
| Имя выходного файла: | d.out |
| Максимальное время работы на одном тесте: | 1 секунда |
| Максимальный объем используемой памяти: | 64 мегабайта |
Двое друзей играют в игру на бесконечной ленте. У каждого из них есть по одной фишке. В начале игры обе фишки стоят на первой клетке. Кроме этого, есть набор карточек с числами.
Игра состоит в том, что игроки по очереди выбирают одну из карточек и передвигают свою фишку по ленте на то количество клеток, какое число написано на карточке. После этого карточка выбрасывается.
Игра завершается, когда карточки закончились. Победившим считается игрок, у которого фишка стоит на поле с большим номером.
Известен набор карточек. Напишите программу, которая определит победителя и номера клеток, на которых будут стоять фишки по окончанию игры. Известно, что оба друга играют по оптимальной стратегии.
Формат входных данных
Сначала вводится число N - количество карточек с числами (1≤N≤100000). Далее записаны N натуральных чисел - числа, написанные на карточках. Каждое из этих чисел не превышает 10000.
Формат выходных данных
Выведите номер клетки, на которой будет стоять в конце игры фишка победителя, и номер клетки, на которой будет стоять фишка его противника, если оба использовали оптимальную стратегию.
Примеры
| d.in | d.out |
4 5 1 8 2 |
11 7 |
4 1 1 1 1 |
3 3 |