Problem:


Score : 400 points

Problem Statement

We have a grid with H rows and W columns. The square at the i-th row and the j-th column will be called Square (i,j).

The integers from 1 through H×W are written throughout the grid, and the integer written in Square (i,j) is A_{i,j}.

You, a magical girl, can teleport a piece placed on Square (i,j) to Square (x,y) by consuming |x-i|+|y-j| magic points.

You now have to take Q practical tests of your ability as a magical girl.

The i-th test will be conducted as follows:

Initially, a piece is placed on the square where the integer L_i is written.

Let x be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer x+D is written, as long as x is not R_i. The test ends when x=R_i.

Here, it is guaranteed that R_i-L_i is a multiple of D.

For each test, find the sum of magic points consumed during that test.

Constraints

1 \leq H,W \leq 300

1 \leq D \leq H×W

1 \leq A_{i,j} \leq H×W

A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))

1 \leq Q \leq 10^5

1 \leq L_i \leq R_i \leq H×W

(R_i-L_i) is a multiple of D.

Input

Input is given from Standard Input in the following format:

H W D
A_{1,1} A_{1,2} ... A_{1,W}
:
A_{H,1} A_{H,2} ... A_{H,W}
Q
L_1 R_1
:
L_Q R_Q

Output

For each test, print the sum of magic points consumed during that test.

Output should be in the order the tests are conducted.

Sample Input 1

3 3 2
1 4 3
2 5 7
8 9 6
1
4 8

Sample Output 1

5

4 is written in Square (1,2).

6 is written in Square (3,3).

8 is written in Square (3,1).

Thus, the sum of magic points consumed during the first test is (|3-1|+|3-2|)+(|3-3|+|1-3|)=5.

Sample Input 2

4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2

Sample Output 2

0
0

Note that there may be a test where the piece is not moved at all, and there may be multiple identical tests.

Sample Input 3

5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13

Sample Output 3

0
5
0



Sample input:
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8


Sample output:
5

Submission status: Runtime Error

Solution code:
h,w,d=[int(i) for i in input().split()]
p=[[-1,-1] for i in range(h*w+1) ]
a=[]
for i in range(h):
  a0 =[int(i0) for i0 in input().split()]
  a.append(a0)
  for j in range(w):
    p[a0[j]]=[i,j]

n=int(input())

import sys
sys.setrecursionlimit(100000)
from functools import lru_cache

@lru_cache(maxsize=1000)
def dist_d(s,g,d,y0,x0):
  if s==g:
    return 0
  else:
    s = s+d
    y,x = p[s]
    return abs(x-x0)+abs(y-y0) + dist_d(s,g,d,y,x)
  
for i in range(n):
  z=0
  s,g=[int(i0) for i0 in input().split()]
  y0,x0=p[s]
  print(dist_d(s,g,d,y0,x0))

Submission status: Runtime Error

Solution code:
temp = list(map(int,input().split()))
H = temp[0]
W = temp[1]
D = temp[2]
dic = [0 for x in range(H*W)]
for i in range(H):
    temp = list(map(int,input().split()))
    for j in range(len(temp)):
        ad = [str(i),str(j)]
        key = " ".join(ad)
        dic[temp[j]] = key

Q = int(input())
end = {}
for i in range(Q):
    tot = input().split()
    temp = list(map(int,tot))
    L = temp[0]
    R = temp[1]
    literature = " ".join(tot)
    length = 0
    if L == R:
        print(0)
    elif literature in end.keys():
        print(int(end[literature]))
    else:
        Lt = L
        for j in range(int((R-L)/D)):
            pre = list(map(int,dic[Lt].split()))
            pro = list(map(int,dic[Lt+D].split()))
            length += abs(pre[0]-pro[0]) + abs(pre[1]-pro[1])
            Lt = Lt+D
        print(length)
        end[literature] = str(length)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

H, W, D = map(int, raw_input().split())
A = []
for i in range(H):
	A.append(map(int, raw_input().split()))
Q = input()
LR = []
for i in range(Q):
	LR.append(map(int, raw_input().split()))

def search_index(num, arr, height):
	for i in range(height):
		if arr[i] in num:
			return i,arr.index(num)
	return -1,-1

