Problem:


人生ゲーム

太郎君は、おもちゃ屋さんに会津ホビー社製の人生ゲームを買いに行きました。人生ゲームは、マス目の書かれたボードとルーレットを使って遊びます。ボードには図のようにスタート地点とゴール地点が一つずつあり、それらはひとつながりのマス目でつながっています。最初に、コマはスタート地点のマスに置かれ、ルーレットを回して出た数によってコマを進めます。マスによっては、そこに止まったり通過したりすることでお金を得たり、コマの位置を変えたりするイベントマスがあります。最終的な勝敗は、コマがゴール地点に到達した時点の所持金の多寡で決まります。

 この会社の人生ゲームの面白いところは、ルーレットの出る目の大きさ、ゴールまでのマスの数、イベントマスの配置がひとつひとつパッケージごとに異なるところです。それらはケースに書かれており、それを読むことで確認することができます。お金を最も得られる人生ゲームを選びたい太郎君は、得るお金の期待値が一番大きいものを買いたがっています。そこであなたは、太郎君のゲーム選びを手伝うことにしました。

 ルーレットは、円周を X 等分に区分され、それぞれに V1、V2、...、VX という値が記入されているとします。ボードには、0 番、1 番、...、Y 番と番号がふられたマス目があり、順番につながっています。マス目の中には、イベントマスと呼ばれる特別なマスが Z 個あり、そこに到達すると特別な動作を行います。イベントマスのマス目の番号は Ni で与えられます。イベントマスには 1 ~ 3 の種類 (Ei)  があり、それぞれ次の動作が行われます。

            種類 (Ei)   特別動作              値 (Ai) の範囲

             1    指定の値 Ai だけ先へ進む       1~10 

             2     指定の値 Ai の金額を得る       1~100

             3     指定の値 Ai の金額を支払う      1~100

最初の所持金は 0 円で、第 0 マス目からスタートし、第 Y マス目に到達するとゴールとなります。ゴールを越えた場合もゴールと見なします。スタートとゴールにイベントは無く、1 マスに複数のイベントが重なることはありません。イベントによって進んだ先のマスのイベントは無視します。所持金が 0 円より少なくなる場合は 0 円とします。

 例えば、ある人生ゲームで得られるお金の期待値は以下のように計算できます。

 この例では、スタート、イベントマス(100 円入手) 、ゴールの 3 つのマスと、1 か 2 が出るルーレットからなる人生ゲームが表されています。まず、1 回目にルーレットを回した時、1 が出ればイベントマスに到達し、所持金は 100 円になります。一方、2 が出た場合はゴールに到達し、所持金は 0 円のままです。これらはどちらも 2 分の 1 の確率で起こります。

 さらに、1 回目でイベントマスに到達した場合は 2 回目のルーレットを回しますが、どの値が出てもゴールに到達し、所持金はどの場合も 100 円です。

 このように、全部で 3 通りのゴールの仕方があります。ゴールした時点の所持金に着目すると、0 円になる場合が 1 通りでその確率は 2 分の 1、100 円になる場合が 2 通りでその確率が 4 分の 1 です。この場合、ゴールでの所持金の期待値は、ゴールの仕方ごとの    (所持金 &times; その確率)   を足した値であり、この人生ゲームの期待値は 50 円になります。

 ルーレットの情報とボードの情報を入力とし、ゴール時の所持金の期待値を出力するプログラムを作成してください。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロみっつの行で示されます。各データセットは以下の形式で与えられます。

X Y Z
V1 V2 ... VX
N1 E1 A1
N2 E2 A2
:
NZ EZ AZ

X (1 ≤ X ≤ 4)、Vi (1 ≤ Vi ≤ 10)、Y (1 ≤ Y ≤ 50)、Ni (1 ≤ Ni ≤ Y-1)、Z (0 ≤ Z ≤ Y-1)、Ei (1 ≤ Ei ≤ 3)、 Ai (1 ≤ Ai ≤ 100) は整数で与えられます。

