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 = map(int, input().split())
A = [0] * H * W
for i in range(H):
    temp = list(map(int, input().split()))
    for j in range(len(temp)):
        A[temp[j] - 1] = (i + 1, j + 1)

Q = int(input())
L = []
R = []
for _ in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)


def consumption(point_A, point_B):
    return abs(point_A[0] - point_B[0]) + abs(point_A[1] - point_B[1])


X = []
for i in [D] + list(range(1, D)):
    power = 0
    x = []
    for j in range(int((H * W - i) / D)):
        power += consumption(A[i - 1 + j * D], A[i - 1 + (j + 1) * D])
        x.append(power)
    X.append(x)
for i in range(Q):
    l = int(L[i] / D) - 2
    r = int(R[i] / D) - 2
    print(X[L[i] % D][r] - X[L[i] % D][l])

Submission status: Runtime Error

Solution code:
import numpy as np

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

A = []

for _ in range(H):
    A.append(list(map(int, input().split())))

A = np.array(A)

Q = int(input())

LR = []
for _ in range(Q):
  LR.append(list(map(int, input().split())))

B = np.zeros((H*W,H*W))
for lr in LR:
    l = lr[0]
    r = lr[1]
    if l == r:
        print(0)
    else:
        magic = 0
        while l != r:
            if B[l-1][l+D-1] == 0:
                loc = np.where(A == l)
                i, j = map(int, loc)
                nloc = np.where(A == l+D)
                x, y = map(int, nloc)
                magic_plus = abs(x-i) + abs(y-j)
                magic += magic_plus
                B[l-1][l+D-1] = magic_plus
                l += D
            else:
                magic += B[l-1][l+D-1]
                l += D
        print(magic)

Submission status: Runtime Error

Solution code:
import numpy as np

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

A = []

for _ in range(H):
    A.append(list(map(int, input().split())))

A = np.array(A)

Q = int(input())

LR = []
for _ in range(Q):
  LR.append(list(map(int, input().split())))

B = np.zero((H*W,H*W))
for lr in LR:
    l = lr[0]
    r = lr[1]
    if l == r:
        print(0)
    else:
        magic = 0
        while l != r:
            if B[l-1][l+D-1] == 0:
                loc = np.where(A == l)
                i, j = map(int, loc)
                nloc = np.where(A == l+D)
                x, y = map(int, nloc)
                magic_plus = abs(x-i) + abs(y-j)
                magic += magic_plus
                B[l-1][l+D-1] = magic_plus
                l += D
            else:
                magic += B[l-1][l+D-1]
                l += D
        print(magic)

Submission status: Runtime Error

Solution code:
h, w, d = map(int, input().split())
a, a_map, dis, cost = [], [0]*(h*w+1), [0]*h*w, []
for i in range(h):
    a.extend(list(map(int, input().split())))
for i in range(1, h*w+1):
    a_map[a[i-1]] = i
for i in range(1, d+1):
    for j in range(i+d, h*w, d):
        k = abs(a_map[j] - a_map[j-d])
        dis[j] = dis[j-d] + k//3 + k%3
q = int(input())
while(q):
    l, r = map(int, input().split())
    cost.append(dis[r] - dis[l])
    q -= 1
print('\n'.join(map(str, cost)))

Submission status: Runtime Error

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

Q=int(input().strip())
L=[]
R=[]
dist={}
def search(l,r):
    if l==r:
        return 0
    if (l,r) in dist:
        return dist[l,r]
    else:
        if l+D==r:
            posl=mapper[l]
            posr=mapper[r]
            val= abs(posl[0]-posr[0])+abs(posl[1]-posr[1])
            dist[(l,l+D)]=val
            return val
        else:
            val=search(l,l+D)+search(l+D,r)
            dist[l,r]=val
            return val
for i in range(Q):
    cst=0
    l,r=map(int,input().split())
    print(search(l,r))

Submission status: Runtime Error

Solution code:
import numpy as np
H, W, D = map(int, input().split())

