Форум программистов, компьютерный форум CyberForum.ru

№38 с ******** - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
Veyron
 Аватар для Veyron
104 / 104 / 4
Регистрация: 02.06.2009
Сообщений: 579
17.05.2011, 21:37     №38 с ******** #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.
Чето не получается сделать... Ответ не выдает правильный. В чем косяк?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.05.2011, 05:47     №38 с ******** #2
Цитата Сообщение от Veyron Посмотреть сообщение
Ответ не выдает правильный. В чем косяк?
Скорее всего в алгоритме (но может быть и в реализации кода). Жалко что уезжаю до пятницы. Если до пятницы не решите и еще останется у Вас желание решить эту задачу, то в пятницу или субботу выкладывайте Ваш код, а мне в личку ссылку на него.
Yandex
Объявления
18.05.2011, 05:47     №38 с ********
Ответ Создать тему
Опции темы

Текущее время: 19:38. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru