Problem:


通勤経路 

問題

JOIさんが住むカナダのある都市は，南北方向にまっすぐに伸びる w 本の道路と，東西方向にまっすぐに伸びる h 本の道路により，碁盤の目の形に区分けされている．

南北方向の w 本の道路には，西から順に 1, 2, ... , w の番号が付けられている．また，東西方向の h 本の道路には，南から順に 1, 2, ... , h の番号が付けられている．西から i 番目の南北方向の道路と，南から j 番目の東西方向の道路が交わる交差点を (i, j) で表す．

JOIさんは，交差点 (1, 1) の近くに住んでおり，交差点 (w, h) の近くの会社に車で通っている．車は道路に沿ってのみ移動することができる．JOIさんは，通勤時間を短くするため，東または北にのみ向かって移動して通勤している．また，この都市では，交通事故を減らすために，次のような交通規則が設けられている：

交差点を曲がった車は，その直後の交差点で曲がることは出来ない．

すなわち，交差点で曲がったあとに1ブロックだけ進んで再び曲がることは許されない．このとき，JOIさんの通勤経路は何通り考えられるだろうか．

w と h が与えられたとき，JOIさんの通勤経路の個数を 100000 で割った余りを出力するプログラムを作成せよ．

入力

入力は複数のデータセットからなる．各データセットは1行からなり，空白を区切りとして2個の整数 w, h (2 ≤ w ≤ 100， 2 ≤ h ≤ 100) が書かれている．w は南北方向の道路の本数， h は東西方向の道路の本数を表す．

w, h がともに 0 のとき入力の終了を示す.データセットの数は 5 を超えない．

出力

データセットごとに，JOIさんの通勤経路の個数を 100000 で割った余りを1行に出力する．

 入出力例

入力例

3 4
15 15
0 0

出力例

5
43688

1つ目の入力例におけるJOIさんの通勤経路 ( 5 通り)

1つ目の入力例において，JOIさんの通勤経路は図のように 5 通り考えられる．したがって，5を出力する．

2つ目の入力例において，JOIさんの通勤経路は 143688 通り考えられる．したがって，143688 を 100000 で割った余りである 43688 を出力する．

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
3 4
15 15
0 0


Sample output:
5
43688

Submission status: Wrong Answer

Solution code:
for e in iter(input,'0 0'):
 w,h=map(int,e.split())
 M=[[[1,0]*2 for _ in[0]*h]for _ in[0]*w]
 for i in range(1,w):
  for j in range(1,h):
   a,b=M[i-1][j][:2]
   c,d=M[i][j-1][2:]
   M[i][j]=[d,a+b,b,c+d]
 for x in M:print(x)
 print(sum(M[w-2][h-1][:2])+sum(M[w-1][h-2][2:]))

Submission status: Wrong Answer

Solution code:
for e in iter(input,'0 0'):
 w,h=map(int,e.split())
 M=[[[1,0]*2 for _ in[0]*h]for _ in[0]*w]
 for i in range(1,w):
  for j in range(1,h):
   a,b=M[i-1][j][:2]
   c,d=M[i][j-1][2:]
   M[i][j]=[d,a+b,b,c+d]
 for x in M:print(x)
 print((sum(M[w-2][h-1][:2])+sum(M[w-1][h-2][2:]))%10**5)

Submission status: Accepted

Solution code:
while 1:
    w, h = map(int, raw_input().split())
    if w == 0: break
    dp = [[[0]*4 for i in range(w + 1)] for j in range(h + 1)]
    dp[1][0][0] = dp[0][1][3] = 1
    for i in range(h):
        for j in range(w):
            dp[i + 1][j][0] += dp[i][j][0] + dp[i][j][2]
            dp[i][j + 1][1] += dp[i][j][0]
            dp[i + 1][j][2] += dp[i][j][3]
            dp[i][j + 1][3] += dp[i][j][1] + dp[i][j][3]
    print reduce(lambda a, x: (a + x) % 100000, dp[h - 1][w - 1])

Submission status: Accepted