データセットの数は 100 を超えません。

Output

入力データセットごとに、最終的な所持金の期待値を１行に出力します。なお、所持金の期待値は小数点以下切り捨ての整数で出力してください。

Sample Input

1 2 0
1
1 2 1
1
1 2 100
1 2 1
2
1 2 100
2 2 1
1 2
1 2 100
4 5 3
1 2 3 4
1 1 2
2 2 100
4 3 60
0 0 0

Output for the Sample Input

0
100
0
50
20



Sample input:
1 2 0
1
1 2 1
1
1 2 100
1 2 1
2
1 2 100
2 2 1
1 2
1 2 100
4 5 3
1 2 3 4
1 1 2
2 2 100
4 3 60
0 0 0


Sample output:
0
100
0
50
20

Submission status: Wrong Answer

Solution code:
def solve(X, Y, Z, V, E, A):
    dp = [[0.0] * 6001 for _ in range(Y + max(V) + 1)]
    dp[0][0] = 1.0
    for i in range(Y):
        for j in range(5001):
            if dp[i][j] <= 0.0:
                continue
            for k in V:
                t = i + k
                if t > Y:
                    dp[Y][j] += dp[i][j]/X
                elif E[t] == 1:
                    dp[min(Y, t+A[t])][j] += dp[i][j]/X
                else:
                    dp[t][max(0, j+A[t])] += dp[i][j]/X

    s = 0
    for i in range(5001):
        if dp[Y][i] <= 0.0:
            continue
        s += i * dp[Y][i]
    print(int(s))

if __name__ == "__main__":
    import sys

    while True:
        X, Y, Z = map(int, input().split())
        if X | Y | Z == 0:
            sys.exit()
        V = map(int, input().split())
        E = [0] * 100
        A = [0] * 100
        for _ in range(Z):
            n, e, a = map(int, input().split())
            E[n] = e
            if e == 3:
                A[n] = -a
            else:
                A[n] = a
        solve(X, Y, Z, V, E, A)

Submission status: Wrong Answer

Solution code:
while 1:
    x,y,z=map(int,raw_input().split())
    if x==0 and y==0 and z==0:break
    v=map(int,raw_input().split())
    event=[[] for _ in xrange(y+1)]
    maxm=0
    for i in xrange(z):
        n,e,a=map(int,raw_input().split())
        event[n].append(e)
        event[n].append(a)
        if e==2:
            maxm+=a

    dp=[[0]*(5005) for _ in xrange(y+1)]
    dp[0][0]=1
    x=float(x)
    for i in xrange(y):
        for j in xrange(int(x)):
            for k in xrange(maxm+1):
                if i+v[j]>=y:
                    dp[y][k]+=dp[i][k]/x
                    continue

                if event[i+v[j]]==[]:
                    dp[i+v[j]][k]+=dp[i][k]/x

                elif event[i+v[j]][0]==1:
                    skip=event[i+v[j]][1]
                    dp[min(y,i+skip)][k]+=dp[i][k]/x

                elif event[i+v[j]][0]==2:
                    m=event[i+v[j]][1]
                    dp[i+v[j]][k+m]+=dp[i][k]/x

                else:
                    m=event[i+v[j]][1]
                    dp[i+v[j]][max(0,k-m)]+=dp[i][k]/x

    ans=0.0
    for i in xrange(maxm+1):
        ans+=dp[y][i]*i
    print(int(ans))

Submission status: Wrong Answer