maryoku = 0
for i in range(Q):
	ori_i,ori_j = search_index(LR[i][0], A, H)
	x = A[ori_i][ori_j]
	while x == LR[i][1]:
		x += D
		tra_i,tra_j = search_index(x, A, H)
		maryoku += abs(tra_i-ori_i) + abs(tra_j-ori_i)
		ori_i, ori_j = tra_i, tra_j
print maryoku

Submission status: Runtime Error

Solution code:
import collections
import itertools
from pprint import pprint as pp

H,W,D = tuple(map(int, input().split()))
A = [tuple(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [tuple(map(int, input().split())) for _ in range(Q)]

Arev = [None] * (H*W+1)
for h in range(H):
  for w in range(W):
    Arev[A[h][w]] = (h,w)

tbl = []
for i in range(D):
  i += 1
  ary = []
  mp = 0
  start = Arev[i]
  for x in range(i, H*W, D):
    next_ = Arev[x]
    mp += abs(start[0]-next_[0]) + abs(start[1]-next_[1])
    ary.append((x,mp))
    start = next_
  tbl.append(ary)
for L,R in LR:
  col1, row = divmod(L, D)
  col2 = R // D
  if row == 0:
    col1 -= 1
    col2 -= 1
  row -= 1
  print(tbl[row][col2][1] - tbl[row][col1][1])

Submission status: Runtime Error

Solution code:
import collections
import itertools
from pprint import pprint as pp

H,W,D = tuple(map(int, input().split()))
A = [tuple(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [tuple(map(int, input().split())) for _ in range(Q)]

Arev = [None] * (H*W+1)
for h in range(H):
  for w in range(W):
    Arev[A[h][w]] = (h,w)

tbl = []
for i in range(D):
  i += 1
  ary = []
  mp = 0
  start = Arev[i]
  for x in range(i, H*W, D):
    next_ = Arev[x]
    mp += abs(start[0]-next_[0]) + abs(start[1]-next_[1])
    ary.append((x,mp))
    start = next_
  tbl.append(ary)
pp(tbl)
for L,R in LR:
  col1, row = divmod(L, D)
  col2 = R // D
  if row == 0:
    col1 -= 1
    col2 -= 1
  row -= 1
  pp((row,col1,col2))
  print(tbl[row][col2][1] - tbl[row][col1][1])

Submission status: Runtime Error

Solution code:
H,W,D = map(int,input().split(" "))
field = []
power = 0
for i in range(H):
    field.append(list(map(int,input().split(" "))))
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split(" "))
    point = field.index(L)

    while L != R:
        point = field.index(L)
        x1 = int(point/W)+1
        y1 = point%W + 1
        L = L + D
        point2 = field.index(L)
        x2 = int(point/W)+1
        y2 = point%W + 1

        power = power + abs(x1-x2) + abs(y1-y2)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

H, W, D = map(int, raw_input().split())
A = []
for i in range(H):
	A.append(map(int, raw_input().split()))
Q = input()
LR = []
for i in range(Q):
	LR.append(map(int, raw_input().split()))

def search_index(num, arr, height):
	for i in range(height):
		if num in arr[i]:
			return i,arr.index(num)
	return -1,-1
maryoku = 0
for i in range(Q):
	ori_i,ori_j = search_index(LR[i][0], A, H)
	x = A[ori_i][ori_j]
	while x == LR[i][1]:
		x += D
		tra_i,tra_j = search_index(x, A, H)
		maryoku += abs(tra_i-ori_i) + abs(tra_j-ori_i)
		ori_i, ori_j = tra_i, tra_j
print maryoku

Submission status: Runtime Error

Solution code:
from math import *

inp = input().split(' ')
H = int(inp[0]); W = int(inp[1]); D = int(inp[2])
A_ = [None for _ in range(H * W + 1)]
for y in range(H):
  line = input().split(' ')
  for x in range(W):
    A_[int(line[x])] = (x, y)
Q = int(input())
for _ in range(Q):
  inp = input().split(' ')
  n = int(inp[0])
  R = int(inp[1])
  e = 0
  while n is not R:
    (x, y) = A_[n]
    n += D
    (x_, y_) = A_[n]
    e += abs(x - x_) + abs(y - y_)
  print(e)

Submission status: Runtime Error

Solution code:
H,W,D = map(int,input().split(" "))
field = [] 
power = 0
for i in range(H):
    field.extend(list(map(int,input().split(" "))))
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split(" "))
    point = field.index(L)

    while L =/ R:
        point = field.index(L)
        x1 = int(point/W)+1
        y1 = point%W + 1
        L = L + D
        point2 = field.index(L)
        x2 = int(point/W)+1
        y2 = point%W + 1

        power = power + abs(x1-x2) + abs(y1-y2)

Submission status: Runtime Error

Solution code:
import sys
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

dp = {}

def dp_search(L, R, D, num_dic):
    global dp
    if (L, R) in dp:
        return dp[(L, R)]
    if L== R:
        return 0

    if L + D == R:
        now_pos = num_dic[L]
        next_pos = num_dic[R]
        dp[(L, R)] =  abs(next_pos[0] - now_pos[0]) + abs(next_pos[1] - now_pos[1])
        return dp[(L, R)]

    dp[(L, R)] = dp_search(L , R - D, D , num_dic) + dp_search(L + D , R, D , num_dic)

    return dp[(L, R)]


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, D] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    num_dic= {}
    for i in range(H):
        input_raw = read_func().strip().split()
        for j in range(W):
            num_dic[int(input_raw[j])] = (i, j)
    input_raw = read_func().strip().split()
    [Q] = [int(input_raw[0])]
    test_list = []
    for i in range(Q):
        input_raw = read_func().strip().split()
        test_list.append((int(input_raw[0]), int(input_raw[1])))

    dp = [[0 for i in range(H)] for j in range(W)]
    for test in test_list:
        L = test[0]
        R = test[1]
        print dp_search(L,R,D,num_dic)




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

dp = [[0 for i in range(300)] for j in range(300)]

dp = {}

def dp_search(L, R, D, num_dic):
    global dp
    if (L, R) in dp:
        return dp[(L, R)]
    if L== R:
        return 0

    if L + D == R:
        now_pos = num_dic[L]
        next_pos = num_dic[R]
        dp[(L, R)] =  abs(next_pos[0] - now_pos[0]) + abs(next_pos[1] - now_pos[1])
        return dp[(L, R)]

    dp[(L, R)] = dp_search(L , R - D, D , num_dic) + dp_search(L + D , R, D , num_dic)

    return dp[(L, R)]


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, D] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    num_dic= {}
    for i in range(H):
        input_raw = read_func().strip().split()
        for j in range(W):
            num_dic[int(input_raw[j])] = (i, j)
    input_raw = read_func().strip().split()
    [Q] = [int(input_raw[0])]
    test_list = []
    for i in range(Q):
        input_raw = read_func().strip().split()
        test_list.append((int(input_raw[0]), int(input_raw[1])))

    dp = [[0 for i in range(H)] for j in range(W)]
    for test in test_list:
        L = test[0]
        R = test[1]
        print dp_search(L,R,D,num_dic)




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())

