Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Delphi программирование > Паскаль, Turbo Pascal, PascalABC.NET
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 14.11.2008, 17:57   #1
sverhuVniz
Пользователь
 
Аватар для sverhuVniz
 
Регистрация: 24.10.2008
Сообщений: 32
По умолчанию Игра состоит в том, что игроки по очереди выбирают одну из карточек и передвигают свою фишку по ленте

мучаюсь уже 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
___________________________________ ____________
ВОН ВЫГНАТЬ ПРОКЛЯТЫХ СПАММЕРОВ!

Последний раз редактировалось sverhuVniz; 14.11.2008 в 18:33. Причина: ошибка
sverhuVniz вне форума Ответить с цитированием
Старый 15.11.2008, 01:20   #2
Min
Форумчанин
 
Регистрация: 12.09.2008
Сообщений: 239
По умолчанию

странно..... уже кто-то эту задачу вроде задавал.... и выходной файл из первого примера исходя из условия должен содержать сначала 11 а потом 7....... Я неправильно понял задания? Я просто сложности не понимаю...... отсортировать массив по неубыванию...... сумма всех элементов на нечетных позициях + 1 это номер клетки победителя, а сумма всех элементов на четных позициях +1 это номер клетки проигравшего.... Если я правильно условие понял
Надо бы избавиться от привычки ставить многоточие.....
Min вне форума Ответить с цитированием
Старый 15.11.2008, 09:25   #3
puporev
Старожил
 
Регистрация: 13.10.2007
Сообщений: 2,740
По умолчанию

Сложность в том, чтобы написать быстрый алгоритм поиска максимального числа, когда их 100 000, числа до 10 000. А логика игры примитивна, каждый выбирает максимальное из оставшихся. Видимо решение в лоб в 1 сек не укладывается.
puporev вне форума Ответить с цитированием
Старый 16.11.2008, 02:46   #4
Min
Форумчанин
 
Регистрация: 12.09.2008
Сообщений: 239
По умолчанию

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


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Пусть группа состоит из N человек. В ней каждый имеет (N/2) друзей и не больше K врагов. koshka669 Помощь студентам 3 26.05.2011 18:15
Игра "Что такое" Hallo Свободное общение 384 17.09.2009 19:09
Запуск экзешников по очереди Airou Общие вопросы Delphi 2 03.09.2008 21:15
Помогите сделать одну фишку! eldar Работа с сетью в Delphi 1 04.08.2008 14:34
загрузить в компонент imagelist 3 рисунка, а потом по очереди выводить их Stanislav Компоненты Delphi 2 25.11.2007 01:43