abc046d-test.py

def validate(s):
  g, p = 0, 0
  for c in s:
    if c == 'g':
      g += 1
    elif c == 'p':
      p += 1
      if p > g:
        return False
  return True

def generate(l):
  q = ['']
  for _ in range(l):
    nq = []
    while q:
      i = q.pop()
      t = i + 'g'
      if validate(t):
        nq.append(t)
      t = i + 'p'
      if validate(t):
        nq.append(t)
    q = nq
  return q

def solve(s):
  g = s.count('g')
  p = s.count('p')
  t = list(s)
  for i in range(len(s) -1, -1, -1):
    if t[i] == 'g' and g > p + 1:
      t[i] = 'p'
      g -= 1
      p += 1
  t = ''.join(t)
  if not validate(t):
    print('invalid %s from %s' % (t, s))
    exit()
  return count_point(t, s)

def count_point(player, opponent):
  result = 0
  for i in range(len(player)):
    if player[i] == 'p' and opponent[i] == 'g':
        result += 1
    elif player[i] == 'g' and opponent[i] == 'p':
        result -= 1
  return result

def slow_solve(o, gs):
  result = -float('inf')
  for p in gs:
    result = max(result, count_point(p, o))
  return result

for i in range(1, 16):
  print(i)
  gs = generate(i)
  for g in gs:
    t1 = slow_solve(g, gs)
    t2 = solve(g)
    if t1 != t2:
      print('bad from %s' % g)
      exit()