H,W,D = Is()
d = dict()
for i in range(H):
    s = Is()
    for j,e in enumerate(s):
        d[e] = (i,j)
Q = I()

m = [[0]*H*W for i in range(H*W)] 
def calc(l,r):
    if m[l][r] != 0:
        return m[l][r]
    else:
        maho = 0
        for k in range(l,r,D):
            maho += abs(d[k+D][0] - d[k][0]) + abs(d[k+D][1] - d[k][1])
        m[l][r] = maho
        return maho
    
for q in range(Q):
    l,r = Is()
    maho = calc(l,r)
    print(maho)

Submission status: Runtime Error

Solution code:
def solve():
    h, w, d = map(int, input().split())

    a = [(0,0) for i in range(h*w+1)]
    for y in range(h):
        row = list(map(int, input().split()))
        for x, v in enumerate(row):
            a[v] = (x, y)

    q = int(input())

    l, r = [], []

    for i in range(q):
        l_, r_ = map(int, input().split())
        l.append(l_)
        r.append(r_)

    # print(h, w, d)
    # print(a)
    # print(l, r)

    from collections import defaultdict
    memo = defaultdict(int)

    def magic(fr, to, d, m):
        if to-fr == 0:
            return 0

        if (to-fr) // d == 1:
            frx, fry = a[fr]
            tox, toy = a[to]
            dist = abs(frx-tox) + abs(fry-toy)
            # print(fr, to, dist)
            memo[(fr, to)] = dist
            return m + dist

        else:
            last = memo[(to - d, to)]
            if last == 0:
                last = magic(to - d, to, d, m)
                memo[(to - d, to)] = last

            rest = memo[(fr, to-d)]
            if rest == 0:
                rest = magic(fr, to-d, d, m)
                memo[(fr, to - d)] = rest

            return  last + rest

    for qi in range(q):
        ans = magic(l[qi], r[qi], d, 0)
        print(ans)