Solution code:
DIV = 100000
while 1:
    w, h = map(int, raw_input().split())
    if w == 0: break
    dp = [[[0]*4 for i in range(w + 1)] for j in range(h + 1)]
    dp[1][0][0] = dp[0][1][3] = 1
    for i in range(h):
        for j in range(w):
            dp[i + 1][j][0] += (dp[i][j][0] + dp[i][j][2]) % DIV
            dp[i][j + 1][1] += dp[i][j][0] % DIV
            dp[i + 1][j][2] += dp[i][j][3] % DIV
            dp[i][j + 1][3] += (dp[i][j][1] + dp[i][j][3]) % DIV
    print sum(dp[h - 1][w - 1]) % DIV

Submission status: Accepted

Solution code:
while True:
    w, h = map(int, input().split())
    if not w:
        break
    district = [[0] * w for _ in range(h)]

    district[0] = [(1, 0, 0, 0)] * w

    for i in range(1, h):
        row = district[i]
        row[0] = (0, 1, 0, 0)
        for j in range(1, w):
            left, under = row[j - 1], district[i - 1][j]
            row[j] = tuple(map(lambda x: x % 100000, (left[0] + left[2], under[1] + under[3], left[1], under[0])))

    print(sum(district[-1][-1]) % 100000)

Submission status: Accepted

Solution code:
while True:
    w,h = map(int,input().split())
    if w==0: break
    mapp = [[[0]*2 for _ in range(w+2)] for _ in range(h+2)]
    mapp[0][0][0] = mapp[0][0][1] = 1
    mapp[0][2][0] = mapp[2][0][1] = -1
    for i in range(0,h):
        for j in range(0,w):
            if i==h-1 and j==w-1 : break
            mapp[i][j+1][0] += mapp[i][j][0]
            if mapp[i][j+1][0] >= 100000: mapp[i][j+1][0] -= 100000
            mapp[i][j+2][0] += mapp[i][j][1]
            if mapp[i][j+2][0] >= 100000: mapp[i][j+2][0] -= 100000
            mapp[i+1][j][1] += mapp[i][j][1]
            if mapp[i+1][j][1] >= 100000: mapp[i+1][j][0] -= 100000
            mapp[i+2][j][1] += mapp[i][j][0]
            if mapp[i+2][j][1] >= 100000: mapp[i+2][j][0] -= 100000

    print(sum(mapp[h-1][w-1]+mapp[h][w-1]+mapp[h-1][w])%100000)

Submission status: Accepted

Solution code:
while True:
  h,w = map(int, input().split())
  if not h:
    break
#dp[R][U][""]
  h -= 1
  w -= 1
  mp = {(0,2,"UU") : 1, (2,0,"RR") : 1, (1,1,"UR") : 1, (1,1,"RU") : 1}
  for i in range(h + 1):
    for j in range(w + 1):
      if i + j <= 2:
        continue
      mp[(i, j, 'UU')] = 0
      if (i, j - 1, 'UU') in mp:
        mp[(i, j, 'UU')] += mp[(i, j - 1, 'UU')]
      if (i, j - 1, 'RU') in mp:
        mp[(i, j, 'UU')] += mp[(i, j - 1, 'RU')]
      mp[(i, j, 'RR')] = 0
      if (i - 1, j, 'RR') in mp:
        mp[(i, j, 'RR')] += mp[(i - 1, j, 'RR')]
      if (i - 1, j, 'UR') in mp:
        mp[(i, j, 'RR')] += mp[(i - 1, j, 'UR')]
      mp[(i, j, 'UR')] = 0
      if (i - 1, j, 'UU') in mp:
        mp[(i, j, 'UR')] += mp[(i - 1, j, 'UU')]
      mp[(i, j, 'RU')] = 0
      if (i, j - 1, 'RR') in mp:
        mp[(i, j, 'RU')] += mp[(i, j - 1, 'RR')]
  print((mp[(h, w, 'UU')] + mp[(h, w, 'UR')] + mp[(h, w, 'RU')] + mp[(h, w, 'RR')]) % 100000)

Submission status: Accepted

Solution code:
for e in iter(input,'0 0'):
 w,h=map(int,e.split())
 M=[[[1,0]*2 for _ in[0]*h]for _ in[0]*w]
 for i in range(1,w):
  for j in range(1,h):
   a,b=M[i-1][j][:2]
   c,d=M[i][j-1][2:]
   M[i][j]=[d,a+b,b,c+d]
 print((sum(M[w-2][h-1][:2])+sum(M[w-1][h-2][2:]))%10**5)

Submission status: Accepted