px, py = np.zeros(H*W+1, dtype=int), np.zeros(H*W+1, dtype=int)
for i in range(H):
    A = map(int, input().split())
    for j in range(W):
        px[A[j]] = i
        py[A[j]] = j

d = np.zeros(H*W+1, dtype=int)
for i in range(D+1, H*W+1):
    d[i]= d[i-D]+abs(px[i]-px[i-D])+abs(py[i]-py[i-D])

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    print(d[R]-d[L])

Submission status: Runtime Error

Solution code:
import numpy as np
sitei = input().split()
H, W, D = int(sitei[0]), int(sitei[1]), int(sitei[2])
_masume = np.zeros([H, W])
for i in range(H):
    _masume[i] = np.array(input().split())
masume = _masume.astype(int)

Q = int(input())

_settei = np.zeros([Q, 2])
#print(settei.dtype)
for i in range(Q):
    _settei[i] = np.array(input().split())

settei = _settei.astype(int)
maryoku = 0

zahyou = [np.where(masume==l) for l in range(1, H*W+1)]
#print(zahyou)

for l in range(Q):
    atai = settei[l][0]
    while (atai != settei[l][1]):
        maryoku += abs((zahyou[atai+D-1])[0]-(zahyou[atai-1])[0]) + abs((zahyou[atai+D-1])[1]-(zahyou[atai-1])[1])
        atai += D

maryoku, = maryoku
print(maryoku)

Submission status: Runtime Error

Solution code:
import numpy as np


def get_next_int():
    return int(float(input()))


def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])


def get_next_str():
    return input()


def get_next_strs(delim=" "):
    return tuple(input().split(delim))


def get_next_by_types(*value_types, delim=" "):
    return tuple([t(x) for t, x in zip(value_types, input().split(delim))])

class PracticalSkillTest():

    def __init__(self):
        self.H, self.W, self.D = get_next_ints()
        self.field = []
        for _ in range(self.H):
            self.field.append(get_next_ints())
        self.Q = get_next_int()
        self.places = []
        for _ in range(self.Q):
            self.places.append(get_next_ints())
        self.mapping()
        self.dp = np.zeros((self.H * self.W, self.H*self.W), dtype=np.int)

    def mapping(self):
        self.mapping_dic = {}
        for y in range(self.H):
            for x in range(self.W):
                self.mapping_dic[self.field[y][x]] = (x, y)


    def get_consumption(self, num):
        start = self.places[num][0]
        end = self.places[num][1]
        if self.dp[start][end] != 0:
            return self.dp[start][end]
        pos = (self.mapping_dic[start])
        cost = 0
        for i in range(start+self.D, end+1, self.D):
            next_pos = self.mapping_dic[i]
            cost += abs(pos[0] - next_pos[0]) + abs(pos[1] - next_pos[1])
            self.dp[start][i] = cost
            pos = next_pos
        self.dp[start][end] = cost
        return cost


    def practice_solve(self):
        for i in range(self.Q):
            cost = self.get_consumption(i)
            print(cost)
    
def solve():
    p = PracticalSkillTest()
    p.practice_solve()


solve()

Submission status: Runtime Error

Solution code:
#■標準入力ショートカット


def get_next_int():
    return int(float(input()))


def get_next_ints(delim=" "):
    return tuple([int(float(x)) for x in input().split(delim)])


def get_next_str():
    return input()


def get_next_strs(delim=" "):
    return tuple(input().split(delim))


def get_next_by_types(*value_types, delim=" "):
    return tuple([t(x) for t, x in zip(value_types, input().split(delim))])