Solution code:
while 1:
    x,y,z=map(int,raw_input().split())
    if x==0 and y==0 and z==0:break
    v=map(int,raw_input().split())
    event=[[] for _ in xrange(y+1)]
    maxm=0
    for i in xrange(z):
        n,e,a=map(int,raw_input().split())
        event[n].append(e)
        event[n].append(a)
        if e==2:
            maxm+=a

    dp=[[0]*(5005) for _ in xrange(y+1)]
    dp[0][0]=1
    x=float(x)
    for i in xrange(y):
        for j in xrange(maxm+1):
            if dp[i][j]==0:continue
            for k in xrange(int(x)):
                if i+v[k]>=y:
                    dp[y][j]+=dp[i][j]/x
                    continue

                if event[i+v[k]]==[]:
                    dp[i+v[k]][j]+=dp[i][j]/x

                elif event[i+v[k]][0]==1:
                    skip=event[i+v[k]][1]
                    dp[min(y,i+skip)][j]+=dp[i][j]/x

                elif event[i+v[k]][0]==2:
                    m=event[i+v[k]][1]
                    dp[i+v[k]][j+m]+=dp[i][j]/x

                else:
                    m=event[i+v[k]][1]
                    dp[i+v[k]][max(0,j-m)]+=dp[i][j]/x

    ans=0.0
    for i in xrange(maxm+1):
        ans+=dp[y][i]*i
    print(int(ans))

Submission status: Wrong Answer

Solution code:
def solve(x,y,maxm):
    for i in xrange(y):
        for j in xrange(maxm+1):
            if dp[i][j]==0:continue
            for k in xrange(int(x)):
                if i+v[k]>=y:
                    dp[y][j]+=dp[i][j]/x
                    continue

                if event[i+v[k]]==[]:
                    dp[i+v[k]][j]+=dp[i][j]/x

                elif event[i+v[k]][0]==1:
                    skip=event[i+v[k]][1]
                    dp[min(y,i+skip)][j]+=dp[i][j]/x

                elif event[i+v[k]][0]==2:
                    m=event[i+v[k]][1]
                    dp[i+v[k]][j+m]+=dp[i][j]/x

                else:
                    m=event[i+v[k]][1]
                    dp[i+v[k]][max(0,j-m)]+=dp[i][j]/x
    return dp
while 1:
    x,y,z=map(int,raw_input().split())
    if x==0 and y==0 and z==0:break
    v=map(int,raw_input().split())
    event=[[] for _ in xrange(y+1)]
    maxm=0
    for i in xrange(z):
        n,e,a=map(int,raw_input().split())
        event[n].append(e)
        event[n].append(a)
        if e==2:
            maxm+=a

    dp=[[0]*(5005) for _ in xrange(y+1)]
    dp[0][0]=1
    x=float(x)
    dp=solve(x,y,maxm)
    ans=0.0
    for i in xrange(maxm+1):
        ans+=dp[y][i]*i
    print(int(ans))

Submission status: Wrong Answer

Solution code:
def solve(x,y,maxm):
    for i in xrange(y):
        for j in xrange(maxm+1):
            for k in xrange(int(x)):
                if i+v[k]>=y:
                    dp[y][j]+=dp[i][j]/x
                    continue

                if event[i+v[k]]==[]:
                    dp[i+v[k]][j]+=dp[i][j]/x

                elif event[i+v[k]][0]==1:
                    skip=event[i+v[k]][1]
                    dp[min(y,i+skip)][j]+=dp[i][j]/x

                elif event[i+v[k]][0]==2:
                    m=event[i+v[k]][1]
                    dp[i+v[k]][j+m]+=dp[i][j]/x

                else:
                    m=event[i+v[k]][1]
                    dp[i+v[k]][max(0,j-m)]+=dp[i][j]/x
    return dp

while 1:
    x,y,z=map(int,raw_input().split())
    if x==0 and y==0 and z==0:break
    v=map(int,raw_input().split())
    event=[[] for _ in xrange(y+1)]
    maxm=0
    for i in xrange(z):
        n,e,a=map(int,raw_input().split())
        event[n].append(e)
        event[n].append(a)
        if e==2:
            maxm+=a

    dp=[[0]*(5005) for _ in xrange(y+1)]
    dp[0][0]=1
    x=float(x)
    dp=solve(x,y,maxm)
    ans=0.0
    for i in xrange(maxm+1):
        ans+=dp[y][i]*i
    print(int(ans))

