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: Wrong Answer

Solution code:
def solve(string):
    h, w, d, *a = map(int, string.split())
    a, q, lr = a[:h * w], a[h * w], a[h * w + 1:]
    n = h * w
    index = [a.index(i + 1) for i in range(h * w)]
    # costs = [
    # [0 if j <= i or (j - i) % d != 0 else n * (j - i) // d for j in range(n)] for i in range(n)
    # ]
    diff = [abs(i0 // w - i1 // w) + abs(i0 % w - i1 % w) for i0, i1 in zip(index, index[d:])]
    """
    for s in range(n):
        if sum(costs[s]) == 0:
            continue
        for g in range(n):
            if costs[s][g] == 0:
                continue
            if s - d >= 0:
                costs[s][g] = costs[s - d][g] - costs[s - d][s]
                continue
            before = 0 if g - d < 0 else costs[s][g - d]
            costs[s][g] = +before
    return "\n".join([str(costs[l - 1][r - 1]) for l, r in zip(lr[::2], lr[1::2])])
    """
    print(diff)
    return "\n".join([str(sum(diff[l - 1:r - 1:d])) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Wrong Answer

Solution code:
from itertools import product


def solve(string):
    h, w, d, *a = map(int, string.split())
    a, q, lr = a[:h * w], a[h * w], a[h * w + 1:]
    n = h * w
    index = [a.index(i + 1) for i in range(h * w)]
    costs = [
        [0 if j <= i or (j - i) % d != 0 else n * (j - i) // d for j in range(n)] for i in range(n)
    ]
    for s, g in product(range(n), repeat=2):
        if costs[s][g] == 0:
            continue
        if s - d >= 0:
            costs[s][g] = costs[s - d][g] - costs[s - d][s]
            continue
        before = 0 if g - d < 0 else costs[s][g - d]
        costs[s][g] = abs(index[g - d] // w - index[g] // w) + abs(index[g - d] % w -
                                                                   index[g] % w) + before
    print(costs)
    return "\n".join([str(costs[l - 1][r - 1]) for l, r in zip(lr[::2], lr[1::2])])


if __name__ == '__main__':
    n, m, d = map(int, input().split())
    ins = '{} {} {}\n'.format(n, m, d) + '\n'.join([input() for _ in range(n)])
    n = int(input())
    print(solve(ins + '\n{}\n'.format(n) + '\n'.join([input() for _ in range(n)])))

Submission status: Wrong Answer

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

# 各数字の位置を覚える
d = dict()
for i in range(H):
    for j in range(W):
        d[Aij[i][j]] = [i, j]

mp = 0
for lr in LRi:
    mp = 0
    start = d[lr[0]]
    end = d[lr[1]]
    curr = lr[0]
    while curr < lr[1]:
        old = curr
        curr += D
        p1 = d[lr[0]]
        p2 = d[curr]
        d[lr[0]] = p2
        d[curr] = p1

        mp += abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
    print(mp)

Submission status: Wrong Answer

Solution code:
import heapq
import sys
input=sys.stdin.readline
from collections import defaultdict
h, w, d = map(int, input().split())
p = dict()
D = defaultdict(list)
for i in range(h):
    for j, x in enumerate(map(int, input().split())):
        p[x] = (x, i, j)
        heapq.heappush(D[x%d], (x, i, j))

q = int(input())
for i in range(q):
    a, b = map(int, input().split())
    v = D[a%d]
    ans = 0
    while v:
        x, i, j = heapq.heappop(v)
        if x == a:
            s, t = i, j
        elif a < x <= b:
            ans += abs(s-i)+abs(t-j)
            s, t = i, j
            if x == b:
                break
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def main():
    input = sys.stdin.readline
    H, W, D = map(int, input().split())
    d = {}

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

    A = [[0 for _ in range(H*W)] for _ in range(H*W)]
    for r in range(H * W - 1, 0, -1):
        for l in range(r - D, 0, -D):
            ans = 0
            L, R = l + 1, r + 1
            a = d[L]
            b = d[L+D]
            ans += abs(a[0] - b[0]) + abs(a[1] - b[1])
            A[l][r] = ans + A[l+D][r]

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# D
h, w, d = map(int, input().split())
points = [[0]*2 for i in range(h*w)]
cost = [0]* (h*w)
for h_i in range(h):
    a_row = [int(i) for i in input().split()]
    for r_i, a in enumerate(a_row):
        points[a-1][0] = h_i
        points[a-1][1] = r_i
for i in range(d+1, (h*w)):
    cost[i] = cost[i-d] + abs(points[i][0]-points[i-d][0]) + abs(points[i][1]-points[i-d][1])
q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(cost[r-1] - cost[l-1])

Submission status: Wrong Answer

Solution code:
N, W ,D = map(int, input().split())
inf = float("inf")
dp = [0]*(N*W)
s = [inf]*N*W

d = [list(map(int, input().split())) for i in range(N)]
T = int(input())
m = [list(map(int, input().split())) for i in range(T)]
ans = 0
 
for i in range(N):
    for j in range(W):
        s[d[i][j]-1] = [i,j]
k=0
#print(s)

for n in range(D,N*W):
    print(n)
    dp[n] = dp[n-D]+abs(s[n][0]-s[n-D][0])+abs(s[n][1]-s[n-D][1])
    k+=1
for x,y in m:
    if x == y:print(0)
    else:print(dp[y-1]-dp[x-1])

Submission status: Wrong Answer

Solution code:
N, W ,D = map(int, input().split())
inf = float("inf")
dp = [0]*(N*W)
s = [inf]*N*W

d = [list(map(int, input().split())) for i in range(N)]
T = int(input())
m = [list(map(int, input().split())) for i in range(T)]
ans = 0
 
for i in range(N):
    for j in range(W):
        s[d[i][j]-1] = [i,j]
k=0
#print(s)

for n in range(D+1,N*W):
    #print(n)
    dp[n] = dp[n-D]+abs(s[n][0]-s[n-D][0])+abs(s[n][1]-s[n-D][1])
    k+=1
for x,y in m:
    if x == y:print(0)
    else:print(dp[y-1]-dp[x-1])

Submission status: Wrong Answer

Solution code:
h,w,d = map(int,input().split())
hw = [[] for _ in range(h*w+1)]
hw[0] = [0,0]
for i in range(h):
    row = list(map(int,input().split()))
    for j in range(w):
        hw[row[j]] = [i,j]
print(hw)

a = [0 for _ in range(h*w+1)]
for i in range(d+1,h*w+1):
    a[i] = a[i-d] + abs(hw[i][0] - hw[i-d][0]) + abs(hw[i][1] - hw[i-d][1])

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

Submission status: Wrong Answer

Solution code:
ANS = dict()


def f(l, r):
    if (l, r) in ANS:
        return ANS[l, r]
    n = r
    ans = 0
    while (n != l):
        ans += (abs(P[n][0] - P[n - D][0]) + abs(P[n][1] - P[n - D][1]))
        ANS[(l, n)] = ans
        n -= D
    return ans


H, W, D = [int(x) for x in input().split()]
P = [0] * (H * W + 1)
for h in range(H):
    A = [int(x) for x in input().split()]
    for w, a in enumerate(A):
        P[a] = (h, w)

Q = int(input())

for q in range(Q):
    l, r = [int(x) for x in input().split()]
    print(f(l, r))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import math
from pprint import pprint

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

xy = {}
for h in range(H):
    for w in range(W):
        xy[A[h][w]] = (h,w)

xy[0] = xy[D]

width = math.ceil(H*W/D)
rui_xy = [[0 for _ in range(width+1)] for _ in range(D)]
for d in range(D):
    rui_cost = 0
    x,y = xy[d]
    for w in range(width):
        if w*D+d > H*W:
            break
        i,j = xy[w*D+d]
        rui_cost += abs(x-i) + abs(y-j)
        rui_xy[d][w] = rui_cost
        x,y = i,j

for l,r in LR:
    if l == r:
        print(0)
        continue

    print(rui_xy[r % D][r//D] - rui_xy[l % D][l//D])

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import math
from pprint import pprint

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

xy = {0:(0,0)}
for h in range(H):
    for w in range(W):
        xy[A[h][w]] = (h,w)

width = math.ceil(H*W/D)
rui_xy = [[0 for _ in range(width+1)] for _ in range(D)]
for d in range(D):
    rui_cost = 0
    x,y = xy[d]
    for w in range(width):
        if w*D+d > H*W:
            break
        i,j = xy[w*D+d]
        rui_cost += abs(x-i) + abs(y-j)
        rui_xy[d][w] = rui_cost
        x,y = i,j

for l,r in LR:
    if l == r:
        print(0)
        continue

    print(rui_xy[r % D][r//D] - rui_xy[l % D][l//D])

Submission status: Wrong Answer

Solution code:
H,W,D=map(int,input().split())
A=[[0,0]]*(H*W)
j=0
for i in range(H):
  for a in input().split():
    A[int(a)-1]=[i,j]
    j+=1
  j=0
Q=int(input())
ans=0
for q in range(Q):
  l,r=map(int,input().split())
  for k in range((r-l)//D):
    x1=A[l+D*k-1][0]
    x2=A[l+D*(k+1)-1][0]
    y1=A[l+D*k-1][1]
    y2=A[l+D*(k+1)-1][1]
    ans+=abs(x1-x2)
    ans+=abs(y1-y2)
  print(ans-1)
  ans=0

Submission status: Wrong Answer

Solution code:
h,w,d=map(int, input().split())
m=[list(map(int, input().split())) for i in range(h)]
b=[0]*(h*w)
for i in range(h):
    for j in range(w):
        b[m[i][j]-1]=[i,j]
dp=[0]*(h*w)
for i in range(d,h*w):
    dp[i]=dp[i-d]+abs(b[i][0]-b[i-d][0])+abs(b[i][1]-b[i-d][1])
n=int(input())
count=0
for i in range(n):
    x,y=map(int, input().split())
    count+=dp[y-1]-dp[x-1]
print(count)

Submission status: Wrong Answer

Solution code:
h, w, d = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
lr = [list(map(int, input().split())) for _ in range(q)]

a_and_pos = {}
for i in range(h):
    for j in range(w):
        a_and_pos[a[i][j]] = (i, j)

paths = {}
for rem in range(1, d+1):
    path = [0]*(h*w+1)
    i, j = a_and_pos[rem]
    for x in range(rem+d, h*w+1, d):
        i_next, j_next = a_and_pos[x]
        path[x] = path[x-d] + abs(i_next-i) + abs(j_next-j)
        i, j = i_next, j_next
    paths[rem] = path

# for k, v in paths.items(): print(f'{k} : {v}')
for l, r in lr:
    rem = l%d if l%d != 0 else l%d+1
    path = paths[rem]
    print(path[r] - path[l])

Submission status: Wrong Answer

Solution code:
H,W,D=list(map(int,input().split()))
arr=[0 for i in range(H*W+1)]
for y in range(H):
    for x,n in enumerate(map(int,input().split())):
        arr[n]=[x,y]

dic={}

Q=int(input())
for i in range(Q):
    ans=0
    now,goal= list(map(int,input().split()))
    nx=arr[now][0]
    ny=arr[now][1]
    tmp=now
    for j in range((goal-now)//D):
        if dic.get(tmp*H*W+goal,0)!=0:
            dic[now*H*W+goal]=ans+dic[tmp*H*W+goal]
            print(dic[now*H*W+goal])
            break
        tmp+=D
        x=arr[tmp][0]
        y=arr[tmp][1]
        ans+=abs(x-nx)+abs(y-ny)
        nx=x
        ny=y
        dic[now*H*W+tmp]=ans
    if dic.get(now*H*W+goal,0)==0:
        dic[now*H*W+goal]=ans
        print(ans)

Submission status: Wrong Answer

Solution code:
H,W,D=list(map(int,input().split()))
arr=[0 for i in range(H*W+1)]
for y in range(H):
    for x,n in enumerate(map(int,input().split())):
        arr[n]=[x,y]

dic={}

Q=int(input())
for i in range(Q):
    ans=0
    now,goal= list(map(int,input().split()))
    nx=arr[now][0]
    ny=arr[now][1]
    tmp=now
    for j in range((goal-now)//D):
        if dic.get(tmp*H*W+goal,0)!=0:
            dic[now*H*W+goal]=ans+dic[tmp*H*W+goal]
            print(dic[now*H*W+goal])
            break
        tmp+=D
        x=arr[tmp][0]
        y=arr[tmp][1]
        ans+=abs(x-nx)+abs(y-ny)
        nx=x
        ny=y
    dic[now*H*W+goal]=ans
    print(ans)

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

h,w,d = ai()
ph = [0 for _ in range(h*w + 1)]
pw = [0 for _ in range(h*w + 1)]

for i in range(h):
    a = ai()
    for j in range(w):
        ph[a[j]] = i
        pw[a[j]] = j


score = [0 for _ in range(h*w + 1)]
for i in range(d+1, h*w+1):
    score[i] = score[i-d] + abs(ph[i]-ph[i-d]) + abs(pw[i]-pw[i-d])

print(score)

q = int(input())
for _ in range(q):
    l,r = ai()
    print(score[r]-score[l])

Submission status: Wrong Answer

Solution code:
ai = lambda: list(map(int, input().split()))

h,w,d = ai()
ph = [0 for _ in range(h*w + 1)]
pw = [0 for _ in range(h*w + 1)]

for i in range(h):
    a = ai()
    for j in range(w):
        ph[a[j]] = i
        pw[a[j]] = j

score = [0 for _ in range(h*w + 1)]
for i in range(d+1, h*w):
    score[i] = score[i-d] + abs(ph[i]-ph[i-d]) + abs(pw[i]-pw[i-d])

q = int(input())
for _ in range(q):
    l,r = ai()
    print(score[r]-score[l])

Submission status: Wrong Answer

Solution code:
H, W, D=map(int, input().split())
pos={}
for i in range(H):
    A=list(map(int, input().split()))
    for j in range(W):
        pos[A[j]]=(i, j)
p=[0]*(H*W+1)
for i in range(D+1,H*W+1):
    p[i]=p[i-D]+abs(pos[i][0]-pos[i-D][0])+abs(pos[i][1]-pos[i-D][1])
print(p)
Q=int(input())
for _ in range(Q):
    L, R=map(int, input().split())
    print(p[R]-p[L])

Submission status: Wrong Answer

Solution code:
H, W, D=map(int, input().split())
pos={}
for i in range(H):
    A=list(map(int, input().split()))
    for j in range(W):
        pos[A[j]]=(i, j)
Q=int(input())
p=0
for i in range(Q):
    L, R=list(map(int, input().split()))
    for j in range((R-L)//D):
        p+=abs(pos[L+D*j][0]-pos[L+D*(j+1)][0])+abs(pos[L+D*j][1]-pos[L+D*(j+1)][1])
    print(p)

Submission status: Wrong Answer

Solution code:
H, W, D=map(int, input().split())
A=[list(map(int,input().split())) for _ in range(H)]
Q=int(input())
LR=[list(map(int, input().split())) for _ in range(Q)]
# 二重配列のindex
# pos_L = [[x, y] for y, row in enumerate(A) for x, elem in enumerate(row) if A[x][y] == LR[0][0]][0]

for j in range(Q):
    try:
        pos = [[[x+1, y+1] for y, row in enumerate(A) for x, elem in enumerate(row) if A[x][y]==(LR[j][0]+i*D)][0] for i in range((LR[j][1]-LR[j][0])//D+1)]
        pow=0
        for i in range(len(pos)-1):
            pow+=abs(pos[i][0]-pos[i+1][0])
            pow+=abs(pos[i][1]-pos[i+1][1])
        print(pow)
    except IndexError:
        print(0)

Submission status: Wrong Answer

Solution code:
def m():
    h, w, d = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]
    pre = [0] * ((h+1)*(w+1))
    for i in range(h):
        for j in range(w):
            pre[a[i][j]] = (i+1, j+1)
    q = int(input())
    power = 0
    for _ in range(q):
        l, r = map(int, input().split())
        for p in range(l+d, r+1, d):
            power += abs(pre[p][0]-pre[p-d][0])
            power += abs(pre[p][1]-pre[p-d][1])
    return power


print(m())

Submission status: Wrong Answer

Solution code:
H, W, D=[int(x) for x in str(input()).split()]
A=[[0 for x in range(W+1)]]
for i in range(1,H+1):
  b=[0]
  b+=[int(x) for x in str(input()).split()]
  A.append(b)
Q=int(input())
LR=[[0 for x in range(3)]]
for i in range(1,Q+1):
  b=[0]
  b+=[int(x) for x in str(input()).split()]
  LR.append(b)












B=[0 for x in range(H*W+1)]
for i in range(1,W+1):
  for j in range(1,H+1):
    B[A[j][i]]=[j,i]

print(B)

XY=[0]
for i in range(1,D+1):

  C=[]
  x=i
  s=0
  while x<(H*W-D+1):

    s+=abs(B[x][0]-B[x+D][0])+abs(B[x][1]-B[x+D][1])
    C.append(s)
    x+=D

  C.append(s+abs(B[i][0]-B[x][0])+abs(B[i][1]-B[x][1]))
  XY.append(C)
print(XY)


def mo(x,y):
  if x%y==0:
    return y
  else:
    return x%y

def br(x):
  if x<=0:
    return 0
  else:
    return int(x)

ans=[]
for i in range (1,Q+1):
  if LR[i][1]<LR[i][2] and LR[i][1]==mo(LR[i][1],D):
    g=XY[mo(LR[i][1],D)][br((LR[i][1]-0.1)//D-1)]
    h=XY[mo(LR[i][1],D)][br((LR[i][2]-0.1)//D-1)]

    ans.append(h)
  elif LR[i][1]<LR[i][2]:
    g=XY[mo(LR[i][1],D)][br((LR[i][1]-0.1)//D-1)]
    h=XY[mo(LR[i][1],D)][br((LR[i][2]-0.1)//D-1)]

    ans.append(h-g)
  elif LR[i][1]>LR[i][2]:
    g=XY[mo(LR[i][2],D)][br((LR[i][2]+0.1)//D)-2]
    h=XY[mo(LR[i][2],D)][-1]-XY[mo(LR[i][1],D)][br((LR[i][2]+0.1)//D-2)]
    ans.append(h+g)
  else:
    ans.append(0)

for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
H, W, DA = map(int, input().split())
InvA = [[0, 0] for i in range(H * W + 1)]
if H==1 and W==1: exit()

for i in range(H):
    for j, a in enumerate(map(int, input().split())):
        InvA[a] = [i, j]

C = [False]*(H*W+1)
i = 0
InvA2 = []
Con = [0]*(H*W+1)
for j in range(H*W+1):
    while C[i] == True:
        i += 1
        if i == H*W:
            i=0
    InvA2.append(InvA[i])
    C[i] = True
    Con[i] = j
    i += DA
    i %= H*W+1

D = []
tmp = [0, 0]
for i in range(1, H*W+1):
    ia = InvA2[i]
    D.append(abs(tmp[0]-ia[0])+abs(tmp[1]-ia[1]))
    tmp = ia


treeSize = 1
while treeSize < H*W+1:
    treeSize *= 2
treeSize *= 2
Rmq = [0] * (treeSize - 1)
Rmq[treeSize // 2 - 1 : treeSize // 2 - 1 + H*W] = D
for i in range(treeSize//2-2, -1, -1):
    Rmq[i] = Rmq[2*i+1] + Rmq[2*i+2]

# a, bは求めたい範囲 l, rはだんだん狭くなる 半開区間
def query(a, b, k, l, r):
    if r <= a or b <= l: return 0
    if a <= l and r <= b: return Rmq[k]
    vl = query(a, b, k*2+1, l, (l+r)//2)
    vr = query(a, b, k*2+2, (l+r)//2, r)
    return vl + vr

for i in range(int(input())):
    a, b = map(int, input().split())
    print(query(Con[a], Con[b], 0, 0, treeSize//2))

Submission status: Wrong Answer

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 = [0]
    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)
        #print("{}->{}".format(A[i - 1], A[i - 1 + (j + 1) * D]))
    X.append(x)
# print(X)
for i in range(Q):
    k = L[i] % D
    if k == 0:
        l = int((L[i] - D) / D)
        r = int((R[i] - D) / D)
    else:
        l = int((L[i] - k) / D)
        r = int((L[i] - k) / D)
#    print(X[k], l, r)
    print(X[k][r] - X[k][l])

Submission status: Wrong Answer

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])


print(A)
for i in range(Q):
    power = 0
    for j in range(int((R[i] - L[i]) / D)):
        power += consumption(A[L[i] + j * D - 1], A[L[i] + (j + 1) * D - 1])
        #print("{}->{}".format(A[L[i] + j * D - 1], A[L[i] + (j + 1) * D - 1]))
    print(power)

Submission status: Wrong Answer

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])


print(A)
assert len(A) == H * W
for i in range(Q):
    power = 0
    for j in range(int((R[i] - L[i]) / D)):
        power += consumption(A[L[i] + j * D - 1], A[L[i] + (j + 1) * D - 1])
        #print("{}->{}".format(A[L[i] + j * D - 1], A[L[i] + (j + 1) * D - 1]))
    print(power)

Submission status: Wrong Answer

Solution code:
h, w, d = map(int, input().split())
a = [0] * h * w
for i in range(h):
    a[i * w:(i + 1) * w] = list(map(int, input().split()))
q = int(input())
for _ in range(q):
    ans = 0
    l, r = map(int, input().split())

    xy = []
    for i in range(l, r + 1, d):
        i = a.index(i)
        xy.append((i // h + 1, i % h + 1))

    for i in range(len(xy) - 1):
        x1, y1 = xy[i]
        x2, y2 = xy[i + 1]
        d = abs(x1 - x2) + abs(y1 - y2)
        ans += d
    print(ans)

Submission status: Wrong Answer

Solution code:
H, W, D = [int(x) for x in input().split()]

def calc_costs(points, d):
    costs = [0] * len(points)
    for i in range(d, len(points)):
        curr = points[i]
        prev = points[i - d]
        costs[i] = abs(curr[0] - prev[0]) + abs(curr[1] - prev[1])
    return costs

def main():
    size = H * W
    points = [None] * size
    for j in range(H):
        for i, x in enumerate(input().split()):
            points[int(x) - 1] = (i, j)

    costs = calc_costs(points, D)
    print(costs)

    q = int(input())
    for _ in range(q):
        l, r = map(lambda x: int(x) - 1, input().split())
        ans = 0
        while l < r:
            l += D
            if l > size:
                break
            ans += costs[l]
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
h, w, d = map(int, input().split())
l = [[0]]*(h*w+1)

for i in range(h):
  temp = list(map(int, input().split()))
  for j in range(len(temp)):
    l[temp[j]] = [i+1, j+1]

q = int(input())

for i in range(q):
  a, b = map(int, input().split())
  ans = 0

  while True:
    nowX, nowY = l[a]
    if a == b:
      print(ans)
      break
    a += d
    nextX, nextY = l[a]
    ans += abs(nextY-nowX) + abs(nextX-nowY)

Submission status: Wrong Answer

Solution code:
H, W, D = map(int, input().split())
A = []
for i in range(H):
    A.extend(list(map(int, input().split())))
size = H * W
a_map = [0]*(size+1)
for i in range(1, size+1):
    a_map[A[i-1]] = i
cost = []
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    c = 0
    for i in range(l, r, D):
        dis = abs(a_map[i+D] - a_map[i])
        c += dis//3 + dis%3
    cost.append(c)
print('\n'.join(map(str, cost)))

Submission status: Wrong Answer

Solution code:
H, W, D = map(int, input().split())
A = []
for i in range(H):
    A.extend(list(map(int, input().split())))
size = H * W
a_map = [0]*(size+1)
for i in range(1, size+1):
    a_map[A[i-1]] = i
cost = []
Q = int(input())
for i in range(Q):
    l, r = map(int, input().split())
    c = 0
    for i in range(l, r, D):
        dis = abs(a_map[i+D] - a_map[i])
        c += dis//3 + dis%3
    cost.append(c)
print(cost)
print('\n'.join(map(str, cost)))

Submission status: Wrong Answer

Solution code:
h,w,d=map(int,input().split())
lst=[0 for i in range(h*w+1)]
for i in range(h):
    x=list(map(int,input().split()))
    for j in range(w):
        lst[x[j]]=(i,j)

dif=[0 for i in range(h*w+1)]
for j in range(1,h+1):
    for i in range(1,d+1):
        if j*d+i>h*w:
            break
        dif[j*d+i]=dif[(j-1)*d+i]+abs(lst[j*d+i][0]-lst[(j-1)*d+i][0])+abs(lst[j*d+i][1]-lst[(j-1)*d+i][1])
q=int(input())
ans=[]
for i in range(q):
    l,r=map(int,input().split())
    ans.append(dif[r]-dif[l])
for num in ans:
    print(num)

Submission status: Wrong Answer

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

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

d = np.zeros(H*W+1)
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 = input().split()
    L = int(L)
    R = int(R)
    print(d[R]-d[L])

Submission status: Wrong Answer

Solution code:
h, w, d = map(int,input().split())
measure = []
for i in range(h):
    temp = list(map(int,input().split()))
    measure.extend(temp)
del temp

query = int(input())


graph_a, graph_b = [0] * (h * w + 1), [0] * (h * w + 1)

for i in range(h*w):
    graph_a[measure[i]] = (i + w) // w
    graph_b[measure[i]] = (i + 1) % w

for i in range(1, h*w):
    if graph_b[i] == 0:
        graph_b[i] = w

distance = []
for i in range(d):
    temp = [0]
    for j in range(i+d, h*w, d):
        temp.append(temp[-1] + abs(graph_a[j]-graph_b[j-d]) + abs(graph_b[j]-graph_b[j-d]))
    distance.append(temp)
for i in range(query):
    l, r = map(int,input().split())
    l -= 1
    r -= 1
    print(distance[l%d][r//d] - distance[l%d][l//d])

Submission status: Wrong Answer

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)
for i in range(q):
    cost = 0
    for j in range(int((r[i]-l[i])/d)):
        #print("{}->{}:{}+{}".format(l[i]+j*d,l[i]+(j+1)*d,
            #abs(loc[l[i]+(j+1)*d][0]-loc[l[i]+j*d][0]),
            #abs(loc[l[i]+(j+1)*d][1]-loc[l[i]+j*d][1])))
        cost += abs(loc[l[i]+(j+1)*d][0]-loc[l[i]+j*d][0])
        cost += abs(loc[l[i]+(j+1)*d][1]-loc[l[i]+j*d][1])
    print(cost)

Submission status: Wrong Answer

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

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 = [None for _ in range(h*w) ]
for x, y in itertools.product(range(h), range(w)):
    #print(x,y,board[x][y])
    pos_number[board[x][y]-1] = [x,y]
print(pos_number)

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-1]
        next_pos = pos_number[next_n-1]
        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: Wrong Answer

Solution code:
h,w,d = map(int,input().split())
a = [[0 for i in range(0,w)] for j in range(0,h)]
x = [0 for i in range(0,h*w)]
y = [0 for i in range(0,h*w)]
for i in range(0,h):
    a[i] = list(map(int,input().split()))
for j in range(0,h):
    for i in range(0,w):
        x[a[j][i]-1] = i
        y[a[j][i]-1] = j
l = []
r = []
q = int(input())
for i in range(0,q):
    L,R = map(int,input().split())
    l.append(L)
    r.append(R)

way = [0 for i in range(0,h*w)]
for i in range(d+1,h*w):
    way[i] = way[i-d] + abs(x[i] - x[i-d]) + abs(y[i] - y[i-d])
for i in range(0,q):
    print(way[r[i]-1] - way[l[i]-1])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 23 11:18:48 2018

@author: natsukiiwano
"""

_in_ = list(map(int,input().split(" ")))
H,W,D = _in_[0],_in_[1],_in_[2]
dic = {}
for h in range(H):
    _in_ = list(map(int,input().split(" ")))
    for w in range(W):
        dic[_in_[w]]=h+w*1j

print(dic)

for n in range(H*W-D):
    dic[n+1] = int(abs(dic[n+1].real-dic[n+1+D].real)+abs(dic[n+1].imag-dic[n+1+D].imag))
    
print(dic)
    
for q in range(int(input())):
    _in_ = list(map(int,input().split(" ")))
    _from_,_to_ = _in_[0],_in_[1]
    _sum_=0
    while _to_ != _from_:
        _sum_ = _sum_ + dic[_from_]
        _from_ = _from_ + D
    print(_sum_)

Submission status: Wrong Answer

Solution code:
from math import fabs
def calc(A,B):
    x=B[0]
    diff=0
    x_posi=[]
    for i in range(H):
        if x in A[i]:
            x_posi.append(i)
            x_posi.append(A[i].index(x))
    x_plus_posi=[]
    while x!=B[1]:
        x_plus=x+D
        for i in range(H):
            if x_plus in A[i]:
                x_plus_posi.append(i)
                x_plus_posi.append(A[i].index(x_plus))
        diff+=fabs(x_posi[0]-x_plus_posi[0])+fabs(x_posi[1]-x_plus_posi[1])
        x=x_plus
        x_posi=x_plus_posi
    print(int(diff))
        


H,W,D=list(map(int,input().split()))
A=[]
for i in range(H):
    x=(list(map(int,input().split())))
    A.append(x)
    
Q=int(input())
for i in range(Q):
    B=list(map(int,input().split()))
    calc(A,B)

Submission status: Wrong Answer

Solution code:
H,W,D = map(int, input().split())
arr = [0]*(H*W)
for i in range(H):
    for j , v in enumerate(map(int, input().split())):
        arr[v-1] = (i,j)
print(arr)        
X = [[] for _ in range(D)]
Y = [[] for _ in range(D)]
for i , (x,y) in enumerate(arr):
    if i // D == 0:
        X[i%D].append(0)
        Y[i%D].append(0)
    else:
        px, py = arr[i - D]
        X[i%D].append(X[i%D][-1] + abs(x - px))
        Y[i%D].append(Y[i%D][-1] + abs(y - py))
Q = int(input())
for _ in range(Q):
    L, R = map(lambda x : int(x) - 1 , input().split())
    
    assert L % D  == R % D
    print(X[R%D][R//D] - X[L%D][L//D] + Y[R%D][R//D] - Y[L%D][L//D])

Submission status: Wrong Answer

Solution code:
str1 = input().split(" ")
h = int(str1[0])
w = int(str1[1])
d = int(str1[2])
res = [0 for i in range(90001)]
px = [0 for i in range(90001)]
py = [0 for j in range(90001)]
for i in range(h):
    str2 = input().split(" ")
    for j in range(w):
        px[int(str2[j])] = i
        py[int(str2[j])] = j

for i in range(d+1, h*w):
    res[i] = res[i - d] + abs(px[i] - px[i - d]) + abs(py[i] - py[i - d])
q = int(input())
for i in range(q):
    str3 = input().split(" ")
    print(res[int(str3[1])] - res[int(str3[0])])