class PracticalSkillTest():

    def __init__(self):
        self.H, self.W, self.D = get_next_ints()
        self.field = []
        for _ in range(self.H):
            self.field.append(get_next_ints())
        self.Q = get_next_int()
        self.places = []
        for _ in range(self.Q):
            self.places.append(get_next_ints())
        self.mapping()
        self.dp = [[-1]*(self.H*self.W) for i in range(self.H*self.W)]

    def mapping(self):
        self.mapping_dic = {}
        for y in range(self.H):
            for x in range(self.W):
                self.mapping_dic[self.field[y][x]] = (x, y)


    def get_consumption(self, num):
        start = self.places[num][0]
        end = self.places[num][1]
        if self.dp[start][end] != -1:
            return self.dp[start][end]
        pos = (self.mapping_dic[start])
        cost = 0
        for i in range(start+self.D, end+1, self.D):
            next_pos = self.mapping_dic[i]
            cost += abs(pos[0] - next_pos[0]) + abs(pos[1] - next_pos[1])
            pos = next_pos
        self.dp[start][end] = cost
        return cost


    def practice_solve(self):
        for i in range(self.Q):
            cost = self.get_consumption(i)
            print(cost)
    
def solve():
    p = PracticalSkillTest()
    p.practice_solve()


solve()

Submission status: Runtime Error

Solution code:
import numpy as np

#### 入力フェーズ開始 ####
HWD = input().split()
H = int(HWD[0])
W = int(HWD[1])
D = int(HWD[2])

A = []
for i in range(H):
    Ai = []
    Ai_raw = input().split()
    for j in range(W):
        Ai.append(int(Ai_raw[j]))
    A.extend(Ai)

# 各移動で踏むA_ijとそのx,yの値にindexベースで参照できるように
# A_ijの値でindexをソートしておく
x_ = np.arange(W)
x = np.tile(x_, H)
y_ = np.arange(H)
y = np.repeat(y_, W)
# A_ijの値でsortした時のindexの順番を取得
B = np.argsort(A)

Q = int(input())

for q in range(Q):
    # 各実技試験につき
    score = 0
    LR_raw = input().split()
    Li = LR_raw[0]
    Ri = LR_raw[1]
    M = int((Ri - Li) / D) # 何回移動が必要か
    m_vec = [Li + D * m for m in range(M+1)] # 通るA_ijの値

    for m in range(M):
        # 各移動につき
        id_from = B[m_vec[m] - 1]
        id_to = B[m_vec[m+1] - 1]
        score += np.abs(x[id_from] - x[id_to]) 
            + np.abs(y[id_from] - y[id_to])

    print(score)

Submission status: Runtime Error

Solution code:
h,w,d=(int(i) for i in input().split())
num=[None for i in range(h*w)]
for i in range(h):
    a=list(map(int,input().split()))
    for j in range(w):
        num[a[j]-1]=(i,j)
numm=[None for i in range(h*w)]
for i in range(d):
    numm[i]=0
for i in range(d,h*w):
    numm[i]=numm[i-d]+abs(num[i-1][0]-num[i-d-1][0])+abs(num[i-1][1]-num[i-d-1][1])

q=int(input())
for i in range(q):
    l,r=list(map(int,input().split()))
    print(numm[r]-numm[l])

Submission status: Runtime Error

Solution code:
h,w,d=(int(i) for i in input().split())
num=[None for i in range(h*w)]
for i in range(h):
    a=list(map(int,input().split()))
    for j in range(w):
        num[a[j]-1]=(i,j)
numm=[None for i in range(h*w)]
for i in range(h*w-d):
    numm[i]=abs(num[i+d-1][0]-num[i-1][0])+abs(num[i+d-1][1]-num[i-1][1])
q=int(input())
for i in range(q):
    l,r=list(map(int,input().split()))
    result=0
    while l!=r:
        result+=numm[l]
        l+=d
    print(result)

Submission status: Runtime Error

Solution code:
tmp = list(map(int,input().split()))
H,W,D = tmp[0],tmp[1],tmp[2]
kiro = [None] * (H*W)
As = []
for i in range(H):
  As.append(list(map(int,input().split())))
for i in range(H):
  for j in range(W):
    kiro[As[i][j]-1] = [i,j]