Solution code:
for e in iter(input,'0 0'):
 w,h=map(int,e.split())
 M=[[[1,0]*2 for _ in[0]*h]for _ in[0]*w]
 for i in range(1,w):
  for j in range(1,h):
   a,b,c,d=[*M[i-1][j][:2],*M[i][j-1][2:]]
   M[i][j]=[d,a+b,b,c+d]
 print((sum(M[w-2][h-1][:2])+sum(M[w-1][h-2][2:]))%10**5)

Submission status: Accepted

Solution code:
def s():
 for e in iter(input,'0 0'):
  w,h=map(int,e.split())
  M=[[[1,0]*2 for _ in[0]*h]for _ in[0]*w]
  for i in range(1,w):
   for j in range(1,h):
    a,b=M[i-1][j][:2]
    c,d=M[i][j-1][2:]
    M[i][j]=[d,a+b,b,c+d]
  print((sum(M[w-2][h-1][:2])+sum(M[w-1][h-2][2:]))%10**5)
if'__main__'==__name__:s()

Submission status: Accepted

Solution code:
def s():
 for e in iter(input,'0 0'):
  w,h=map(int,e.split())
  M=[[[1,0]*2 for _ in[0]*h]for _ in[0]*w]
  for i in range(1,w):
   for j in range(1,h):
    a,b=M[i-1][j][:2]
    c,d=M[i][j-1][2:]
    M[i][j]=[d,a+b,b,c+d]
  print((sum(M[w-2][h-1][:2])+sum(M[w-1][h-2][2:]))%10**5)
s()

Submission status: Accepted

Solution code:
# AOJ 0547: Commute routes
# Python3 2018.7.1 bal4u

import sys
from sys import stdin
input = stdin.readline

S, W = 0, 1
while True:
	w, h = map(int, input().split())
	if w == 0: break
	p = [[[[0 for a in range(2)] for b in range(2)] for c in range(h+1)] for d in range(w+1)]
	for x in range(1, w+1): p[x][1][W][S] = p[x][1][W][W] = 1
	for y in range(1, h+1): p[1][y][S][W] = p[1][y][S][S] = 1
	p[w][1][W][W] = p[1][h][S][S] = 0
	for y in range(2, h+1):
		for x in range(2, w+1):
			p[x][y][S][S] += p[x][y-1][S][S] + p[x][y-1][W][S]
			p[x][y][W][W] += p[x-1][y][W][W] + p[x-1][y][S][W]
			p[x][y][S][W] += p[x][y-1][S][S]
			p[x][y][W][S] += p[x-1][y][W][W]
			p[x][y][S][S] %= 100000
			p[x][y][W][W] %= 100000
			p[x][y][S][W] %= 100000
			p[x][y][W][S] %= 100000
	print((p[w][h][S][S]+p[w][h][W][W]) % 100000)

Submission status: Accepted

Solution code:
from pprint import pprint

while True:
  w, h = map(int, raw_input().split())

  if w == 0 and h == 0:
    break

  dp = [[[[0] * 2 for x in xrange(2) ] for w_ in xrange(w)] for h_ in xrange(h)]

  dp[0][0][0][1] = 1
  dp[0][0][1][1] = 1

  for x in xrange(w):
    for y in xrange(h):
      if x < w - 1:
        dp[y][x + 1][0][0] += dp[y][x][0][0] + dp[y][x][0][1]
        dp[y][x + 1][0][1] += dp[y][x][1][0]

      if y < h - 1:
        dp[y + 1][x][1][0] += dp[y][x][1][0] + dp[y][x][1][1]
        dp[y + 1][x][1][1] += dp[y][x][0][0]

  ans = sum(sum(a) for a in dp[h - 1][w - 1])
  print ans % 100000

Submission status: Accepted

Solution code:
dpw = [[0 for i in range(105)] for j in range(105)]
dph = [[0 for i in range(105)] for j in range(105)]
while 1:
    w,h = map(int,raw_input().split())
    if w==0 and h==0: break
    for i in range(h+2):
        for j in range(w+2): dpw[i][j] = dph[i][j] = 0;
    dpw[1][0] = dph[0][1] = 1
    for i in range(h):
        for j in range(w):
            if i==h-1 and j==w-1:break
            dph[j][i+1] += dph[j][i]; dpw[j+1][i] += dpw[j][i];
            dph[j][i+2] += dpw[j][i]; dpw[j+2][i] += dph[j][i];
    print (dpw[w-1][h-1]+dpw[w][h-1]+dph[w-1][h-1]+dph[w-1][h])%10**5

