№38 с acmp.ru

@Veyron · Регистрация: 02.06.2009

Author24 — интернет-сервис помощи студентам

Вы любите играть в игры? Конечно, любите! Но про эту игру, возможно, ничего не знаете и не слышали даже. Что ж, расскажем о новой игре. На доске написана последовательность 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 · 18.05.2011, 05:47

Сообщение от Veyron

Ответ не выдает правильный. В чем косяк?

Скорее всего в алгоритме (но может быть и в реализации кода). Жалко что уезжаю до пятницы. Если до пятницы не решите и еще останется у Вас желание решить эту задачу, то в пятницу или субботу выкладывайте Ваш код, а мне в личку ссылку на него.

@Veyron 107 / 107 / 9 Регистрация: 02.06.2009 Сообщений: 578
		1
	№38 с acmp.ru 17.05.2011, 21:37. Показов 2306. Ответов 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

valeriikozlov 4727 / 2548 / 757 Регистрация: 18.08.2009 Сообщений: 4,568
	18.05.2011, 05:47	2
	Сообщение от Veyron Ответ не выдает правильный. В чем косяк? Скорее всего в алгоритме (но может быть и в реализации кода). Жалко что уезжаю до пятницы. Если до пятницы не решите и еще останется у Вас желание решить эту задачу, то в пятницу или субботу выкладывайте Ваш код, а мне в личку ссылку на него. 0