Problem:


Problem B : Grid

r × c の2次元グリッド上の２つの座標 (a1,a2) と (b1,b2) が与えられる。
あるマス (e,f) から (e+1,f)、(e-1,f)、(e,f+1)、(e,f-1) のどれかのマスに移動するコストを１とする。
また、(e,c-1) と (e,0)、(r-1,f) と (0,f) の間もコスト１で移動することができる。
この時に１つ目の座標から２つ目の座標へ最短コストで移動できる経路の数を求めよ。

Input

入力は以下のフォーマットで与えられる。

r c a1 a2 b1 b2

入力は以下の制約を満たす

1 ≤ r , c ≤ 1,000

0 ≤ a1 , b1 < r

0 ≤ a2 , b2 < c

Output

答えの値を100,000,007で割った余りを出力せよ。

Sample Input 1

4 4 0 0 3 3

Sample Output 1

2

Sample Input 2

4 4 0 0 1 1

Sample Output 2

2

Sample Input 3

2 3 0 0 1 2

Sample Output 3

4

Sample Input 4

500 500 0 0 200 200

Sample Output 4

34807775



Sample input:
4 4 0 0 3 3


Sample output:
2

Submission status: Wrong Answer

Solution code:
# Edit: 2014/09/09
# Lang: Python2
# Time: .00s

from itertools import product
from math import factorial

if __name__ == "__main__":
    # a, b, c, d, e, f = map(int, input().strip("\n").split(" "))
    r, c, ar, ac, br, bc = map(int, raw_input().strip("\n").split(" "))
    maxans = 100000007  # 100,000,007
    # maxn =   100000007

    # tate Row
    dr = abs(br - ar)
    if dr == r / 2:
        dr = dr
        gainr = 2
    elif dr > r / 2:
        dr = r - dr
        gainr = 1
    else:
        dr = dr
        gainr = 1

    # yoko Column
    dc = abs(bc - ac)
    if dc == r / 2:
        dc = dc
        gainc = 2
    elif dc > r / 2:
        dc = c - dc
        gainc = 1
    else:
        dc = dc
        gainc = 1

    dr = 200  # int(dr)
    dc = 200  # int(dc)
    gainr = int(gainr)
    gainc = int(gainc)

    #print(dr, dc)
    #print(gainr, gainc)

    """
    ans = 0
    a = factorial(400) % maxans
    b = factorial(200) % maxans
    c = factorial(200) % maxans
    ans = int(a / b / c)
    print(a)
    print(b)
    """
    #ans = factorial(dr + dc) / factorial(dr) / factorial(dc) # * gainr * gainc
    # python overflow error integer division result too large for a float

    ans = factorial(dr + dc) / factorial(dr) / factorial(dc) * gainr * gainc

    # t = 1
    #for i in range(dr, dr + dc):
    #print(t)
    #    t *= i
    #ans = t / factorial(dc) * gainr * gainc

    #print(ans)
    print(ans % maxans)

    # print("34807775")
    #67,352,549

Submission status: Wrong Answer

Solution code:
# Edit: 2014/09/09
# Lang: Python2
# Time: .00s

from itertools import product
from math import factorial

if __name__ == "__main__":
    # a, b, c, d, e, f = map(int, input().strip("\n").split(" "))
    r, c, ar, ac, br, bc = map(int, raw_input().strip("\n").split(" "))
    maxans = 100000007  # 100,000,007
    # maxn =   100000007

    # tate Row
    dr = abs(br - ar)
    if dr == r / 2:
        dr = dr
        gainr = 2
    elif dr > r / 2:
        dr = r - dr
        gainr = 1
    else:
        dr = dr
        gainr = 1

    # yoko Column
    dc = abs(bc - ac)
    if dc == r / 2:
        dc = dc
        gainc = 2
    elif dc > r / 2:
        dc = c - dc
        gainc = 1
    else:
        dc = dc
        gainc = 1

    dr = int(dr)
    dc = int(dc)
    gainr = int(gainr)
    gainc = int(gainc)

    #print(dr, dc)
    #print(gainr, gainc)

    """
    ans = 0
    a = factorial(400) % maxans
    b = factorial(200) % maxans
    c = factorial(200) % maxans
    ans = int(a / b / c)
    print(a)
    print(b)
    """
    #ans = factorial(dr + dc) / factorial(dr) / factorial(dc) # * gainr * gainc
    # python overflow error integer division result too large for a float

    ans = factorial(dr + dc) / factorial(dr) / factorial(dc) * gainr * gainc

    # t = 1
    #for i in range(dr, dr + dc):
    #print(t)
    #    t *= i
    #ans = t / factorial(dc) * gainr * gainc

    #print(ans)
    print(ans % maxans)

    # print("34807775")
    #67,352,549

