Два человека принимают монеты, то Hacky Раствора

Question

Головоломка:

Есть ˝n˝ монеты в строке, монеты имеют различные значения. Два игрока по очереди берут монету с одного из концов линии, пока не осталось больше монет. Побеждает игрок с большей суммой денег. Если n равно, есть ли какой-нибудь хакерский алгоритм, который может решить, победит ли первый игрок или проиграет в O (1) памяти и O (n) времени?

Я решил проблему с динамическим программированием, но я не знаю, что Hacky алгоритм является. После поиска, я нашел решение от here:

def firstWillWinEven(self, values): 
    """ 
    odd_s: sum of values at odd position 
    even_s: sum of values at even position 
    if odd_s == even_s, the first mover cannot win if the other player mimics the first player 
    if odd_s > even_s, the first mover chooses the odd position values, and FORCE the other player choose the even 
    position values. The strategy and outcome are similar when even_s > odd_s. 
    """ 
    odd_s = 0 
    even_s = 0 
    for i in xrange(len(values)): 
     if i%2 == 0: 
      even_s += values[i] 
     else: 
      odd_s += values[i] 

    return odd_s != even_s 

В то время как я могу понять, если odd_s != even_s, первый человек, всегда победит, но я просто не мог понять odd_s == even_s situtation. Как доказать, что нет выигрышной стратегии, если odd_s == even_s?

Answer 1

Оказывается, я неправильно понял решение. Вот полное решение:

def firstWillWin(self, values): 
    """ 
    :param values: a list of integers 
    :return: a boolean which equals to True if the first player will win 
    """ 
    n = len(values) 
    if n%2 == 0 and self.firstWillWinEven(values): 
     return True 

    return self.firstWillWinNormalCase(values) 

Если odd_s != even_s тогда первый человек выиграет наверняка. если odd_s == even_s, мы не знаем, кто победит, поэтому опуститесь на firstWillWinNormalCase.