Submission status: Wrong Answer

Solution code:
def solve(x,y,maxm):
    for i in xrange(y):
        for j in xrange(maxm+1):
            if dp[i][j]==0:continue
            for k in xrange(int(x)):

                if event[min(y,i+v[k])][0]==0:
                    dp[min(y,i+v[k])][j]+=dp[i][j]/x

                elif event[i+v[k]][0]==1:
                    skip=event[i+v[k]][1]
                    dp[min(y,i+skip)][j]+=dp[i][j]/x

                elif event[i+v[k]][0]==2:
                    m=event[i+v[k]][1]
                    dp[i+v[k]][j+m]+=dp[i][j]/x

                else:
                    m=event[i+v[k]][1]
                    dp[i+v[k]][max(0,j-m)]+=dp[i][j]/x
    return dp

while 1:
    x,y,z=map(int,raw_input().split())
    if x==0 and y==0 and z==0:break
    v=map(int,raw_input().split())
    event=[[0]*2 for _ in xrange(y+1)]
    maxm=0
    for i in xrange(z):
        n,e,a=map(int,raw_input().split())
        event[n][0]=e
        event[n][1]=a
        if e==2:
            maxm+=a

    dp=[[0]*(5005) for _ in xrange(y+1)]
    dp[0][0]=1
    x=float(x)
    dp=solve(x,y,maxm)
    ans=0.0
    for i in xrange(maxm+1):
        ans+=dp[y][i]*i
    print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
while True:
    x, y, z = map(int, raw_input().split())
    if x==0 and y==0 and z==0: break
    dp = [[0.0 for col in range(5101)] for row in range(61)]
    m = {}
    for i in range(y+10):
        m[i] = (0,0)
    v = []
    v = map(int, raw_input().split())
    for i in range(z):
        n, e, a = map(int, raw_input().split())
        m[n] = (e, a)
    dp[0][0] = 1.0
    for i in range(y):
        for j in range(5001):
            for k in range(x):
                nx = i + v[k]
                if m[nx][0] == 1:
                    dp[min(y,nx+m[nx][1])][j]+=dp[i][j]/x
                elif m[nx][0]==2:
                    dp[nx][j+m[nx][1]]+=dp[i][j]/x
                elif m[nx][0]==3:
                    dp[nx][max(0,j-m[nx][1])]+=dp[i][j]/x
                else:
                    dp[min(y,nx)][j] += dp[i][j]/x                       
    ans = 0.0
    for i in range(5001):   
        ans += dp[y][i]*i
    print int(ans)

Submission status: Time Limit Exceeded

Solution code:
while 1:
    x,y,z=map(int,raw_input().split())
    if x==0 and y==0 and z==0:break
    v=map(int,raw_input().split())
    event=[[] for _ in xrange(y+1)]
    maxm=0
    for i in xrange(z):
        n,e,a=map(int,raw_input().split())
        event[n].append(e)
        event[n].append(a)
        if e==2:
            maxm+=a

    dp=[[0]*(5005) for _ in xrange(y+1)]
    dp[0][0]=1
    x=float(x)
    for i in xrange(y):
        for k in xrange(maxm+1):
            for j in xrange(int(x)):
                if i+v[j]>=y:
                    dp[y][k]+=dp[i][k]/x
                    continue

                if event[i+v[j]]==[]:
                    dp[i+v[j]][k]+=dp[i][k]/x

                elif event[i+v[j]][0]==1:
                    skip=event[i+v[j]][1]
                    dp[min(y,i+skip)][k]+=dp[i][k]/x

                elif event[i+v[j]][0]==2:
                    m=event[i+v[j]][1]
                    dp[i+v[j]][k+m]+=dp[i][k]/x

                else:
                    m=event[i+v[j]][1]
                    dp[i+v[j]][max(0,k-m)]+=dp[i][k]/x

    ans=0.0
    for i in xrange(maxm+1):
        ans+=dp[y][i]*i
    print(int(ans))

