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: Time Limit Exceeded

Solution code:

H, W, D = [int(x) for x in input().strip().split(' ')]
stage = {}
for i in range(H):
    nums = [int(x) for x in input().strip().split(' ')]
    for j in range(W):
        stage[nums[j]] = [i + 1, j + 1]
Q = int(input())
tests = []
for _ in range(Q):
    tests.append([int(x) for x in input().strip().split(' ')])

scores = []
done = {}
for i in range(Q):
    L, R = tests[i]
    if (L, R) in done:
        scores.append(done[(L, R)])
    elif L == R:
        scores.append(0)
    else:
        x, y = stage[L]
        score = 0
        nowL = L
        while nowL < R:
            if (nowL, R) in done:
                score += done[(nowL, R)]
                break
            new_x, new_y = stage[nowL + D]
            score += abs(new_x - x) + abs(new_y - y)
            x = new_x
            y = new_y
            nowL += D
        scores.append(score)
        done[(L, R)] = score

for score in scores:
    print(score)

Submission status: Time Limit Exceeded

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

board=[0 for _ in range(h*w)]

for i in range(h):
    for j,a in enumerate(input().split()):
        board[i*w+j]=int(a)

q=int(input())


distances=[0 for _ in range(h*w)]

for i in range(d,h*w):
    a=h*w-i
    tmp=board.index(a)
    i=tmp//w
    j=tmp%w
    tmp=board.index(a+d)
    x=tmp//w
    y=tmp%w
    distances[a-1]=distances[a+d-1]+abs(i-x)+abs(j-y)

for _ in range(q):
    l,r=map(int,input().split())
    print(distances[l-1]-distances[r-1])

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int,input().split())
dist = [0]*(H*W+1)#dist[i]はiからi+Dまでの距離
pos = [[0,0] for i in range(H*W+1)]
for i in range(H):
  A = list(map(int,input().split()))
  for j in range(W):
    pos[A[j]] = [i+1, j+1]
    
for i in range(H*W+1-D):
  dist[i] = abs(pos[i][0]-pos[i+D][0])+abs(pos[i][1]-pos[i+D][1])

distances = [[] for i in range(D)]#あまりがiの距離
for i in range(1,H*W+1-D):
  distances[i%D]+=[dist[i]]