Submission status: Wrong Answer

Solution code:
# Edit: 2014/09/09
# Lang: Python3
# Time: .00s

from itertools import product
from math import factorial

if __name__ == "__main__":
    # a, b, c, d, e, f = map(int, input().strip("\n").split(" "))
    r, c, ar, ac, br, bc = map(int, input().strip("\n").split(" "))
    maxans = 100000007  # 100,000,007
    # maxn =   100000007

    # tate Row
    dr = abs(br - ar)
    if dr == r / 2:
        dr = dr
        gainr = 2
    elif dr > r / 2:
        dr = r - dr
        gainr = 1
    else:
        dr = dr
        gainr = 1

    # yoko Column
    dc = abs(bc - ac)
    if dc == r / 2:
        dc = dc
        gainc = 2
    elif dc > r / 2:
        dc = c - dc
        gainc = 1
    else:
        dc = dc
        gainc = 1

    dr = int(dr)
    dc = int(dc)
    gainr = int(gainr)
    gainc = int(gainc)

    #print(dr, dc)
    #print(gainr, gainc)

    """
    ans = 0
    a = factorial(400) % maxans
    b = factorial(200) % maxans
    c = factorial(200) % maxans
    ans = int(a / b / c)
    print(a)
    print(b)
    """
    #ans = factorial(dr + dc) / factorial(dr) / factorial(dc) # * gainr * gainc
    # python overflow error integer division result too large for a float

    ans = factorial(dr + dc) // factorial(dr) // factorial(dc) * gainr * gainc

    # t = 1
    #for i in range(dr, dr + dc):
    #print(t)
    #    t *= i
    #ans = t / factorial(dc) * gainr * gainc

    #print(ans)
    print(ans % maxans)

    # print("34807775")
    #67,352,549

Submission status: Wrong Answer

Solution code:
# coding: utf-8
def fact(n):
    res = 1
    while n:
        res *= n
        n -= 1
    return res

r,c,a1,a2,b1,b2 = map(int,raw_input().split())
db1,db2 = abs(a1-b1),abs(a2-b2)
c1,c2,d1,d2,e1,e2 = r-db1,b2, b1,c-db2, r-db1,c-db2
print a1,a2,b1,b2,c1,c2,d1,d2,e1,e2
dc1,dc2,dd1,dd2,de1,de2 = abs(a1-c1),abs(a2-c2),abs(a1-d1),abs(a2-d2),abs(a1-e1),abs(a2-e2)
dx,dy = sorted( [[db1,db2],[dc1,dc2],[dd1,dd2],[de1,de2]], key = lambda x:sum(x))[0]
k = [[db1,db2],[dc1,dc2],[dd1,dd2],[de1,de2]].count([dx,dy])
ans  = fact(dx+dy)/fact(dx)/fact(dy)%100000007
print k*ans%100000007

Submission status: Wrong Answer

Solution code:
# coding: utf-8
def fact(n):
    res = 1
    while n:
        res *= n
        n -= 1
    return res

r,c,a1,a2,b1,b2 = map(int,raw_input().split())
db1,db2 = abs(a1-b1),abs(a2-b2)
c1,c2,d1,d2,e1,e2 = r-db1,b2, b1,c-db2, r-db1,c-db2
dc1,dc2,dd1,dd2,de1,de2 = abs(a1-c1),abs(a2-c2),abs(a1-d1),abs(a2-d2),abs(a1-e1),abs(a2-e2)
dx,dy = sorted( [[db1,db2],[dc1,dc2],[dd1,dd2],[de1,de2]], key = lambda x:sum(x))[0]
k = [[db1,db2],[dc1,dc2],[dd1,dd2],[de1,de2]].count([dx,dy])
ans  = fact(dx+dy)/fact(dx)/fact(dy)%100000007
print k*ans%100000007

Submission status: Wrong Answer

Solution code:
# coding: utf-8
def f(n):
    res = 1
    while n:
        res *= n
        n -= 1
    return res