solve()

Submission status: Runtime Error

Solution code:
from math import *

inp = input().split(' ')
H = int(inp[0]); W = int(inp[1]); D = int(inp[2])
A = [list(map(lambda x: int(x), input().split(' '))) for _ in range(H)]
Q = int(input())
A_ = [None for _ in range(H * W + 1)]
for y in range(H):
  for x in range(W):
    A_[A[y][x]] = (x, y)
for _ in range(Q):
  inp = input().split(' ')
  n = int(inp[0])
  R = int(inp[1])
  e = 0
  while n is not R:
    (x, y) = A_[n]
    n += D
    (x_, y_) = A_[n]
    e += abs(x - x_) + abs(y - y_)
  print(e)

Submission status: Runtime Error

Solution code:
import sys
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

dp = [[0 for i in range(300)] for j in range(300)]

def dp_search(L, R, D, num_dic):
    global dp
    if dp[L][R] != 0:
        return dp[L][R]
    if L== R:
        return 0

    if L + D == R:
        now_pos = num_dic[L]
        next_pos = num_dic[R]
        dp[L][R] =  abs(next_pos[0] - now_pos[0]) + abs(next_pos[1] - now_pos[1])
        return dp[L][R]

    dp[L][R] = dp_search(L , R - D, D , num_dic) + dp_search(L + D , R, D , num_dic)

    return dp[L][R]


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, D] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    num_dic= {}
    for i in range(H):
        input_raw = read_func().strip().split()
        for j in range(W):
            num_dic[int(input_raw[j])] = (i, j)
    input_raw = read_func().strip().split()
    [Q] = [int(input_raw[0])]
    test_list = []
    for i in range(Q):
        input_raw = read_func().strip().split()
        test_list.append((int(input_raw[0]), int(input_raw[1])))

    dp = [[0 for i in range(H)] for j in range(W)]
    for test in test_list:
        L = test[0]
        R = test[1]
        print dp_search(L,R,D,num_dic)




if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np

H, W, D = [int(a) for a in input().split()]

a = np.zeros([H*W+1, 2], dtype=int)
for i in range(H):
    a_ = [int(a) for a in input().split()]
    for j in range(W):
        a[a_[j]][0] = i
        a[a_[j]][1] = j

memo = np.zeros([H*W+1, H*W+1], dtype=int)

Q = int(input())
ans = []
for i in range(Q):
    l, r = [int(a) for a in input().split()]
    if memo[l][r] != 0:
        p = memo[l][r]
    else:
        c = l
        p = 0
        while c < r:
            c_ = c + D
            p += abs(a[c][0] - a[c_][0]) + abs(a[c][1] - a[c_][1])
            c = c_
        memo[l][r] = p
    ans.append(p)
for ans_ in ans:
    print(ans_)

Submission status: Runtime Error

Solution code:
H,W,D = map(int,input().split(" "))
field = [] 
power = 0
for i in range(W):
    field.append(list(map(int,input().split(" "))))
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split(" "))
    point = field.index(L)

    while L =/ R:
        point = field.index(L)
        x1 = int(point/W)+1
        y1 = point%W + 1
        L = L + D
        point2 = field.index(L)
        x2 = int(point/W)+1
        y2 = point%W + 1

        power = power + abs(x1-x2) + abs(y1-y2)

Submission status: Runtime Error

Solution code:
from math import *

inp = input().split(' ')
H = int(inp[0]); W = int(inp[1]); D = int(inp[2])
A = [list(map(lambda x: int(x), input().split(' '))) for _ in range(H)]
Q = int(input())
T = [list(map(lambda x: int(x), input().split(' '))) for _ in range(Q)]
A_ = [None for _ in range(H * W + 1)]
for y in range(H):
  for x in range(W):
    A_[A[y][x]] = (x, y)
for t in T:
  e = 0
  n = t[0]
  while n is not t[1]:
    (x, y) = A_[n]
    n += D
    (x_, y_) = A_[n]
    e += abs(x - x_) + abs(y - y_)
  print(e)

