C.py

#!/usr/bin/env python3
class memoize(dict):
   def __init__(self, func):
       self.func = func
       dict.__init__(self)
       
   def __call__(self, *args):
       return self[args]

   def __missing__(self, key):
       res = self[key] = self.func(*key)
       return res

# Single global memo (cleared between cases in main loop)
@memoize
def solve(R, k, g):
   """Returns (euros, final_g)"""
   # cf. exponentiation by squaring
   if R == 0:
       return 0, g
   if R % 2:
       s = 0
       for i, gi in enumerate(g):
           if s + gi > k:
               break
           s += gi
       s2, g = solve(R - 1, k, g[i:] + g[:i])
       return s + s2, g
   
   s1, g = solve(R // 2, k, g)
   s2, g = solve(R // 2, k, g)
   return s1 + s2, g

# Reading from file leaves stdin available for debugging
import fileinput
input = fileinput.input().__next__
   
T = int(input())
for case in range(1, T + 1):
   R, k, N = (int(w) for w in input().split())
   g = tuple(int(w) for w in input().split())
   solve.clear()
   s, g = solve(R, k, g)
   print("Case #{0}: {1}".format(case, s))


-- 
Beni Cherniavsky-Paskin <cben@users.sf.net>