Submission status: Accepted

Solution code:
while True:
    w, h = map(int, raw_input().split())
    if w | h == 0:
        break
    dp = [[[0] * (w + 1) for _ in xrange(h + 1)] for _ in xrange(4)]    
    #0:u -> u, 1: u -> r, 2: r -> u, 3: r -> r
    dp[0][1][0] = dp[3][0][1] = 1
    for y in xrange(h):
        for x in xrange(w):
            dp[0][y + 1][x] += dp[0][y][x] + dp[2][y][x]
            dp[1][y][x + 1] += dp[0][y][x]
            dp[2][y + 1][x] += dp[3][y][x]
            dp[3][y][x + 1] += dp[1][y][x] + dp[3][y][x]
    print sum(dp[i][h-1][w-1] for i in xrange(4)) % 100000

Submission status: Accepted

Solution code:
while True:
    w, h = map(int, raw_input().split())
    if w | h == 0:
        break
    dp = [[[0] * (w + 1) for _ in xrange(h + 1)] for _ in xrange(4)]    
    dp[0][1][0] = dp[3][0][1] = 1
    for y in xrange(h):
        for x in xrange(w):
            dp[0][y + 1][x] += dp[0][y][x] + dp[2][y][x]
            dp[1][y][x + 1] += dp[0][y][x]
            dp[2][y + 1][x] += dp[3][y][x]
            dp[3][y][x + 1] += dp[1][y][x] + dp[3][y][x]
    print sum(dp[i][h-1][w-1] for i in xrange(4)) % 100000

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Commute routes
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0547

"""
import sys


def solve(width, height):
    # 北向き 直前に回転あり・回転なし、東向 直前に回転あり・回転なし
    dp = [[None] * width for _ in range(height)]
    dp[0][0] = [0, 1, 0, 1]
    for h in range(height):
        for w in range(width):
            if h == 0:
                dp[0][w] = [0, 0, 0, 1]
            elif w == 0:
                dp[h][0] = [0, 1, 0, 0]
            else:
                dp[h][w] = [dp[h-1][w][3], dp[h-1][w][0]+dp[h-1][w][1], dp[h][w-1][1], dp[h][w-1][2]+dp[h][w-1][3]]
    return sum(dp[-1][-1]) % 100000


def main(args):
    while True:
        w, h = map(int, input().split())
        if w == 0 and h == 0:
            break
        result = solve(w, h)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
def main():
    while True:
        import sys
        input=sys.stdin.readline
        w,h=map(int,input().split())
        if w==0:
            break
        dp=[[[0,0,0,0] for _ in [0]*(w+1)] for _ in [0]*(h+1)] #右直進、上直進、右、上
        dp[1][0]=[0,1,0,0]
        dp[0][1]=[1,0,0,0]
        mod=10**5
        for k in range(1,w+h-2):
            for j in range(max(0,k-h+1),min(w,k+1)):
                i=k-j
                dp[i+1][j][1]=(dp[i+1][j][1]+dp[i][j][1]+dp[i][j][3])%mod
                dp[i+1][j][3]=(dp[i+1][j][3]+dp[i][j][0])%mod
                dp[i][j+1][0]=(dp[i][j+1][0]+dp[i][j][0]+dp[i][j][2])%mod
                dp[i][j+1][2]=(dp[i][j+1][2]+dp[i][j][1])%mod
        print(sum(dp[h-1][w-1])%mod)
if __name__=='__main__':
    main()

Submission status: Runtime Error

Solution code:
for e in iter(input,'0 0'):
 w,h=map(int,e.split())
 M=[[[1,0]*2 for _ in[0]*h]for _ in[0]*w]
 for i in range(1,w):
  for j in range(1,h):
   a=M[i-1][j][:2]
   b=M[i][j-1][2:]
   M[i][j]=[b[1],a,a[1],b]
 print((sum(M[w-2][h-1][:2])+sum(M[w-1][h-2][2:]))%10**5)

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations

def main():
	while True:
		n = input()
		k = input()
		if n == k == 0:
			return 0
		for i in xrange(n):
			input()
		print "a"
#		nums = [raw_input().strip() for i in xrange(n)]
#		result = set(["".join(p) for p in permutations(nums, k)])
#		print (len(result))

if __name__ == '__main__':
	sys.exit(main())