Submission status: Runtime Error

Solution code:
import numpy as np

H, W, D = [int(a) for a in input().split()]

a = np.zeros([H*W+1, 2])
for i in range(H):
    a_ = [int(a) for a in input().split()]
    for j in range(W):
        a[a_[j]][0] = i
        a[a_[j]][1] = j

memo = np.zeros([H*W+1, H*W+1])

Q = int(input())
for i in range(Q):
    l, r = [int(a) for a in input().split()]
    if memo[l][r] != 0:
        p = memo[l][r]
    else:
        c = l
        p = 0
        while c < r:
            c_ = c + D
            p += abs(a[c][0] - a[c_][0]) + abs(a[c][1] - a[c_][1])
            c = c_
        memo[l][r] = p
    print(int(p))

Submission status: Runtime Error

Solution code:
H,W,D=map(int,input().split())

locations=[(0,0)]*(H*W)
for i in xrange(H):
    row=list(map(int,input().split()))
    for j in range(W):
        locations[row[j]-1]=(i,j)

Q=int(input())

for i in xrange(Q):
    l,r=map(int,input().split())
    power=0
    x=l
    while x!=r:
        mFrom=locations[x-1]
        mTo=locations[x+D-1]
        power+=abs(mFrom[0]-mTo[0])+abs(mFrom[1]-mTo[1])
        x+=D
    print(power)

Submission status: Runtime Error

Solution code:
from math import *

inp = input().split(' ')
H = int(inp[0]); W = int(inp[1]); D = int(inp[2])
A = [list(map(lambda x: int(x), input().split(' '))) for _ in range(H)]
Q = int(input())
T = [list(map(lambda x: int(x), input().split(' '))) for _ in range(Q)]
A_ = [None for _ in range(H * W)]
for y in range(H):
  for x in range(W):
    A_[A[y][x] - 1] = (x + 1, y + 1)
for t in T:
  e = 0
  n = t[0] - 1
  (x, y) = A_[n]
  while n is not t[1] - 1:
    n += D
    (x_, y_) = A_[n]
    e += abs(x - x_) + abs(y - y_)
    x = x_; y = y_
  print(e)

Submission status: Runtime Error

Solution code:
H, W, D = map(int, input().split())
Amap = [None]*W*H
for y in range(H):
    for x, a in enumerate(map(int, input().split())):
        Amap[a-1] = (x, y)
Q = int(input())

dp = [{} for a in range(H*W)]

def calc_dist(a):
    p1, p2 = Amap[a], Amap[a+D]
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

def get_cost(a, c):
    if c == 0:
        return 0
    if c not in dp[a]:
        dp[a][c] = get_cost(a+D, c-1) + calc_dist(a)
        cc = c - 1
        while cc > 0:
            dp[a][cc] = dp[a][cc+1] - dp[a+cc*D][1]
            cc -= 1
    return dp[a][c]

