Google Code Jam Japan 2011 予選 A. カードシャッフル

カードシャッフル

逆から計算する。例えば、サンプルの最後の例だと、[1 2 3 4 5] → [4 5 1 2 3] → [3 4 5 1 2] → [1 2 3 4 5]で、3回目のシャッフルの後で2番目にあるカードは、3回目のシャッフルの前には5番目に、2回目のシャッフルの前には4番目に、最初は2番目の位置にある。こうすればカードの枚数に関わらず、最後にW番目に来るカードの位置だけを覚えておけばよい。

def solve(M,C,W,A,B):
    for i in range(C)[::-1]:
        if W<=B[i]:
            W = A[i]+W-1
        elif W<=A[i]+B[i]-1:
            W -= B[i]
    return W

for t in range(input()):
    M,C,W = map(int,raw_input().split())
    A,B = [0]*C,[0]*C
    for i in range(C):
        A[i],B[i] = map(int,raw_input().split())
    
    print "Case #%s: %s" % (t+1,solve(M,C,W,A,B))