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))