Q = int(input())
Ls = []
Rs = []
def mkmk(L,R):
    ans = 0
    for j in range(L,R,D):
    ans += abs(kiro[j+D-1][0] - kiro[j-1][0]) + abs(kiro[j+D-1][1] - kiro[j-1][1])
    return(ans)
for i in range(Q):
  t = list(map(int,input().split()))
  L = t[0]
  R = t[1]
  print(mkmk(L,R))

Submission status: Runtime Error

Solution code:
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(W)]
Q = int(input())

def find_A(num):
    i_,j_ = 0, 0
    for i in range(W):
        for j in range(H):
            if A[i][j] == num:
                i_,j_ = i,j
    return i_,j_
#print(find_A(8))
counter = 0

for k in range(Q):
    L, R = map(int,input().split())
    (X,Y) = find_A(L)
    for s in range(int((R-L)/D)):
        (x,y) = (X,Y)
        (X,Y) = find_A(L+s*D+D)
        counter += abs(X-x)+abs(Y-y)
print(counter)

Submission status: Runtime Error

Solution code:
H,W,D = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(W)]
Q = int(input())

def find_A(num):
    i_,j_ = 0, 0
    for i in range(H):
        for j in range(W):
            if A[i][j] == num:
                i_,j_ = i,j
    return i_,j_
#print(find_A(8))
counter = 0

for k in range(Q):
    L, R = map(int,input().split())
    (X,Y) = find_A(L)
    for s in range(int((R-L)/D)):
        (x,y) = (X,Y)
        (X,Y) = find_A(L+s*D+D)
        counter += abs(X-x)+abs(Y-y)
print(counter)

Submission status: Runtime Error

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

q = int(input())#moving num
l = [0 for i in range(q)]#start number
r = [0 for i in range(q)]#finish number

for i in range(q):
    tmp = input().split()
    l[i]=int(tmp[0])-1
    r[i]=int(tmp[1])-1
loc = [[0, 0] for i in range(h*w)]
for i in range(h):
    for j in range(w):
        loc[a[i][j]][0] = i
        loc[a[i][j]][1] = j
#print(loc)
cost = [0 for i in range(int((h*w)/d))]
#print(cost)
for i in range(1, len(cost)):
    cost[i] += abs(loc[(i+1)*d-1][0]-loc[i*d-1][0])
    cost[i] += abs(loc[(i+1)*d-1][1]-loc[i*d-1][1])
#print(cost)
for i in range(1, len(cost)):
    cost[i] += cost[i-1]
#print(cost)

for i in range(q):
    print(cost[int(r[i]/d)]-cost[int(l[i]/d)])

Submission status: Runtime Error

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

q = int(input())#moving num
l = [0 for i in range(q)]#start number
r = [0 for i in range(q)]#finish number

for i in range(q):
    tmp = input().split()
    l[i]=int(tmp[0])-1
    r[i]=int(tmp[1])-1
loc = [[0, 0] for i in range(h*w)]
for i in range(h):
    for j in range(w):
        loc[a[i][j]][0] = i
        loc[a[i][j]][1] = j
#print(loc)
cost = [0 for i in range(int((h*w)/d))]
#print(cost)
for i in range(1, len(cost)):
    cost[i] += abs(loc[(i+1)*d-1][0]-loc[i*d-1][0])
    cost[i] += abs(loc[(i+1)*d-1][1]-loc[i*d-1][1])
#print(cost)
for i in range(1, len(cost)):
    cost[i] += cost[i-1]
print(cost)

for i in range(q):
    print(cost[int(r[i]/d)]-cost[int(l[i]/d)])

Submission status: Runtime Error

Solution code:
import itertools
h, w, d = list(map(int, input().split()))
#print(h, w, d)

#line1 = input().split()
#h = int(line1[0])
#w = int(line1[1])
#d = int(line1[2])
#print(h,w,d)
board = []
for i in range(h):
    board.append(list(map(int, input().split())))


def find_pos(cur):
    for x, y in itertools.product(range(h), range(w)):
        if board[x,y] == cur:
            return [x, y]