for _ in range(Q):
    l, r = map(int, input().split())
    l-=1
    r-=1
    print(get_cost(l, (r-l)//D))

Submission status: Runtime Error

Solution code:
def calc(prepoint, nextpoint):
    return abs(nextpoint[0]-prepoint[0]) + abs(nextpoint[1]-prepoint[1])

def search(L,A,H):
    for h in range(H):
        if L in A[h]:
            return (h,A[h].index(L))
def main():
    H,W,D = map(int,input().split())
    A = [list(map(int, input().split())) for i in range(H)]
    Q = int(input())
    L_R_List = [list(map(int, input().split())) for i in range(Q)]

    temp = [(0,0) for i in range(H*W)]
    for L_R in L_R_List:
        L = L_R[0]
        R = L_R[1]
        ans = 0
        if temp[L] == (0,0):
            temp[L] = search(L,A,H)
            prepoint = temp[L]
        else:
            prepoint = temp[L]
        while(L != R):
            L += D
            if temp[L] == (0,0):
                temp[L] = search(L,A,H)
                nextpoint = temp[L]
            else:
                nextpoint = temp[L]
            ans += calc(prepoint, nextpoint)
            prepoint = nextpoint
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import *

inp = input().split(' ')
H = int(inp[0]); W = int(inp[1]); D = int(inp[2])
A = [list(map(lambda x: int(x), input().split(' '))) for _ in range(H)]
Q = int(input())
T = [list(map(lambda x: int(x), input().split(' '))) for _ in range(Q)]
A_ = [None for _ in range(H * W)]
for y in range(H):
  for x in range(W):
    A_[A[y][x] - 1] = (x + 1, y + 1)
for t in T:
  e = 0
  n = t[0]
  (x, y) = A_[n - 1]
  while n is not t[1]:
    n += D
    (x_, y_) = A_[n - 1]
    e += abs(x - x_) + abs(y - y_)
    x = x_; y = y_
  print(e)

Submission status: Runtime Error

Solution code:
H, W, D = map(int, input().split())

A = [list(map(int, input().split())) for i in range(H)]
rA = [[0 for j in range(2)] for i in range(H * W + 1)]
S = [0 for i in range(H * W + 1)]
for i in range(H):
	for j in range(W):
		rA[A[i][j]][0] = i
		rA[A[i][j]][1] = j

Q = int(input())
for i in range(Q):
	L, R = map(int, input().split())
	ans = 0
	for j in range(H * W) [L::D]:
		if j == R:
			break
		if S[j]:
			ans += S[j]
			break
		S[j] -= ans
		ans += abs(rA[j + D][1] - rA[j][1]) + abs(rA[j + D][0] - rA[j][0])
	for j in range(H * W)[L::D]:
		if S[j] > 0:
			break
		if j == R
			break
		S[j] += ans
	print (ans)

Submission status: Runtime Error

Solution code:
def calc(prepoint, nextpoint):
    return abs(nextpoint[0]-prepoint[0]) + abs(nextpoint[1]-prepoint[1])

def search(i,A):
    for h in range(H):
        if L in A[h]:
            return (h,A[h].index(L))
def main():
    H,W,D = map(int,input().split())
    A = [list(map(int, input().split())) for i in range(H)]
    Q = int(input())
    L_R_List = [list(map(int, input().split())) for i in range(Q)]

    temp = [(0,0) for i in range(H*W)]
    for L_R in L_R_List:
        L = L_R[0]
        R = L_R[1]
        ans = 0
        if temp[L] == (0,0):
            temp[L] = search(L,A)
            prepoint = temp[L]
        else:
            prepoint = temp[L]
        while(L != R):
            L += D
            if temp[L] == (0,0):
                temp[L] = search(L,A)
                nextpoint = temp[L]
            else:
                nextpoint = temp[L]
            ans += calc(prepoint, nextpoint)
            prepoint = nextpoint
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import *

inp = input().split(' ')
H = int(inp[0]); W = int(inp[1]); D = int(inp[2])
A = [list(map(lambda x: int(x), input().split(' '))) for _ in range(H)]
Q = int(input())
T = [list(map(lambda x: int(x), input().split(' '))) for _ in range(Q)]
A_ = [None for _ in range(H * W)]
for y in range(H):
  for x in range(W):
    A_[A[y][x] - 1] = (x + 1, y + 1)
for t in T:
  e = 0
  n = t[0]
  (x, y) = A_[n - 1]
  while n is not t[1]:
    n += D
    (x_, y_) = A_[n - 1]
    e += abs(x - x_) + abs(y - y_)
    (x, y) = (x_, y_)
  print(e)

Submission status: Runtime Error

Solution code:
def calc(prepoint, nextpoint):
    return abs(nextpoint[0]-prepoint[0]) + abs(nextpoint[1]-prepoint[1])

def search(i,A):
    for h in range(H):
        if L in A[h]:
            return (h,A[h].index(L))

H,W,D = map(int,input().split())
A = [list(map(int, input().split())) for i in range(H)]
Q = int(input())
L_R_List = [list(map(int, input().split())) for i in range(Q)]

temp = [(0,0) for i in range(H*W)]
for L_R in L_R_List:
    L = L_R[0]
    R = L_R[1]
    ans = 0
    if temp[L] == (0,0):
        temp[L] = search(L,A)
        prepoint = temp[L]
    else:
        prepoint = temp[L]
    while(L != R):
        L += D
        if temp[L] == (0,0):
            temp[L] = search(L,A)
            nextpoint = temp[L]
        else:
            nextpoint = temp[L]
        ans += calc(prepoint, nextpoint)
        prepoint = nextpoint
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np


def move_and_compute_cost(field, d, l, r, cost):
    if l == r:
        return cost

    curr_y, curr_x = np.where(field == l)
    curr_y, curr_x = curr_y[0], curr_x[0]

    next_y, next_x = np.where(field == l + d)
    next_y, next_x = next_y[0], next_x[0]

    cost += abs(next_y - curr_y) + abs(next_x - curr_x)
    return move_and_compute_cost(field, d, l + d, r, cost)


if __name__ == '__main__':
    h, w, d = [int(v) for v in input().split()]

    # read field
    field = np.empty((h, w), dtype=int)
    for i in range(h):
        line = [int(v) for v in input().split()]
        field[i, :] = line

    ls, rs = [], []
    q = int(input())
    for i in range(q):
        line = [int(v) for v in input().split()]
        ls.append(line[0])
        rs.append(line[1])

    costs = [move_and_compute_cost(field, d, l, r, 0) for l, r in zip(ls, rs)]
    for c in costs:
        print(c)

Submission status: Runtime Error

Solution code:
from math import *

inp = input().split(' ')
H = int(inp[0]); W = int(inp[1]); D = int(inp[2])
A = [list(map(lambda x: int(x), input().split(' '))) for _ in range(H)]
Q = int(input())
T = [list(map(lambda x: int(x), input().split(' '))) for _ in range(Q)]
A_ = {}
for y in range(H):
  for x in range(W):
    A_[A[y][x]] = (x + 1, y + 1)
for t in T:
  e = 0
  n = t[0]
  (x, y) = A_[n]
  while n is not t[1]:
    n += D
    (x_, y_) = A_[n]
    e += abs(x - x_) + abs(y - y_)
    (x, y) = (x_, y_)
  print(e)

Submission status: Runtime Error

Solution code:
H, W, D = map(int, input().split())
Amap = [None]*W*H
for y in range(H):
    al = list(map(int, input().split()))
    for x in range(W):
        Amap[al[x]-1] = (x, y)
Q = int(input())

dp = [{} for a in range(H*W)]

def calc_dist(a):
    p1, p2 = Amap[a], Amap[a+D]
    return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])