r,c,a1,a2,b1,b2 = map(int,raw_input().split())
db1,db2 = abs(a1-b1),abs(a2-b2)
c1,c2,d1,d2,e1,e2 = r-db1,b2, b1,c-db2, r-db1,c-db2
dc1,dc2,dd1,dd2,de1,de2 = abs(a1-c1),abs(a2-c2),abs(a1-d1),abs(a2-d2),abs(a1-e1),abs(a2-e2)
a1 = f(db1+db2)/f(db1)/f(db2)%100000007
a2 = f(dc1+dc2)/f(dc1)/f(dc2)%100000007
a3 = f(dd1+dd2)/f(dd1)/f(dd2)%100000007
a4 = f(de1+de2)/f(de1)/f(de2)%100000007
ans = min(a1,a2,a3,a4)
k = [a1,a2,a3,a4].count(ans)
print k*ans%100000007

Submission status: Wrong Answer

Solution code:
def func (x):
	if x:
		return int(x)*func(x-1)
	else:
		return (1)
def comb (x,y):
	return func(x)//func(x-y)//func(y)

h,w,ax,ay,bx,by=map(int,input().split())
dx=min(w-abs(ax-bx),abs(ax-bx))
dy=min(h-abs(ay-by),abs(ay-by))
ans=1
if dx*2==w:ans*=2
if dy*2==h:ans*=2
ans*=comb(dx+dy,dx)
print(ans%100000007)

Submission status: Wrong Answer

Solution code:
from math import factorial
def comb (x,y):
	return factorial(x)//factorial(x-y)//factorial(y)

w,h,ax,ay,bx,by=map(int,input().split())
dx=abs(ax-bx)
dx=min(dx,w-dx)
dy=abs(ay-by)
dy=min(dy,h-dy)
an=1
if dx*2==w:an*=2
if dy*2==h:an*=2
an*=comb(dx+dy,dx)
print(an%int(1E9+7))

Submission status: Accepted

Solution code:
# AOJ 1501: Grid
# Python3 2018.7.13 bal4u

MOD = 100000007
def dp(n, k):
	if tbl[n][k]: return tbl[n][k]
	if (k << 1) > n: k = n-k
	if k == 0: ans = 1
	elif k == 1: ans = n
	else: ans = dp(n-1, k) + dp(n-1, k-1)
	tbl[n][k] = ans % MOD
	return tbl[n][k]

tbl = [[0 for j in range(1001)] for i in range(1001)]
k = 0
r, c, a1, a2, b1, b2 = map(int, input().split())

dr = abs(a1-b1)
if dr > r-dr: dr = r-dr
if (dr << 1) == r: k += 1

dc = abs(a2-b2)
if dc > c-dc: dc = c-dc
if (dc << 1) == c: k += 1

print((dp(dr+dc, min(dr, dc)) << k) % MOD)

Submission status: Accepted

Solution code:
# AOJ 1501: Grid
# Python3 2018.7.13 bal4u

from math import factorial
def comb (n, k):
	return factorial(n)//factorial(n-k)//factorial(k)
	
k = 0
r, c, a1, a2, b1, b2 = map(int, input().split())

dr = abs(a1-b1)
if dr > r-dr: dr = r-dr
if (dr << 1) == r: k += 1

dc = abs(a2-b2)
if dc > c-dc: dc = c-dc
if (dc << 1) == c: k += 1

print((comb(dr+dc, min(dr, dc)) << k) % 100000007)

Submission status: Accepted

Solution code:
# Edit: 2014/09/09
# Lang: Python3
# Time: .00s

from math import factorial