Submission status: Accepted

Solution code:
while True:
    x, y, z = map(int, raw_input().split())
    if x==0 and y==0 and z==0: break
    dp = [[0.0 for col in range(5101)] for row in range(61)]
    m = {}
    for i in range(y+10):
        m[i] = (0,0)
    v = []
    v = map(int, raw_input().split())
    for i in range(z):
        n, e, a = map(int, raw_input().split())
        m[n] = (e, a)
    dp[0][0] = 1.0
    for i in range(y):
        for j in range(y*100):
            if dp[i][j] == 0.0: continue
            for k in range(x):
                nx = i + v[k]
                if m[nx][0] == 1:
                    dp[min(y,nx+m[nx][1])][j]+=dp[i][j]/x
                elif m[nx][0]==2:
                    dp[nx][j+m[nx][1]]+=dp[i][j]/x
                elif m[nx][0]==3:
                    dp[nx][max(0,j-m[nx][1])]+=dp[i][j]/x
                else:
                    dp[min(y,nx)][j] += dp[i][j]/x                       
    ans = 0.0
    for i in range(5001):   
        ans += dp[y][i]*i
    print int(ans)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve(X, Y, Z, V, E, A):
    dp = [[0.0] * 6001 for _ in xrange(Y + max(V) + 1)]
    dp[0][0] = 1.0
    for i in xrange(Y):
        for j in xrange(5001):
            if dp[i][j] <= 0.0:
                continue
            for k in V:
                t = i + k
                if t > Y:
                    dp[Y][j] += dp[i][j]/X
                elif E[t] == 1:
                    dp[min(Y, t+A[t])][j] += dp[i][j]/X
                else:
                    dp[t][max(0, j+A[t])] += dp[i][j]/X

    s = 0
    for i in xrange(5001):
        s += i * dp[Y][i]
    print int(s)

if __name__ == "__main__":
    import sys

    while True:
        X, Y, Z = map(int, raw_input().split())
        if X | Y | Z == 0:
            sys.exit()
        V = map(int, raw_input().split())
        E = [0] * 100
        A = [0] * 100
        for _ in xrange(Z):
            n, e, a = map(int, raw_input().split())
            E[n] = e
            if e == 3:
                A[n] = -a
            else:
                A[n] = a
        solve(X, Y, Z, V, E, A)

Submission status: Accepted

Solution code:
def solve(X, Y, Z, V, E, A):
    dp = [[0.0] * 6001 for _ in range(Y + max(V) + 1)]
    dp[0][0] = 1.0
    for i in range(Y):
        for j in range(5001):
            if dp[i][j] <= 0.0:
                continue
            for k in V:
                t = i + k
                if t > Y:
                    dp[Y][j] += dp[i][j]/X
                elif E[t] == 1:
                    dp[min(Y, t+A[t])][j] += dp[i][j]/X
                else:
                    dp[t][max(0, j+A[t])] += dp[i][j]/X

    s = 0
    for i in range(5001):
        if dp[Y][i] <= 0.0:
            continue
        s += i * dp[Y][i]
    print(int(s))

if __name__ == "__main__":
    import sys

    while True:
        X, Y, Z = map(int, raw_input().split())
        if X | Y | Z == 0:
            sys.exit()
        V = map(int, raw_input().split())
        E = [0] * 100
        A = [0] * 100
        for _ in range(Z):
            n, e, a = map(int, raw_input().split())
            E[n] = e
            if e == 3:
                A[n] = -a
            else:
                A[n] = a
        solve(X, Y, Z, V, E, A)

Submission status: Accepted

