Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/8: Рейтинг темы: голосов - 8, средняя оценка - 4.75
106 / 106 / 9
Регистрация: 02.06.2009
Сообщений: 578
1

№38 с ********

17.05.2011, 21:37. Просмотров 1537. Ответов 1
Метки нет (Все метки)


Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали даже. Что ж, расскажем о новой игре. На доске написана последовательность n целых чисел. Играют двое. На очередном ходе игрок выбирает число с правого или с левого края последовательности, затем это число стирается и последовательность становится на одно число меньше, а ход переходит к противнику. Выигрывает тот, кто наберет в сумме больше. Написать программу, определяющую победителя в конкретной игре, при условии, что игроки будут играть оптимально.
Входные данные

В первой строке входного файла INPUT.TXT записано целое число n (0 < n < 100). Во второй строке через пробел заданы n натуральных чисел, не превосходящих 1000.
Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести 1, если победит первый игрок, 2 – если победит второй игрок и 0 – в случае ничьей.
Решал так.
Беру массив пар dp NxN, где номер строки - число цифр, убранных с правой стороны, а номер столбца - число цифр, убранных с левой стороны. В dp[0][0] пишем ноль, а нулевой столбец и нулевую строку заполняем так, как будто игроки берут только слева или только справа цифры (для каждого случая).
Затем заполняем таблицу по правилу - если сумма i+j - четная, то это ход второго игрока, иначе первого.
В текущую ячейку для текущего игрока запишем число, которое будет максимумом среди чисел dp[i][j-1].first(или second)+F[i-2], dp[i-1][j].first(или second)+F[N-j+1], где N - количество чисел, а F - массив самих чисел. Сумму противоположного игрока перенесем. Если максимума из тех двух чисел нет, то запишем любую сумму, а в сумму противоположного игрока внесем минимум из тех возможных ситуаций.
Получим матрицу, заполненную до побочной диагонали, на диагонали по идее будут возможные финалы игры (их счета). Пробегаем по этой диагонали и смотрим, сколько матчей завершилось в пользу первого и вничью. Если число побед первого не равно нулю, то вывести 1, иначе, если число ничьих не равно нулю - вывести 0, иначе вывести 2.
Чето не получается сделать... Ответ не выдает правильный. В чем косяк?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.05.2011, 21:37
Ответы с готовыми решениями:

Задачка с acmp
задача 421 с сайта ******** не проходит 4 тестimport java.util.*; import java.io.*; import...

Охотник acmp
Привет всем. Решаю такую задачу: Сезон охоты очень не долог, и поэтому оставшуюся часть года...

Графы (acmp 97)
В райской долине расположены N заповедников, имеющих форму прямоугольников. Однажды на собрании...

Распаковка строки, ACMP
Ребят, помогите выявить ошибку, а. В программировании новичок, мало чего понимаю. Условие:...

1
Эксперт С++
4710 / 2535 / 753
Регистрация: 18.08.2009
Сообщений: 4,550
18.05.2011, 05:47 2
Цитата Сообщение от Veyron Посмотреть сообщение
Ответ не выдает правильный. В чем косяк?
Скорее всего в алгоритме (но может быть и в реализации кода). Жалко что уезжаю до пятницы. Если до пятницы не решите и еще останется у Вас желание решить эту задачу, то в пятницу или субботу выкладывайте Ваш код, а мне в личку ссылку на него.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
18.05.2011, 05:47

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Красивые числа - 2 ACMP C++
Помогите чем сможете! Буду благодарен. Не могу решить эту задачу Красивые числа - 2 (Время: 1...

Задача 401 с acmp
Всем привет. Есть такая задача из категории &quot;Динамическое программирование&quot;. В динамике я всегда...

Боги (задача с acmp)
Здравствуйте. Проблема с решением задачи &quot;Боги&quot; (_http://********/?main=task&amp;id_task=93). Вот...

Степень строки(из acmp)
Привет всем. Я решаю такую задачу: Пусть задана строка s = s1s2...sn. Назовем ее k-ой (k &gt; 0)...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.