if __name__ == "__main__":
    # a, b, c, d, e, f = map(int, input().strip("\n").split(" "))
    r, c, ar, ac, br, bc = map(int, input().strip("\n").split(" "))
    maxans = 100000007  # 100,000,007
    # maxn =   100000007

    # tate Row
    dr = min(abs(br - ar), r - abs(br - ar))
    if 2 * dr == r:
        gainr = 2
    else:
        gainr = 1

    # yoko Column
    dc = min(abs(bc - ac), c - abs(bc - ac))
    if 2 * dc == c:
        gainc = 2
    else:
        gainc = 1

    #dr = int(dr)
    #dc = int(dc)
    #gainr = int(gainr)
    #gainc = int(gainc)

    # print(dr, dc)
    # print(gainr, gainc)

    ans1 = factorial(dr+dc)
    #print("ans1",ans1)
    #print("type",type(ans1))

    ans2 = factorial(dr)
    #print("ans2",ans2)
    #print("type",type(ans2))

    ans3 = factorial(dc)
    #print("ans3",ans3)
    #print("type",type(ans3))

    ans4 = ans1//ans2//ans3*gainr*gainc
    #print("ans4",ans4)
    #print("type",type(ans4))

    ans = ans4
    ## ans = factorial(dr + dc) / factorial(dr) / factorial(dc) # * gainr * gainc
    # python overflow error integer division result too large for a float

    #ans = factorial(dr + dc) // factorial(dr) // factorial(dc) * gainr * gainc


    # t = 1
    #for i in range(dr, dr + dc):
    #print(t)
    #    t *= i
    #ans = t / factorial(dc) * gainr * gainc

    #print(ans)
    #print(ans, type(ans))
    print(ans % maxans)

    # print("34807775")
    #67,352,549

Submission status: Accepted

Solution code:
# Edit: 2014/09/09
# Lang: Python3
# Time: .00s

from math import factorial

if __name__ == "__main__":
    r, c, ar, ac, br, bc = map(int, input().strip("\n").split(" "))
    maxans = 100000007  # 100,000,007

    # tate Row
    dr = min(abs(br - ar), r - abs(br - ar))
    if 2 * dr == r:
        gainr = 2
    else:
        gainr = 1

    # yoko Column
    dc = min(abs(bc - ac), c - abs(bc - ac))
    if 2 * dc == c:
        gainc = 2
    else:
        gainc = 1

    #dr = int(dr)
    #dc = int(dc)
    #gainr = int(gainr)
    #gainc = int(gainc)

    # print(dr, dc)
    # print(gainr, gainc)

    #ans1 = factorial(dr+dc)
    #print("ans1",ans1)
    #print("type",type(ans1))

    #ans2 = factorial(dr)
    #print("ans2",ans2)
    #print("type",type(ans2))

    #ans3 = factorial(dc)
    #print("ans3",ans3)
    #print("type",type(ans3))

    #ans4 = ans1//ans2//ans3*gainr*gainc
    #print("ans4",ans4)
    #print("type",type(ans4))

    #ans = ans4
    ## ans = factorial(dr + dc) / factorial(dr) / factorial(dc) # * gainr * gainc
    # python overflow error integer division result too large for a float

    ans = factorial(dr + dc) // factorial(dr) // factorial(dc) * gainr * gainc


    # t = 1
    #for i in range(dr, dr + dc):
    #print(t)
    #    t *= i
    #ans = t / factorial(dc) * gainr * gainc

    #print(ans)
    #print(ans, type(ans))
    print(ans % maxans)

    # print("34807775")
    #67,352,549

Submission status: Accepted

Solution code:
# Edit: 2014/09/17
# Lang: Python3
# Time: 00.04s

from math import factorial

if __name__ == "__main__":
    r, c, ar, ac, br, bc = map(int, input().strip("\n").split(" "))
    maxans = 100000007  # 100,000,007

    # tate Row
    dr = min(abs(br - ar), r - abs(br - ar))
    if 2 * dr == r:
        gainr = 2
    else:
        gainr = 1

    # yoko Column
    dc = min(abs(bc - ac), c - abs(bc - ac))
    if 2 * dc == c:
        gainc = 2
    else:
        gainc = 1

    ans = factorial(dr + dc) // factorial(dr) // factorial(dc) * gainr * gainc

    print(ans % maxans)

Submission status: Accepted

Solution code:
def func (x):
	if x:
		return int(x)*func(x-1)
	else:
		return (1)
def comb (x,y):
	return func(x)//func(x-y)//func(y)

import sys
sys.setrecursionlimit(10000)
w,h,ax,ay,bx,by=map(int,input().split())
dx=min(w-abs(ax-bx),abs(ax-bx))
dy=min(h-abs(ay-by),abs(ay-by))
ans=1
if dx*2==w:ans*=2
if dy*2==h:ans*=2
ans*=comb(dx+dy,dx)
print(ans%100000007)

Submission status: Accepted

Solution code:
import sys
from math import factorial
sys.setrecursionlimit(10000)
def comb (x,y):
	return factorial(x)//factorial(x-y)//factorial(y)