pos_number = [find_pos(i) for i in range(h*w) ]
#print(board)

q = int(input())


for i in range(q):
    l, r = list(map(int, input().split()))
    cur = l
    energy = 0
    if r == l:
        print(0)
        continue
    while(True):
        next_n = cur + d
        pos = pos_number[cur]
        next_pos = pos_number[next_n]
        energy += abs(pos[0]-next_pos[0]) + abs(pos[1] - next_pos[1])
        cur = next_n
        if next_n == r:
            break
    print(energy)

Submission status: Runtime Error

Solution code:
import itertools
h, w, d = list(map(int, input().split()))
#print(h, w, d)

#line1 = input().split()
#h = int(line1[0])
#w = int(line1[1])
#d = int(line1[2])
#print(h,w,d)
board = []
for i in range(h):
    board.append(list(map(int, input().split())))

pos_number = [find_pos(i) for i in range(h*w) ]
#print(board)

q = int(input())

def find_pos(cur):
    for x, y in itertools.product(range(h), range(w)):
        if board[x,y] == cur:
            return [x, y]


for i in range(q):
    l, r = list(map(int, input().split()))
    cur = l
    energy = 0
    if r == l:
        print(0)
        continue
    while(True):
        next_n = cur + d
        pos = pos_number[cur]
        next_pos = pos_number[next_n]
        energy += abs(pos[0]-next_pos[0]) + abs(pos[1] - next_pos[1])
        cur = next_n
        if next_n == r:
            break
    print(energy)

Submission status: Runtime Error

Solution code:
# 要は、Li + m の座標を求め、座標の位置の距離のpathを計算すればよいだけ
import time
H, W, D = map(int, input().split())

mp_dict = {}
for i in range(H):
    a = map(int, input().split())

    for j in range(W):
        mp_dict[int(a[j])] = (i, j)

Q = int(input())
start_end_list = []
for i in range(Q):
    start_end_list.append(list(map(int, input().split())))

for x in start_end_list:
    abs_sum = 0
    for k in range(((x[1] - x[0])/D)):
        abs_sum += abs(mp_dict[x[0] + (k+1)*D][0] -  mp_dict[x[0] + (k*D)][0]) + \
                   abs(mp_dict[x[0] + (k+1) * D][1] - mp_dict[x[0] + (k*D)][1])
    print(abs_sum)

Submission status: Runtime Error

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

A = []

for i in range(H):
    l = list(map(int, input().split()))
    for j in range(W):
        A[l[j]] = (i, j)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    while L != R:
        start = A[L]
        stop  = A[L+D]
        cost += abs(start[0] - stop[0]) + abs(start[1] - stop[1])
        start = stop
        L += D
    print(cost, flush=True)

Submission status: Runtime Error

Solution code:
import cython


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

A = [False] * (H * W + 1)

for i in range(H):
    l = list(map(int, input().split()))
    for j in range(W):
        A[l[j]] = (i, j)

Q = int(input())

for i in range(Q):
    L, R = map(int, input().split())
    cost = 0
    while L != R:
        start = A[L]
        stop  = A[L+D]
        cost += abs(start[0] - stop[0]) + abs(start[1] - stop[1])
        start = stop
        L += D
    print(cost, flush=True)

Submission status: Runtime Error

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

d = [0 for i in range(H*W)]
sA = [0 for i in range(H*W+1)]

for i in range(len(A)):
        for j in range(len(A[i])):
            sA[A[i][j]] = [i, j]

for i in range(D+1, H*W):
    d[i] = d[i-D] + abs(sA[i][0]-sA[i-D][0]) + abs(sA[i][1]-sA[i-D][1])

for lr in LR:
    l, r = lr[0], lr[1]
    print(d[r] - d[l])

Submission status: Runtime Error

Solution code:
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
INF = float("inf")
import sys
sys.setrecursionlimit(10000)

def manhattan(y1, x1, y2, x2): return abs(y1 - y2) + abs(x1 - x2)