def get_cost(a, c):
    if c == 0:
        return 0
    if c not in dp[a]:
        dp[a][c] = get_cost(a+D, c-1) + calc_dist(a)
    return dp[a][c]

for _ in range(Q):
    l, r = map(int, input().split())
    l-=1
    r-=1
    print(get_cost(l, (r-l)//D))

Submission status: Runtime Error

Solution code:
H, W, D = map(int, input().split())
A = [[] * W for i in range(H)]
dic = {}
for i in range(H):
    a = list(map(int, input().split()))
    A[i] = a
    for j in range(W):
        dic[a[j]] = (i + 1, j + 1)

rec = {}


def cal(L, R):
    global rec
    if L == R:
        return 0
    if (L, R) in rec:
        return rec[(L, R)]
    else:
        p = abs(dic[L + D][0] - dic[L][0]) + abs(dic[L + D][1] - dic[L][1])
        rec[(L, R)] = cal(L + D, R) + p
        return rec[(L, R)]


Q = int(input())
for i in range(Q):
    L, R = map(int, input().split())
    print(cal(L, R))

Submission status: Runtime Error

Solution code:
from math import *

inp = input().split(' ')
H = int(inp[0]); W = int(inp[1]); D = int(inp[2])
A = [list(map(lambda x: int(x), input().split(' '))) for _ in range(H)]
Q = int(input())
T = [list(map(lambda x: int(x), input().split(' '))) for _ in range(Q)]
A_ = {}
for y in range(H):
  for x in range(W):
    A_[A[y][x]] = (x, y)
for t in T:
  e = 0
  n = t[0]
  (x, y) = A_[n]
  while n is not t[1]:
    n += D
    (x_, y_) = A_[n]
    e += abs(x - x_) + abs(y - y_)
    (x, y) = (x_, y_)
  print(e)

Submission status: Runtime Error

Solution code:
line = input().split(" ")
a = list(map(int, line))
data = [0]*90000
ans=0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i,j]
times=int(input())
for i in range(0,times):
    line = input().split(" ")
    temp = list(map(int, line))
    nowloc=temp[0]
    ans=0
    while nowloc!=temp[1]:
        ans+=abs(data[nowloc][0]-data[nowloc+a[2]][0])+abs(data[nowloc][1]-data[nowloc+a[2]][1])
        nowloc+=a[2]
    print(ans)