w,h,ax,ay,bx,by=map(int,input().split())
dx=min(w-abs(ax-bx),abs(ax-bx))
dy=min(h-abs(ay-by),abs(ay-by))
ans=1
if dx*2==w:ans*=2
if dy*2==h:ans*=2
ans*=comb(dx+dy,dx)
print(ans%100000007)

Submission status: Accepted

Solution code:
from math import factorial
def comb (x,y):
	return factorial(x)//factorial(x-y)//factorial(y)

w,h,ax,ay,bx,by=map(int,input().split())
dx=min(w-abs(ax-bx),abs(ax-bx))
dy=min(h-abs(ay-by),abs(ay-by))
ans=1
if dx*2==w:ans*=2
if dy*2==h:ans*=2
ans*=comb(dx+dy,dx)
print(ans%100000007)

Submission status: Accepted

Solution code:
from math import factorial
def comb (x,y):
	return factorial(x)//factorial(x-y)//factorial(y)

w,h,ax,ay,bx,by=map(int,input().split())
dx=abs(ax-bx)
dx=min(dx,w-dx)
dy=abs(ay-by)
dy=min(dy,h-dy)
ans=1
if dx*2==w:ans*=2
if dy*2==h:ans*=2
ans*=comb(dx+dy,dx)
print(ans%100000007)

Submission status: Accepted

Solution code:
from math import factorial
def comb (x,y):
	return factorial(x)//factorial(x-y)//factorial(y)

w,h,ax,ay,bx,by=map(int,input().split())
dx=abs(ax-bx)
dx=min(dx,w-dx)
dy=abs(ay-by)
dy=min(dy,h-dy)
an=1
if dx*2==w:an*=2
if dy*2==h:an*=2
an*=comb(dx+dy,dx)
print(an%int(1E8+7))

Submission status: Accepted

Solution code:
mod = 10**8+7
n = 1001

def comb(x, y):
    if 2*y > x: return comb(x, x-y)
    return fac[x] * inv[y]* inv[x-y] % mod

fac = [1]*(n+1)
inv = [1]*(n+1)
for i in range(2, n+1):
    fac[i] = fac[i-1] * i % mod
inv[n] = pow(fac[n], mod-2, mod)
for i in range(n-1, 1, -1):
    inv[i] = inv[i+1] * (i+1) % mod

r, c, a1, a2, b1, b2 = map(int, input().split())

row = min(abs(b1-a1), r-abs(b1-a1))
col = min(abs(b2-a2), ｃ-abs(b2-a2))

ans = 1
if row*2 == r: ans *= 2
if col*2 == c: ans *= 2

ans *= comb(row+col, row)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 100000007
r, c, a1, a2, b1, b2 = map(int, input().split())
dx = abs(a1 - b1)
dy = abs(a2 - b2)
cnt = 1
if dx * 2 == r:cnt *= 2
if dy * 2 == c:cnt *= 2
dx = min(dx, r - dx)
dy = min(dy, c - dy)

dp = [[0] * (dx + 2) for _ in range(dy + 2)]
dp[0][1] = 1
for y in range(1, dy + 2):
    for x in range(1, dx + 2):
        dp[y][x] = (dp[y - 1][x] + dp[y][x - 1]) % MOD
print(dp[dy + 1][dx + 1] * cnt % MOD)

Submission status: Runtime Error

Solution code:
def func (x):
	if x:
		return int(x)*func(x-1)
	else:
		return (1)
def comb (x,y):
	return func(x)//func(x-y)//func(y)

w,h,ax,ay,bx,by=map(int,input().split())
dx=min(w-abs(ax-bx),abs(ax-bx))
dy=min(h-abs(ay-by),abs(ay-by))
ans=1
if dx*2==w:ans*=2
if dy*2==h:ans*=2
ans*=comb(dx+dy,dx)
print(ans%100000007)

Submission status: Runtime Error

Solution code:
import math
def comb (x,y):
	return factorial(x)//factorial(x-y)//factorial(y)

w,h,ax,ay,bx,by=map(int,input().split())
dx=min(w-abs(ax-bx),abs(ax-bx))
dy=min(h-abs(ay-by),abs(ay-by))
ans=1
if dx*2==w:ans*=2
if dy*2==h:ans*=2
ans*=comb(dx+dy,dx)
print(ans%100000007)