def solve(H, W, D, A, query):
    num_pos = dict()
    for y in range(H):
        for x in range(W):
            num_pos[A[y][x]] = (y, x)

    dp = [None] * (H * W + 1)
    for i in range(1, D + 1):
        dp[i] = 0
        for j in range(i + D, len(dp), D):
            dp[j] = dp[j - D] + manhattan(*num_pos[j - D], *num_pos[j])

    for q in query:
        L, R = q
        print(dp[R] - dp[L])


def main():
    H, W, D = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))
    Q = int(input())
    query = []
    for _ in range(Q):
        query.append(list(map(int, input().split())))

    solve(H, W, D, A, query)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys

def uni_norm(pos_a, pos_b):
    return abs(pos_a[0] - pos_b[0]) + abs(pos_a[1] - pos_b[1])

def solve(l, r, d, posses):
    if l >= r:
        return 0
    else:
        return uni_norm(posses[l], posses[l+d]) + solve(l+d, r, d, posses)

def main ():
    with sys.stdin as f:
        s_input = f.read()

        s_args = s_input.splitlines()
        header = s_args[0].split()
        h = int(header[0])
        w = int(header[1])
        d = int(header[2])
        
        posses = {}
        
        for r in range(h):
            row = s_args[r+1].split()
            for c, s_val in enumerate(row):
                posses[int(s_val)] = (r, c)

        #print(posses)

        q = int(s_args[h+1])
        res = []
        for i in range(q):
            query = s_args[h+2+i].split()
            res.append(solve(int(query[0]), int(query[1]), d, posses))

        for ans in res:
            print(ans)

try:
    main()
except MemoryError:
    print("KABOOM")
    
sys.exit(0)

Submission status: Runtime Error

Solution code:
import sys

def uni_norm(pos_a, pos_b):
    return abs(pos_a[0] - pos_b[0]) + abs(pos_a[1] - pos_b[1])

def solve(l, r, d, posses):
    if l >= r:
        return 0
    else:
        return uni_norm(posses[l], posses[l+d]) + solve(l+d, r, d, posses)

def main ():
    with sys.stdin as f:
        s_input = f.read()

        s_args = s_input.splitlines()
        header = s_args[0].split()
        h = int(header[0])
        w = int(header[1])
        d = int(header[2])
        
        posses = {}
        
        for r in range(h):
            row = s_args[r+1].split()
            for c, s_val in enumerate(row):
                posses[int(s_val)] = (r, c)

        #print(posses)

        q = int(s_args[h+1])
        res = []
        for i in range(q):
            query = s_args[h+2+i].split()
            res.append(solve(int(query[0]), int(query[1]), d, posses))

        for ans in res:
            print(ans)

try:
    main()
except KeyError:
    print("KABOOM")
    
sys.exit(0)

Submission status: Runtime Error

Solution code:
import sys

def uni_norm(pos_a, pos_b):
    return abs(pos_a[0] - pos_b[0]) + abs(pos_a[1] - pos_b[1])

def solve(l, r, d, posses):
    if l >= r:
        return 0
    else:
        return uni_norm(posses[l], posses[l+d]) + solve(l+d, r, d, posses)

def main ():
    with sys.stdin as f:
        s_input = f.read()

        s_args = s_input.splitlines()
        header = s_args[0].split()
        h = int(header[0])
        w = int(header[1])
        d = int(header[2])
        
        posses = {}
        
        for r in range(h):
            row = s_args[r+1].split()
            for c, s_val in enumerate(row):
                posses[int(s_val)] = (r, c)

        #print(posses)

        q = int(s_args[h+1])
        res = []
        for i in range(q):
            query = s_args[h+2+i].split()
            res.append(solve(int(query[0]), int(query[1]), d, posses))

        for ans in res:
            print(ans)

try:
    main()
except AttributeError:
    print("KABOOM")
    
sys.exit(0)

Submission status: Runtime Error

Solution code:
import sys