Solution code:
import sys
def solve(X, Y, Z, V, E, A):
    dp = [[0.0] * 6001 for _ in range(Y + max(V) + 1)]
    dp[0][0] = 1.0
    for i in range(Y):
        for j in range(5001):
            if dp[i][j] <= 0.0:
                continue
            for k in V:
                t = i + k
                if t > Y:
                    dp[Y][j] += dp[i][j]/X
                elif E[t] == 1:
                    dp[min(Y, t+A[t])][j] += dp[i][j]/X
                else:
                    dp[t][max(0, j+A[t])] += dp[i][j]/X

    s = 0
    for i in range(5001):
        if dp[Y][i] <= 0.0:
            continue
        s += i * dp[Y][i]
    print(int(s))

while True:
    X, Y, Z = map(int, raw_input().split())
    if X | Y | Z == 0:
        sys.exit()
    V = map(int, raw_input().split())
    E = [0] * 100
    A = [0] * 100
    for _ in range(Z):
        n, e, a = map(int, raw_input().split())
        E[n] = e
        if e == 3:
            A[n] = -a
        else:
            A[n] = a
    solve(X, Y, Z, V, E, A)

Submission status: Accepted

Solution code:
def solve(X, Y, Z, V, E, A):
    dp = [[0.0] * 6001 for _ in xrange(Y + max(V) + 1)]
    dp[0][0] = 1.0
    for i in xrange(Y):
        for j in xrange(5001):
            if dp[i][j] <= 0.0:
                continue
            for k in V:
                t = i + k
                if t > Y:
                    dp[Y][j] += dp[i][j]/X
                elif E[t] == 1:
                    dp[min(Y, t+A[t])][j] += dp[i][j]/X
                else:
                    dp[t][max(0, j+A[t])] += dp[i][j]/X

    s = 0
    for i in xrange(5001):
        if dp[Y][i] <= 0.0:
            continue
        s += i * dp[Y][i]
    print int(s)

if __name__ == "__main__":
    import sys

    while True:
        X, Y, Z = map(int, raw_input().split())
        if X | Y | Z == 0:
            sys.exit()
        V = map(int, raw_input().split())
        E = [0] * 100
        A = [0] * 100
        for _ in xrange(Z):
            n, e, a = map(int, raw_input().split())
            E[n] = e
            if e == 3:
                A[n] = -a
            else:
                A[n] = a
        solve(X, Y, Z, V, E, A)

Submission status: Accepted

Solution code:
def solve(X, Y, Z, V, E, A):
    dp = [[0.0] * 6001 for _ in range(Y + max(V) + 1)]
    dp[0][0] = 1.0
    for i in range(Y):
        for j in range(5001):
            if dp[i][j] <= 0.0:
                continue
            for k in V:
                t = i + k
                if t > Y:
                    dp[Y][j] += dp[i][j]/X
                elif E[t] == 1:
                    dp[min(Y, t+A[t])][j] += dp[i][j]/X
                else:
                    dp[t][max(0, j+A[t])] += dp[i][j]/X

    s = 0
    for i in range(5001):
        if dp[Y][i] <= 0.0:
            continue
        s += i * dp[Y][i]
    print(int(s))

if __name__ == "__main__":
    import sys

    while True:
        X, Y, Z = map(int, input().split())
        if X | Y | Z == 0:
            sys.exit()
        V = list(map(int, input().split()))
        E = [0] * 100
        A = [0] * 100
        for _ in range(Z):
            n, e, a = map(int, input().split())
            E[n] = e
            if e == 3:
                A[n] = -a
            else:
                A[n] = a
        solve(X, Y, Z, V, E, A)

Submission status: Accepted

Solution code:
def solve(X, Y, Z, V, E, A):
    dp = [[0.0] * 6001 for _ in range(Y + max(V) + 1)]
    dp[0][0] = 1.0
    for i in range(Y):
        for j in range(5001):
            if dp[i][j] <= 0.0:
                continue
            for k in V:
                t = i + k
                if t > Y:
                    dp[Y][j] += dp[i][j]/X
                elif E[t] == 1:
                    dp[min(Y, t+A[t])][j] += dp[i][j]/X
                else:
                    dp[t][max(0, j+A[t])] += dp[i][j]/X

    s = 0
    for i in range(5001):
        s += i * dp[Y][i]
    print(int(s))