Q = int(input())
for i in range(Q):
  L, R = map(int, input().split())
  l, r = (L-1)//D, (R-1)//D
  print(sum(distances[L%D][l:r]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

condi = input()
H,W,D = condi.split()
H = int(H)
W = int(W)
D = int(D)
 
pref = np.zeros((H,W))
for i in range(H):
    row = input()
    row = row.split()
    for j in range(W):
            pref[i][j] = int(row[j])
mat = np.array(pref)
 
Q = input()
Q = int(Q)
for i in range(Q):
  MP = 0
  LR = input()
  L,R =LR.split()
  L = int(L)
  R = int(R)
  while R>L:
    p,q = np.where(mat == L)
    x,y = np.where(mat == (L+D))
    MP = MP + abs(x-p)+abs(y-q)
    L = L + D
  print(int(MP))

Submission status: Time Limit Exceeded

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

for i in range(q):
    mrk=0
    crh =0
    while l[i] not in a[crh]:
        crh+=1
    crw = a[crh].index(l[i])

    x=l[i]
    while x != r[i]:
        inh =0
        while x+d not in a[inh]:
            inh+=1
        inw = a[inh].index(x+d)
        mrk+=abs(crh-inh)+abs(crw-inw)
        crh=inh
        crw=inw
        x=x+d
    print(mrk)


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

Submission status: Time Limit Exceeded

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

def main():
    H,W,D = map(int,input().split())
    index  = [(0,0) for i in range(H*W+1)]
    A = []
    for i in range(H):
        temp = list(map(int, input().split()))
        for t in temp:
            index[t] = (i,temp.index(t))
        A.append(temp)
    Q = int(input())
    L_R_List = [list(map(int, input().split())) for i in range(Q)]

    for L_R in L_R_List:
        L = L_R[0]
        R = L_R[1]
        ans = 0
        prepoint = index[L]
        while(L != R):
            L += D
            nextpoint = index[L]
            ans += calc(prepoint, nextpoint)
            prepoint = nextpoint
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import chain

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

Ai = list(chain.from_iterable(A))

def search(x):
    tmp = Ai.index(x)
    return (tmp%W+1,tmp//W+1)

for L, R in exam:
    cost = 0
    nw = L
    nt = L + D
    for _ in range((R-L)//D):
        il, jl = search(nw)
        ir, jr = search(nt)
        nw = nt
        nt = nw + D
        cost += abs(il - ir) + abs(jl - jr)
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
q = int(input())
x = 0
y = 0
for i in range(q):
    l,r = map(int,input().split())
    c = 0
    for b in a:
        if(l in b):
            x = b.index(l)
            y = c
        c+=1
    p=0
    while(a[y][x]!=r):
        x2=0
        y2=0
        c=0
        for b in a:
            if(a[y][x]+d in b):
                x2 = b.index(a[y][x]+d)
                y2 = c
            c+=1
        p+=abs(x-x2)+abs(y-y2)
        x=x2
        y=y2
    print(p)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
in1=list(map(int,input().split(" ")))
#print(in1)
#arr=np.zeros((in1[0],in1[1]))
d={}
for i in range(in1[0]):
    #arr[i]=input().split(" ")
    for n,k in enumerate(input().split(" ")):
        d[int(k)]=[i,n]
#print(arr)
Q=int(input())
test=[]
out=[]
route={}
for k in range(Q):
    ans=0
    start,end=list(map(int,input().split(" ")))
    #place=np.where(arr==start)
    place=d[start]
    #print(start,end)
    while start != end:
        #print("ans",ans)
        #nextplace=np.where(arr==start+in1[2])#[1][0]
        if start in route:
            nextplace=d[start+in1[2]]
        else:
            nextplace=d[start+in1[2]]
            ans1=abs(int(nextplace[0])-int(place[0]))
            ans2=abs(int(nextplace[1])-int(place[1]))
            route[start]=ans1+ans2
        ans+=route[start]
        start+=in1[2]
        place=nextplace

    print(ans)
    #out.append(ans)
#for i in out:
    #print(i)

Submission status: Time Limit Exceeded

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(" "))
    power = 0
    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(point2/W)+1
        y2 = point2%W + 1

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

Submission status: Time Limit Exceeded

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

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

result={}
for i in range(Q):
    cost=0
    L,R = LR[i][0],LR[i][1]
    if L == R:
        print(cost)
    else:
        if "-".join(str(LR[i])) in result:
            print(result["-".join(str(LR[i]))])
        else:
            for j in range((R-L)//D):
                x1,y1 = list[L+D*j]
                x2,y2 = list[L+D*(j+1)]
                cost += abs(x1-x2) + abs(y1-y2)
            print(cost)
            result["-".join(str(LR[i]))] = cost

Submission status: Time Limit Exceeded

Solution code:

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

coord_dict = {}
for i in range(H):
    gyo = [int(i) for i in input().split()]
    coord_dict.update({gyo[j] : (i,j) for j in range(W)})

Q = int(input())
exam = [[int(i) for i in input().split()] for i in range(Q)]

for i in range(Q):
    reduce_MP = 0
    num = exam[i][0]
    coord1 = coord_dict[num]
    while num < exam[i][1]:
        num += D
        coord2 = coord_dict[num]
        reduce_MP += abs(coord1[0] - coord2[0]) + abs(coord1[1] - coord2[1])
        coord1 = coord2
    print(reduce_MP)

Submission status: Time Limit Exceeded

Solution code:
nTmp  = input().rstrip().split(' ')
nH = int(nTmp[0])
nW = int(nTmp[1])
nD = int(nTmp[2])

nS = nH * nW
Ans = 0

nDataH = [0 for i in range(nS + 1)]
nDataW = [0 for i in range(nS + 1)]

for i in range(nH):
    sTmp = input().rstrip().split(' ')
    
    for i2 in range(nW):
        nNum = int (sTmp[i2])
        nDataH[nNum] = i
        nDataW[nNum] = i2

nQ = int(input())

Data = {}

for i in range(nQ):
    nDis = 0
    sTmp = input().rstrip().split(' ')
    nL = int(sTmp[0])
    nR = int(sTmp[1])
    nCnt = (nR - nL) // nD


    if nCnt == 0:
        print('0')
    else:
        nPoi=('%d-%d' %(nL,nR))

        if Data.get(nPoi):
            print(Data[nPoi])
            continue


        for i2 in range(nCnt):
            

            nL2 = nL + nD
            nTmpDis = nDataH[nL2] - nDataH[nL] 
            if nTmpDis < 0:
                nTmpDis *= -1
            nDis += nTmpDis
            nTmpDis = nDataW[nL2] - nDataW[nL] 
            if nTmpDis < 0:
                nTmpDis *= -1
            nDis += nTmpDis
            nL = nL2
        
        Data[nPoi] = nDis
        
        print(nDis)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

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

pref = np.zeros((H,W))
for i in range(H):
    row = input()
    row = row.split()
    for j in range(W):
            pref[i][j] = int(row[j])
mat = np.array(pref)

Q = input()
Q = int(Q)
for i in range(Q):
  MP = 0
  LR = input()
  L,R =LR.split()
  L = int(L)
  R = int(R)
  while R>L:
    p,q = np.where(mat == L)
    x,y = np.where(mat == (L+D))
    MP = MP + math.fabs(x-p)+math.fabs(y-q)
    L = L + D
  print(int(MP))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def cal_ans(L,R,D,A):
    ans = 0
    temp_i = []
    temp_j = []
    if L == R:
        print(0)    
    else:
        while L < R+D:
            # print(L)
            temp = np.where(A == str(L))
            temp_i.append(int(temp[0])+1)
            temp_j.append(int(temp[1])+1)
            # print(temp_i)
            # print(temp_j)
            L += D
            # print(temp)
            # temp_i1 = int(temp[0])+1
            # temp_j1 = int(temp[1])+1
            # # print(temp_i1)
            # # print(temp_j1)
            # L += D
            # # print(L)   
            # temp = np.where(A == str(L))
            # print(temp)

            # temp_i2 = int(temp[0])+1
            # temp_j2 = int(temp[1])+1
            # # print(temp_i2)
            # # print(temp_j2)

            # ans += abs(temp_i2-temp_i1) + abs(temp_j2-temp_j1)
            # print(temp_i2)
            # print(temp_i1)
            # print(temp_j2)
            # print(temp_j1)
        for i in range(1,len(temp_i)):
            # print(abs(temp_i[i]-temp_i[i-1]) + abs(temp_j[i]-temp_j[i-1]))
            ans += abs(temp_i[i]-temp_i[i-1]) + abs(temp_j[i]-temp_j[i-1])
        print(ans)
        
    return ans
ans = 0
H,W,D = list(map(int,input().split(" ")))
A = []
for i in range(H):
    A.append(input().split(" "))
A = np.array(A)
Q = int(input())
L = []

for i in range(Q):
    L,R = map(int,input().split(" "))
    ans = cal_ans(L, R, D, A)

# for i in range(Q):
#     L.append(input().split(" "))
# print(L)

# for i in range(Q):
#     ans = cal_ans(int(L), int(R), int(D), A, ans)

# print(ans)

# temp = np.where(A == "3")
# print(int(temp[0]))
# print(temp[1])
# print(A)

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
q = int(input())
l=[0]*q
r=[0]*q
x = 0
y = 0
for i in range(q):
    l[i],r[i] = map(int,input().split())
    
for i in range(q):
    c = 0
    for b in a:
        if(l[i] in b):
            x = b.index(l[i])
            y = c
        c+=1
    p=0
    while(a[y][x]!=r[i]):
        x2=0
        y2=0
        c=0
        for b in a:
            if(a[y][x]+d in b):
                x2 = b.index(a[y][x]+d)
                y2 = c
            c+=1
        p+=abs(x-x2)+abs(y-y2)
        x=x2
        y=y2
    print(p)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
D - Practical Skill Test
https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

"""
import sys
from sys import stdin
input = stdin.readline


def sub_solve(l, r):
    sx, sy = numbers[l]
    gx, gy = numbers[r]
    return abs(sx - gx) + abs(sy - gy)


def solve(numbers, queries, H, W, D):
    dp = [[-1] * (H*W+1) for _ in range(H*W+1)]

    for l, r in queries:
        ans = 0
        while True:
            if l == r:
                break
            if dp[l][r] != -1:
                res = dp[l][r]
                ans += res
                break
            if dp[l][l+D] == -1:
                dp[l][l+D] = sub_solve(l, l+D)
            res = dp[l][l+D]
            ans += res
            l += D
        print(ans)


numbers = dict()
def main(args):
    global numbers
    H, W, D = map(int, input().split())
    board = []
    for _ in range(H):
        board.append([int(x) for x in input().split()])
    Q = int(input())
    queries = []
    for _ in range(Q):
        queries.append([int(x) for x in input().split()])

    for y, row in enumerate(board, start=1):
        for x, i in enumerate(row, start=1):
            numbers[i] = [x, y]

    solve(numbers, queries, H, W, D)


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

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
a = []
coordinate = {}
for i in range(h):
  t = list(map(int, input().split()))
  a.append(t)
  for j in range(w):
    coordinate[t[j]] = (i, j)

q = int(input())
LR = []

result = {}
for i in range(q):
  LR.append(list(map(int, input().split())))
  if str(LR[i]) in result:
    continue
  x = LR[i][0]
  point = 0
  while x < LR[i][1]:
    if str((x, LR[i][1])) in result:
      point += result[str((x, LR[i][1]))]
      break
    point += abs(coordinate[x][0]-coordinate[x+d][0]) + abs(coordinate[x][1]-coordinate[x+d][1])
    x += d
  result[str(LR[i])] = point

for i in range(q):
  print(result[str(LR[i])])

Submission status: Time Limit Exceeded

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

a = []
for i in range(h):
    b = list(map(int, input().split()))
    a.append(b)

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

magic = 0

def search(word):
    for i in range(w):
        for j in range(h):
            if a[j][i] == word:
                return j+1, i+1




for k in range(q):
    x = 0
    y = 0
    magic = 0
    while True:
        if l[k] == r[k]:
            break
        else:
            if x != 0:
                i, j = x, y
            else:
                i, j = search(l[k])
            l[k] += d
            x, y = search(l[k])

            magic += abs(x-i)+abs(y-j)
    print(magic)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = list(map(int, input().split()))
A = [list(map(int,input().split())) for i in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for i in range(Q)]
place = {}
for i in range (H):
	for j in range(W):
		place[A[i][j]] = [i, j]
MP = {}
def MP1step(s, t):
	if (s, t) not in MP:
		MP[(s, t)] = abs(place[t][0] - place[s][0]) + abs(place[t][1] - place[s][1])
	return MP[(s, t)]

def MP1test(s, t):
	k = 0
	for i in range((t - s)//D):
		k += MP1step(s + D * i, s + D * (i + 1))
	return k

for i in range(Q):
	print(MP1test(LR[i][0], LR[i][1]))

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
a=[]
for i in range(h):
    a.append(list(map(int,input().split())))
q = int(input())
l=[0]*q
r=[0]*q
x = 0
y = 0
for i in range(q):
    l[i],r[i] = map(int,input().split())
    
for i in range(q):
    c = 0
    for b in a:
        if(l[i] in b):
            x = b.index(l[i])
            y = c
        c+=1
    p=0
    while(a[y][x]!=r[i]):
       x2=0
       y2=0
       c=0
       for b in a:
           if(a[y][x]+d in b):
               x2 = b.index(a[y][x]+d)
               y2 = c
           c+=1
       p+=abs(x-x2)+abs(y-y2)
       x=x2
       y=y2
    print(p)

Submission status: Time Limit Exceeded

Solution code:

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

coord_dict = {}
for i in range(H):
    gyo = [int(i) for i in input().split()]
    for j in range(W):
        coord_dict.update({gyo[j] : (i,j)})
        
Q = int(input())

"""
exam = [[] for i in range(Q)]
for i in range(Q):
    exam[i] = [int(i) for i in input().split()]
"""
exam = [[int(i) for i in input().split()] for i in range(Q)]

for i in range(Q):
    reduce_MP = 0
    num = exam[i][0]
    coord1 = coord_dict[num]
    while num < exam[i][1]:
        num += D
        coord2 = coord_dict[num]
        reduce_MP += abs(coord1[0] - coord2[0]) + abs(coord1[1] - coord2[1])
        coord1 = coord2
    print(reduce_MP)

Submission status: Time Limit Exceeded

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

inf = 10000000
d = [list(x) for x in [[inf] * (W * H + 1)] * (W * H + 1)]
for y in range(H):
    for x in range(W):
        for dy, dx in [(0, 1), (1, 0), (-1, 0), (0, -1)]:
            y2, x2 = y + dy, x + dx
            if y2 < 0 or y2 >= H or x2 < 0 or x2 >= W:
                continue
            d[A[y][x]][A[y2][x2]] = 1
            d[A[y2][x2]][A[y][x]] = 1

changed = True
while changed:
    changed = False
    for i in range(W * H + 1):
        for j in range(W * H + 1):
            for k in range(W * H + 1):
                if d[i][j] > d[i][k] + d[j][k]:
                    d[i][j] = d[i][k] + d[j][k]
                    changed = True

for i in range(Q):
    tot = 0
    curr = L[i]
    while curr < R[i]:
        start = [(y, x) for x in range(W) for y in range(H) if A[y][x] == curr][0]
        end = [(y, x) for x in range(W) for y in range(H) if A[y][x] == curr + D][0]
        tot += d[A[start[0]][start[1]]][A[end[0]][end[1]]]
        curr += D
    print(tot)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def cal_ans(L,R,D,A):
    ans = 0
    temp_i = []
    temp_j = []
    if L == R:
        print(0)    
    else:
        while L != R+D:
            # print(L)
            temp = np.where(A == str(L))
            temp_i.append(int(temp[0])+1)
            temp_j.append(int(temp[1])+1)
            # print(temp_i)
            # print(temp_j)
            L += D
            # print(temp)
            # temp_i1 = int(temp[0])+1
            # temp_j1 = int(temp[1])+1
            # # print(temp_i1)
            # # print(temp_j1)
            # L += D
            # # print(L)   
            # temp = np.where(A == str(L))
            # print(temp)

            # temp_i2 = int(temp[0])+1
            # temp_j2 = int(temp[1])+1
            # # print(temp_i2)
            # # print(temp_j2)

            # ans += abs(temp_i2-temp_i1) + abs(temp_j2-temp_j1)
            # print(temp_i2)
            # print(temp_i1)
            # print(temp_j2)
            # print(temp_j1)
        for i in range(1,len(temp_i)):
            # print(abs(temp_i[i]-temp_i[i-1]) + abs(temp_j[i]-temp_j[i-1]))
            ans += abs(temp_i[i]-temp_i[i-1]) + abs(temp_j[i]-temp_j[i-1])
        print(ans)
        
    return ans
ans = 0
H,W,D = list(map(int,input().split(" ")))
A = []
for i in range(H):
    A.append(input().split(" "))
A = np.array(A)
Q = int(input())
L = []

for i in range(Q):
    L,R = map(int,input().split(" "))
    ans = cal_ans(L, R, D, A)

# for i in range(Q):
#     L.append(input().split(" "))
# print(L)

# for i in range(Q):
#     ans = cal_ans(int(L), int(R), int(D), A, ans)

# print(ans)

# temp = np.where(A == "3")
# print(int(temp[0]))
# print(temp[1])
# print(A)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    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(' ')))))

    def check_val(H, W, A, target):
        for i in range(H):
            for j in range(W):
                if target == A[i][j]:
                    x = i
                    y = j
                    return x, y
        return -1, -1

    check_list = []
    for i in range(Q):
        stat_LR = LR[i]
        for j in range(stat_LR[0], stat_LR[1]+D, D):
            check_list.append(j)
    check_list = list(set(check_list))

    buf = H * W
    dict_buf = {}
#    for i in range(1, buf+1):
    for i in check_list:
        x, y = check_val(H, W, A, i)
        if x != -1 and y != -1:
            dict_buf[str(i)] = [x, y]

    for i in range(Q):
        mp = 0
        stat_LR = LR[i]
        if stat_LR[0] == stat_LR[1]:
            print(mp)
            continue
#        stat_x, stat_y = check_val(H, W, A, stat_LR[0])
        stat_x, stat_y = dict_buf[str(stat_LR[0])]
        next = stat_LR[0]
        while next != stat_LR[1]:
            next += D
#            x, y = check_val(H, W, A, next)
            x, y = dict_buf[str(next)]
            mp += abs(x - stat_x) + abs(y - stat_y)
            stat_x = x
            stat_y = y
        print(mp)

Submission status: Time Limit Exceeded

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_ = np.array([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)
memo = {}

Q = int(input())
ans = []
for i in range(Q):
    l, r = [int(a) for a in input().split()]
    try:
        p = memo[l][r]
    except:
        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_
        try:
            memo[l][r] = p
        except:
            memo[l] = {}
            memo[l][r] = p
    ans.append(p)
for ans_ in ans:
    print(ans_)

Submission status: Time Limit Exceeded

Solution code:
H,W,D = map(int,input().split())
A = []
for i in range(H):
    A.append(list(map(int, input().split())))
Q = int(input())
L = []
R = []
for i in range(Q):
    l,r = map(int, input().split())
    L.append(l)
    R.append(r)
    
import numpy as np
A = np.array(A)
for i in range(Q):
    MP = 0
    point = L[i]
    aa = np.array(np.where((L[i] <= A) & (A <= R[i]) & ((A - point)%D == 0))).T
    ix = np.argsort(A[aa[:,0],aa[:,1]])
    aa = aa[ix]
    MP = sum([sum(abs(aa[p]-aa[p+1])) for p in range(len(aa)-1)])
    print(MP)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w, d = map(int, input().strip().split(" "))
a = np.array([[int(i) for i in input().strip().split(" ")] for _ in range(h)])
q = int(input().strip())
lr = [input().strip().split(" ") for _ in range(q)]
rs = [None for _ in range(h * w)]
cs = [None for _ in range(h * w)]
for _r, _a in enumerate(a):
    for _c, __a in enumerate(_a):
        rs[__a - 1] = _r
        cs[__a - 1] = _c
rs_d = [rs[i::d] for i in range(d)]
cs_d = [cs[i::d] for i in range(d)]
costs = [
    np.cumsum(
        np.abs(np.array(_rs[1:]) - np.array(_rs[:-1])) +
        np.abs(np.array(_cs[1:]) - np.array(_cs[:-1]))) for _rs, _cs in zip(rs_d, cs_d)
]
for l, r in lr:
    l = int(l) - 1
    r = int(r) - 1
    if l == r:
        print(0)
    elif l < d:
        print(costs[r % d][r // d - 1])
    else:
        print(costs[r % d][r // d - 1] - costs[l % d][l // d - 1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

H,W,D = list(map(int, input().split(" ")))
masu = []
for i in range(H):
  masu.append(list(map(int, input().split(" "))))
Q = int(input())
exams = []
for i in range(Q):
  exams.append(tuple(map(int, input().split(" "))))
masu = np.array(masu)
for exam in exams:
  sun_energy = 0
  c = np.where(masu==exam[0])
  current = (c[0][0],c[1][0])
  
  while not masu[current[0]][current[1]] == exam[1]:
    target = masu[current[0]][current[1]]+D
    c = np.where(masu==target)
    target_pos = (c[0][0],c[1][0])
    sun_energy+=abs(current[0]-target_pos[0])+abs(current[1]-target_pos[1])
    current = target_pos
  print(sun_energy)

Submission status: Time Limit Exceeded

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

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

Q=int(input())

for i in range(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: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
a = []
coordinate = {}
for i in range(h):
  t = list(map(int, input().split()))
  a.append(t)
  for j in range(w):
    coordinate[t[j]] = (i, j)

q = int(input())
LR = []

result = {}
for i in range(q):
  LR.append(list(map(int, input().split())))
  if str(LR[i]) in result:
    continue
  x = LR[i][0]
  point = 0
  while x < LR[i][1]:
    point += abs(coordinate[x][0]-coordinate[x+d][0]) + abs(coordinate[x][1]-coordinate[x+d][1])
    x += d
  result[str(LR[i])] = point

for i in range(q):
  print(result[str(LR[i])])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
in1=list(map(int,input().split(" ")))
#print(in1)
#arr=np.zeros((in1[0],in1[1]))
d={}
for i in range(in1[0]):
    #arr[i]=input().split(" ")
    for n,k in enumerate(input().split(" ")):
        d[int(k)]=[i,n]
#print(arr)
Q=int(input())
test=[]
out=[]
for k in range(Q):
    ans=0
    start,end=list(map(int,input().split(" ")))
    #place=np.where(arr==start)
    place=d[start]
    #print(start,end)
    while start != end:
        #print("ans",ans)
        #nextplace=np.where(arr==start+in1[2])#[1][0]
        nextplace=d[start+in1[2]]
        ans+=abs(int(nextplace[0])-int(place[0]))
        ans+=abs(int(nextplace[1])-int(place[1]))
        start+=in1[2]
        place=nextplace

    print(ans)
    #out.append(ans)
#for i in out:
    #print(i)

Submission status: Time Limit Exceeded

Solution code:
def searcha(A,H,W,v):
    for i in range(H):
        for j in range(W):
            if v == A[i][j]:
                return i, j

H, W, D = map(int,input().split())
A = []
for i in range(H):
    A.append(list(map(int,input().split())))
Q = int(input())
L = []
R = []
for i in range(Q):
    l, q = map(int,input().split())
    L.append(l)
    R.append(q)
for i in range(Q):
    maryoku = 0
    x, y = searcha(A,H,W,L[i])
    for j in range(L[i]+D,R[i]+1,D):
        ni, nj = searcha(A,H,W,j)
        maryoku += abs(ni-x) + abs(nj-y)
        x = ni
        y = nj
    print (maryoku)

Submission status: Time Limit Exceeded

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_ = np.array([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)
memo = {}

Q = int(input())
ans = []
for i in range(Q):
    l, r = [int(a) for a in input().split()]
    if l not in memo.keys():
        memo[l] = {}
    if r in memo[l].keys():
        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: Time Limit Exceeded

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

for _ in range(Q):
    L, R = map(int, input().split())
    
    to_be_checked = [i for i in range(L, R+1, D)]
    
    if L == R:
        print(0)
    else:
        mask = np.in1d(A, to_be_checked).reshape(A.shape[0], A.shape[1])
        idx_x, idx_y = np.where(mask == True)
        order = np.argsort(A[idx_x, idx_y])
        idx_x = idx_x[order]
        idx_y = idx_y[order]

        MP = sum([np.absolute(idx_x[i] - idx_x[i+1]) for i in range(len(idx_x)-1)]) + sum([np.absolute(idx_y[i] - idx_y[i+1]) for i in range(len(idx_y)-1)])

        print(MP)

Submission status: Time Limit Exceeded

Solution code:
def d_practical_skill_test(H, W, D, A, Q, I):
    import numpy
    a = numpy.array(A)
    tmp = []
    for i in range(D):
        i += 1 + D
        t = [0]
        while i <= H * W:
            j, k = numpy.where(a == i)
            l, m = numpy.where(a == i - D)
            j, k = j[0], k[0]
            l, m = l[0], m[0]
            t.append(t[-1] + abs(j - l) + abs(k - m))
            i += D
        tmp.append(t)
    ans=[]
    for l, r in I:
        l = l - 1
        r = r - 1
        start = l % D
        ans.append(str(tmp[start][r // D] - tmp[start][l // D]))
    return '\n'.join(ans)

H,W,D = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(H)]
Q = int(input())
I = [[int(i) for i in input().split()] for j in range(Q)]
print(d_practical_skill_test(H, W, D, A, Q, I))