def uni_norm(pos_a, pos_b):
    return abs(pos_a[0] - pos_b[0]) + abs(pos_a[1] - pos_b[1])

def solve(l, r, d, posses):
    if l >= r:
        return 0
    else:
        return uni_norm(posses[l], posses[l+d]) + solve(l+d, r, d, posses)

def main ():
    with sys.stdin as f:
        s_input = f.read()

        s_args = s_input.splitlines()
        header = s_args[0].split()
        h = int(header[0])
        w = int(header[1])
        d = int(header[2])
        
        posses = {}
        
        for r in range(h):
            row = s_args[r+1].split()
            for c, s_val in enumerate(row):
                posses[int(s_val)] = (r, c)

        print(posses)

        q = int(s_args[h+1])
        res = []
        for i in range(q):
            query = s_args[h+2+i].split()
            res.append(solve(int(query[0]), int(query[1]), d, posses))

        for ans in res:
            print(ans)

try:
    main()
except TypeError:
    print("KABOOM")
    
sys.exit(0)

Submission status: Runtime Error

Solution code:
import sys

def uni_norm(pos_a, pos_b):
    return abs(pos_a[1] - pos_b[1]) + abs(pos_a[2] - pos_b[2])

def solve(l, r, d, posses):
    if l >= r:
        return 0
    else:
        return uni_norm(posses[l-1], posses[l+d-1]) + solve(l+d, r, d, posses)

def cmp_pos(pos):
    return pos[0]

with sys.stdin as f:
    s_input = f.read()

    s_args = s_input.splitlines()
    header = s_args[0].split()
    h = int(header[0])
    w = int(header[1])
    d = int(header[2])

    posses = []
    
    for r in range(h):
        row = s_args[r+1].split()
        for c, s_val in enumerate(row):
            posses.append((int(s_val), r, c))

    posses = sorted(posses, key=cmp_pos)
    #print(posses)

    q = int(s_args[h+1])
    res = []
    for i in range(q):
        query = s_args[h+2+i].split()
        res.append(solve(int(query[0]), int(query[1]), d, posses))

    for ans in res:
        print(ans)
            
sys.exit(0)

Submission status: Runtime Error

Solution code:
import sys

def uni_norm(pos_a, pos_b):
    return abs(pos_a[1] - pos_b[1]) + abs(pos_a[2] - pos_b[2])

def solve(l, r, d, posses):
    if l >= r:
        return 0
    else:
        return uni_norm(posses[l-1], posses[l+d-1]) + solve(l+d, r, d, posses)

def cmp_pos(pos):
    return pos[0]

with sys.stdin as f:
    s_input = f.read()

    s_args = s_input.splitlines()
    header = s_args[0].split()
    h = int(header[0])
    w = int(header[1])
    d = int(header[2])

    posses = []
    
    for r in range(h):
        row = s_args[r+1].split()
        for c, s_val in enumerate(row):
            posses.append((int(s_val), r, c))

    posses = sorted(posses, key=cmp_pos)
    print(posses)

    q = int(s_args[h+1])
    res = []
    for i in range(q):
        query = s_args[h+2+i].split()
        res.append(solve(int(query[0]), int(query[1]), d, posses))

    for ans in res:
        print(ans)
            
sys.exit(0)

Submission status: Runtime Error

Solution code:
import sys

def uni_norm(pos_a, pos_b):
    return abs(pos_a[0] - pos_b[0]) + abs(pos_a[1] - pos_b[1])

def solve(l, r, d, posses):
    if l >= r:
        return 0
    else:
        return uni_norm(posses[l], posses[l+d]) + solve(l+d, r, d, posses)


with sys.stdin as f:
    s_input = f.read()

    s_args = s_input.splitlines()
    header = s_args[0].split()
    h = int(header[0])
    w = int(header[1])
    d = int(header[2])

    posses = {}
    
    for r in range(h):
        row = s_args[r+1].split()
        for c, s_val in enumerate(row):
            posses[int(s_val)] = (r, c)

    #print(posses)

    q = int(s_args[h+1])
    res = []
    for i in range(q):
        query = s_args[h+2+i].split()
        res.append(solve(int(query[0]), int(query[1]), d, posses))

    for ans in res:
        print(ans)
            