if __name__ == "__main__":
    import sys

    while True:
        X, Y, Z = map(int, input().split())
        if X | Y | Z == 0:
            sys.exit()
        V = list(map(int, input().split()))
        E = [0] * 100
        A = [0] * 100
        for _ in range(Z):
            n, e, a = map(int, input().split())
            E[n] = e
            if e == 3:
                A[n] = -a
            else:
                A[n] = a
        solve(X, Y, Z, V, E, A)

Submission status: Accepted

Solution code:
def solve(X, Y, Z, V, E, A):
    dp = [[0.0] * 6001 for _ in range(Y + 11)]
    dp[0][0] = 1.0
    for i in range(Y):
        for j in range(5001):
            if dp[i][j] <= 0.0:
                continue
            for k in V:
                t = i + k
                if t > Y:
                    dp[Y][j] += dp[i][j]/X
                elif E[t] == 1:
                    dp[min(Y, t+A[t])][j] += dp[i][j]/X
                else:
                    dp[t][max(0, j+A[t])] += dp[i][j]/X

    s = 0
    for i in range(5001):
        s += i * dp[Y][i]
    print(int(s))

if __name__ == "__main__":
    import sys

    while True:
        X, Y, Z = map(int, input().split())
        if X | Y | Z == 0:
            sys.exit()
        V = list(map(int, input().split()))
        E = [0] * 100
        A = [0] * 100
        for _ in range(Z):
            n, e, a = map(int, input().split())
            E[n] = e
            if e == 3:
                A[n] = -a
            else:
                A[n] = a
        solve(X, Y, Z, V, E, A)

Submission status: Accepted

Solution code:
def solve(X, Y, Z, V, E, A):
    dp = [[0.0] * 6001 for _ in range(Y + 11)]
    dp[0][0] = 1.0
    for i in range(Y):
        for j in range(5001):
            if dp[i][j] <= 0.0:
                continue
            for k in V:
                t = i + k
                if t > Y:
                    dp[Y][j] += dp[i][j]/X
                elif E[t] == 1:
                    dp[min(Y, t+A[t])][j] += dp[i][j]/X
                else:
                    dp[t][max(0, j+A[t])] += dp[i][j]/X

    s = 0
    for i in range(5001):
        if dp[Y][i] <= 0.0:
            continue
        s += i * dp[Y][i]
    print(int(s))

if __name__ == "__main__":
    import sys

    while True:
        X, Y, Z = map(int, input().split())
        if X | Y | Z == 0:
            sys.exit()
        V = list(map(int, input().split()))
        E = [0] * 100
        A = [0] * 100
        for _ in range(Z):
            n, e, a = map(int, input().split())
            E[n] = e
            if e == 3:
                A[n] = -a
            else:
                A[n] = a
        solve(X, Y, Z, V, E, A)

Submission status: Accepted

Solution code:
def solve(X, Y, Z, V, E, A):
    dp = [[0.0] * 6001 for _ in range(Y + 11)]
    dp[0][0] = 1.0
    for i in range(Y):
        for j in range(5001):
            if dp[i][j] <= 0.0:
                continue
            for k in V:
                t = i + k
                if t > Y:
                    dp[Y][j] += dp[i][j]/X
                elif E[t] == 1:
                    dp[min(Y, t+A[t])][j] += dp[i][j]/X
                else:
                    dp[t][max(0, j+A[t])] += dp[i][j]/X

    s = 0
    for i in range(5001):
        s += i * dp[Y][i]
    print(int(s))

if __name__ == "__main__":

    while True:
        X, Y, Z = map(int, input().split())
        if X | Y | Z == 0:
            break
        V = list(map(int, input().split()))
        E = [0] * 100
        A = [0] * 100
        for _ in range(Z):
            n, e, a = map(int, input().split())
            E[n] = e
            if e == 3:
                A[n] = -a
            else:
                A[n] = a
        solve(X, Y, Z, V, E, A)

