Игра состоит в том, что игроки по очереди выбирают одну из карточек и передвигают свою фишку по ленте

[sverhuVniz]

мучаюсь уже 2 недели с этой задачей но никакой из решений не подходит!
может поможете решить или киньте идею алгаритма!


Задача D. Игра с фишками
Имя входного файла: d.in
Имя выходного файла: d.out
Максимальное время работы на одном тесте: 1 секунда
Максимальный объем используемой памяти: 64 мегабайта

Двое друзей играют в игру на бесконечной ленте. У каждого из них есть по одной фишке. В начале игры обе фишки стоят на первой клетке. Кроме этого, есть набор карточек с числами.

Игра состоит в том, что игроки по очереди выбирают одну из карточек и передвигают свою фишку по ленте на то количество клеток, какое число написано на карточке. После этого карточка выбрасывается.

Игра завершается, когда карточки закончились. Победившим считается игрок, у которого фишка стоит на поле с большим номером.

Известен набор карточек. Напишите программу, которая определит победителя и номера клеток, на которых будут стоять фишки по окончанию игры. Известно, что оба друга играют по оптимальной стратегии.

Формат входных данных

Сначала вводится число N - количество карточек с числами (1≤N≤100000). Далее записаны N натуральных чисел - числа, написанные на карточках. Каждое из этих чисел не превышает 10000.

Формат выходных данных

Выведите номер клетки, на которой будет стоять в конце игры фишка победителя, и номер клетки, на которой будет стоять фишка его противника, если оба использовали оптимальную стратегию.

Примеры
d.in d.out
4 -----------7
5 1 8 2 -----11

_____________________
4 -----------3
1 1 1 1 -----3

[Min]

странно..... уже кто-то эту задачу вроде задавал.... и выходной файл из первого примера исходя из условия должен содержать сначала 11 а потом 7....... Я неправильно понял задания? Я просто сложности не понимаю...... отсортировать массив по неубыванию...... сумма всех элементов на нечетных позициях + 1 это номер клетки победителя, а сумма всех элементов на четных позициях +1 это номер клетки проигравшего.... Если я правильно условие понял

[puporev]

Сложность в том, чтобы написать быстрый алгоритм поиска максимального числа, когда их 100 000, числа до 10 000. А логика игры примитивна, каждый выбирает максимальное из оставшихся. Видимо решение в лоб в 1 сек не укладывается.

[Min]

ну я вижу тут решение в таком случае через динамическую память..... каждый следущий элемент сразу записывается на нужное место.... т.е. сначала записывается первый элемент, затем каждый раз берётся следущий и пробегается по полученному списку пока не втретит число меньшее, если встретит, то втавляет его перед ним...... получится нужный список...