sys.exit(0)

Submission status: Runtime Error

Solution code:
# スペース区切りのH,W,Dの入力
H, W, D = [int(i) for i in input().split()]
# Aの入力
A = []
for i in range(H):
    A.append([int(i) for i in input().split()])
# Qの入力
Q = int(input())
# L,Rの入力
LR = []
for i in range(Q):
    LR.append([int(i) for i in input().split()])

con = 0
serch = 0

for i in range(Q):
	serch = LR[i][0]
	if serch == LR[i][1]:
		con = con + 0
	else:
		while serch < LR[i][1]:
			serch_next = serch + D
			for j in range(W):
				if serch in A[j]:
					x_0, y_0 = j, A[j].index(serch)
				if serch_next in A[j]:
					x_1, y_1 = j, A[j].index(serch_next)
			con = con + abs(x_1 - x_0)+abs(y_1 - y_0)
			serch = serch_next
	print(con)
	con = 0

Submission status: Runtime Error

Solution code:
# スペース区切りのH,W,Dの入力
H, W, D = [int(i) for i in input().split()]
# Aの入力
A = []
for i in range(H):
    A.append([int(i) for i in input().split()])
# Qの入力
Q = int(input())
# L,Rの入力
LR = []
for i in range(Q):
    LR.append([int(i) for i in input().split()])

con = 0
serch = 0

for i in range(Q):
	serch = LR[i][0]
	if serch == LR[i][1]:
		con = con + 0
	else:
		while serch < LR[i][1]:
			serch_next = serch + D
			for j in range(W):
				if serch in A[j]:
					x_0, y_0 = j, A[j].index(serch)
				if serch_next in A[j]:
					x_1, y_1 = j, A[j].index(serch_next)
			con = con + abs(x_1 - x_0)+abs(y_1 - y_0)
			serch = serch_next

print(con)

Submission status: Runtime Error

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dictx ={}
dicty ={}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dictx[tmp[d]] = i
        dicty[tmp[d]] = d
cost ={}
def calcost(R):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        costs = abs(dictx[R]-dictx[str(int(R)-D)]) + abs(dicty[R]-dicty[str(int(R)-D)])
        if str(int(R)-D) in cost:
            cost[R] = costs + cost[str(int(R)-D)]
            return cost[R]
        else:
            cost[R] = costs + calcost(str(int(R)-D))
            return cost[R]

for n in range(D+1,H*W+1):
    calcost(str(n))

Q = int(input())
for j in range(Q):
    tmp = input().split()
    print(str(cost[tmp[1]]-cost[tmp[0]]))

Submission status: Runtime Error

Solution code:
tmp =input().split()
H,W,D=int(tmp[0]),int(tmp[1]),int(tmp[2])

list = [[0 for x in range(W)] for y in range(H)]
dictx ={}
dicty ={}
for i in range(H):
    tmp = input().split()
    for d in range(W):
        dictx[tmp[d]] = i
        dicty[tmp[d]] = d
result ={}
cost ={}
def calcost(R):
    if int(R)<=D:
        cost[R] = 0
        return 0
    else:
        costs = abs(dictx[R]-dictx[str(int(R)-D)]) + abs(dicty[R]-dicty[str(int(R)-D)])
        if str(int(R)-D) in cost:
            cost[R] = costs + cost[str(int(R)-D)]
            return cost[R]
        else:
            cost[R] = costs + calcost(str(int(R)-D))
            return cost[R]

for n in range(D+1,H*W+1):
    calcost(str(n))

Q = int(input())
for j in range(Q):
    tmpx = input()
    if tmpx in result:
        print(result[tmpx])
    else:
        tmp = tmpx.split()
        result[tmpx] = cost[tmp[1]]-cost[tmp[0]]
        print(result[tmpx])