Submission status: Accepted

Solution code:
def solve(x,y,maxm):
    for i in xrange(y):
        for j in xrange(maxm+1):
            if dp[i][j]==0:continue
            for k in xrange(int(x)):

                if event[min(y,i+v[k])][0]==0:
                    dp[min(y,i+v[k])][j]+=dp[i][j]/x

                elif event[i+v[k]][0]==1:
                    skip=event[i+v[k]][1]
                    dp[min(y,i+v[k]+skip)][j]+=dp[i][j]/x

                elif event[i+v[k]][0]==2:
                    m=event[i+v[k]][1]
                    dp[i+v[k]][j+m]+=dp[i][j]/x

                else:
                    m=event[i+v[k]][1]
                    dp[i+v[k]][max(0,j-m)]+=dp[i][j]/x
    return dp

while 1:
    x,y,z=map(int,raw_input().split())
    if x==0 and y==0 and z==0:break
    v=map(int,raw_input().split())
    event=[[0]*2 for _ in xrange(y+1)]
    maxm=0
    for i in xrange(z):
        n,e,a=map(int,raw_input().split())
        event[n][0]=e
        event[n][1]=a
        if e==2:
            maxm+=a

    dp=[[0]*(5005) for _ in xrange(y+1)]
    dp[0][0]=1
    x=float(x)
    dp=solve(x,y,maxm)
    ans=0.0
    for i in xrange(maxm+1):
        ans+=dp[y][i]*i
    print(int(ans))

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

def main():
  while True:
    x, y, z = map(int, input().split())
    if x == 0:break
    vlst = list(map(int, input().split()))
    events = {}
    for _  in range(z):
      n, e, a = map(int, input().split())
      events[n] = (e, a)
    
    que = []
    heappush(que, (0, 0))
    cnt = [[0] * (100 * y + 1) for _ in range(y + 1)]
    init = x ** y
    cnt[0][0] = init
    visited = {}
    while que:
      pos, score = heappop(que)
      for v in vlst:
        new_pos = pos + v
        new_score = score
        if new_pos in events:
          event, value = events[new_pos]
          if event == 1:
            new_pos += value
          elif event == 2:
            new_score += value
          else:
            new_score = max(new_score - value, 0)
        if new_pos >= y:
          cnt[y][new_score] += cnt[pos][score] // x
        else:
          cnt[new_pos][new_score] += cnt[pos][score] // x
          if (new_pos, new_score) not in visited:
            visited[(new_pos, new_score)] = True
            heappush(que, (new_pos, new_score))
    
    total = 0
    for score in range(100 * y + 1):
      total += cnt[y][score] * score
    print(total // init)

main()

Submission status: Runtime Error

Solution code:
def solve(X, Y, Z, V, E, A):
    dp = [[0.0] * 6001 for _ in range(Y + max(V) + 1)]
    dp[0][0] = 1.0
    for i in range(Y):
        for j in range(5001):
            if dp[i][j] <= 0.0:
                continue
            for k in V:
                t = i + k
                if t > Y:
                    dp[Y][j] += dp[i][j]/X
                elif E[t] == 1:
                    dp[min(Y, t+A[t])][j] += dp[i][j]/X
                else:
                    dp[t][max(0, j+A[t])] += dp[i][j]/X

    s = 0
    for i in range(5001):
        if dp[Y][i] <= 0.0:
            continue
        s += i * dp[Y][i]
    print int(s)

if __name__ == "__main__":
    import sys

    while True:
        X, Y, Z = map(int, input().split())
        if X | Y | Z == 0:
            sys.exit()
        V = map(int, input().split())
        E = [0] * 100
        A = [0] * 100
        for _ in range(Z):
            n, e, a = map(int, input().split())
            E[n] = e
            if e == 3:
                A[n] = -a
            else:
                A[n] = a
        solve(X, Y, Z, V, E, A)