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 = map(int,input().split())

M = {}

for h in range(H):
    A = list(map(int,input().split()))
    for w in range(len(A)):
        M[A[w]] = [h,w]
        
Q = int(input())

anslist = []
for q in range(Q):
    ans = 0
    L,R = map(int,input().split())
    now = M[L]
    for i in range(L+D,R+1,D):
        nex = M[i]
        ans += abs(nex[0]-now[0])+abs(nex[1]-now[1])
        now = nex
    anslist.append(str(ans))
        
print("\n".join(anslist))

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

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

B = np.zeros(H*W+1)
c = D + 1
while c <= H*W:
    loc = loc = np.where(A == c-D)
    i, j = map(int, loc)
    nloc = np.where(A == c)
    x, y = map(int, nloc)
    B[c] = B[c-D] + abs(x-i) + abs(y-j)
    c += 1

for lr in LR:
    l = lr[0]
    r = lr[1]
    if l == r:
        print(0)
    else:
        print(int(B[r]-B[l]))

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

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

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

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split())
A = []
for i in range(H):
    A.extend(list(map(int, input().split())))
Q = int(input())
while(Q):
    cost = 0
    L, R = map(int, input().split())
    while(L != R):
        dis = abs(A.index(L+D) - A.index(L))
        cost += dis//3 + dis%3
        L += D
    Q -= 1
    print(cost)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split(' '))
cells = [0 for j in range(H * W + 1)]

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


Q = int(input())
objs = [list(map(int, input().split(' '))) for i in range(Q)]

ans=""

for i in range(Q):
    power = 0
    for j in range(objs[i][0], objs[i][1] - D + 1, D):
        x, y = cells[j]
        x2, y2 = cells[j + D]
        power += abs(x2- x) + abs(y2- y)
    ans += str(power) + '\n'

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W, D = map(int, input().split(' '))
cells = [[0 for i in range(2)] for j in range(H * W + 1)]

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


Q = int(input())
objs = [list(map(int, input().split(' '))) for i in range(Q)]

for i in range(Q):
    power = 0
    while objs[i][0] < objs[i][1]:
        next = objs[i][0] + D
        power += abs(cells[objs[i][0]][0] - cells[next][0]) + abs(cells[objs[i][0]][1] - cells[next][1])
        objs[i][0] = next
    print(power)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W, D = map(int, input().split(' '))
cells = np.array([list(map(int, input().split(' '))) for i in range(H)])
Q = int(input())
objs = [list(map(int, input().split(' '))) for i in range(Q)]

for i in range(Q):
    power = 0
    currentloc = np.where(cells == objs[i][0])
    while objs[i][0] < objs[i][1]:
        objs[i][0] += D
        nextloc = np.where(cells == objs[i][0])
        power += (abs(currentloc[0] - nextloc[0]) + abs(currentloc[1] - nextloc[1]))[0]
        currentloc = nextloc
    print(power)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

H, W, D = map(int, input().split(' '))
cells = np.array([list(map(int, input().split(' '))) for i in range(H)])
Q = int(input())
objs = [list(map(int, input().split(' '))) for i in range(Q)]

for i in range(Q):
    power = 0
    while objs[i][0] < objs[i][1]:
        nextstop = objs[i][0] + D
        power += np.sum(np.abs((np.asarray(np.where(cells == nextstop)).T - np.asarray(np.where(cells == objs[i][0])).T)))
        objs[i][0] = nextstop 
    print(power)

Submission status: Time Limit Exceeded

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

dic_grid = {}
for i in range(H):
    for j in range(W):
        dic_grid[grid[i][j]] = tuple([i + 1, j + 1])

for LR in LR_list:
    sum_m = 0
    for i in range(LR[0], LR[1], D):
        sum_m += abs(dic_grid[i + D][0] - dic_grid[i][0]) + \
                 abs(dic_grid[i + D][1] - dic_grid[i][1])
    print(sum_m)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
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: Time Limit Exceeded

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=[]
for i in range(Q):
    cst=0
    l,r=map(int,input().split())
    L.append(l)
    R.append(r)
    pos=mapper[l]
    while l!=r:
        l+=D
        npos=mapper[l]
        cst+=abs(pos[0]-npos[0])+abs(pos[1]-npos[1])
        pos=npos
    print(cst)

Submission status: Time Limit Exceeded

Solution code:
# your code goes here
H,W,D = map(int,input().split())

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

place = [0]*(H*W+1)

for i in range(H):
	for j in range(W):
		place[A[i][j]] = [i,j]
Q = int(input())

for i in range(Q):
	L,R = map(int,input().split())
	now = L
	now_place = place[now]
	score = 0
	while now != R:
		now += D
		score = score + abs(now_place[0]-place[now][0]) + abs(now_place[1]-place[now][1])
		now_place = place[now]
	print(score)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H, W, D = list(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 = list(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 = list(map(int, input().split()))
    print(d[R]-d[L])

Submission status: Time Limit Exceeded

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, 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 = input().split()
    L = int(L)
    R = int(R)
    print(d[R]-d[L])

Submission status: Time Limit Exceeded

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

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

for l in range(Q):
    if settei[l][0] == settei[l][1]:
        print(maryoku)
        continue
    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)
    maryoku = 0

Submission status: Time Limit Exceeded

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

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

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
    if maryoku != 0:
        maryoku, = maryoku
    print(maryoku)
    maryoku = 0

Submission status: Time Limit Exceeded

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())
exam = [list(map(int,input().split())) for _ in range(query)]

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

for j in range(query):
    ans = 0
    a, b = exam[j][0], exam[j][1]
    x = a
    p, q = graph_a[x], graph_b[x]
    while x <= b:
        ans += abs(graph_a[x] - p) + abs(graph_b[x] - q)
        p, q = graph_a[x], graph_b[x]
        x += d
    print(ans)

Submission status: Time Limit Exceeded

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

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

    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]
        pos = (self.mapping_dic[start])
        cost = 0
        for num in range(start+self.D, end+1, self.D):
            next_pos = self.mapping_dic[num]
            cost += abs(pos[0] - next_pos[0]) + abs(pos[1] - next_pos[1])
            pos = next_pos
        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: Time Limit Exceeded

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)

Q = int(input())
L = []
R = []
for i in range(Q):
    LRi_raw = input().split()
    L.append(int(LRi_raw[0]))
    R.append(int(LRi_raw[1]))

#### 入力フェーズここまで ####
#### 計算フェーズここから ####

# 各移動で踏む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)

# 累積和を計算
d = []
for i in range(H*W):
    if i < D:
        d.append(0)
    else:
        d.append(d[i-D] + np.abs(x[B[i]] - x[B[i-D]]) + np.abs(y[B[i]] - y[B[i-D]]))

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

    for m in range(M):
        # 各移動につき
        score += d[m_vec[m+1]-1] - d[m_vec[m]-1]

    print(score)

Submission status: Time Limit Exceeded

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)

Q = int(input())
LR = []
dupTrialFlag = []
dupTrialInd = []

for i in range(Q):
    LRi_raw = input().split()
    LRi = [int(LRi_raw[0]),int(LRi_raw[1])]
    if LRi[0] != LRi[1] and LRi in LR:
        # 全く同じ試験があった場合はflagを立ててindexをとっておく
        dupTrialFlag.append(1)
        dupTrialInd.append(LR.index(LRi))
    else:
        dupTrialFlag.append(0)
        dupTrialInd.append(-1)
    LR.append(LRi)

scores = []

#### 入力フェーズここまで ####
#### 計算フェーズここから ####

# 各移動で踏む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)

# 1回の移動でかかる魔力を全て計算し配列にとっとく
C = [[np.abs(x[B[i]] - x[B[j]]) + np.abs(y[B[i]] - y[B[j]])
       for j in range(H*W)] for i in range(H*W)]
for q in range(Q):
    # 各実技試験につき
    score = 0

    if dupTrialFlag[q] == 1:
        # 全く移動がない試験
        scores.append(0)
        print(0)
        continue

    if dupTrialInd[q] != -1:
        # 全く同じ試験を以前やった場合
        # とって置いたindexを使って前回計算したscoreを参照
        print(scores[dupTrialInd[q]])
        scores.append(scores[dupTrialInd[q]])
        continue

    Li = LR[q][0]
    Ri = LR[q][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 = m_vec[m] - 1
        id_to = m_vec[m+1]- 1
        score += C[id_from][id_to]

    print(score)
    scores.append(score)

Submission status: Time Limit Exceeded

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)

Q = int(input())
LR = []
dupTrialInd = []

for i in range(Q):
    LRi_raw = input().split()
    LRi = [int(LRi_raw[0]),int(LRi_raw[1])]
    if LRi in LR:
        # 全く同じ試験があった場合はflagを立ててindexをとっておく
        dupTrialInd.append(LR.index(LRi))
    else:
        dupTrialInd.append(-1)
    LR.append(LRi)

scores = []

#### 入力フェーズここまで ####
#### 計算フェーズここから ####

# 各移動で踏む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)

for q in range(Q):
    # 各実技試験につき
    score = 0

    if LR[q] == [0,0]:
        # 全く移動がない試験
        scores.append(0)
        print(0)
        continue

    if dupTrialInd[q] != -1:
        # 全く同じ試験を以前やった場合
        # とって置いたindexを使って前回計算したscoreを参照
        print(scores[dupTrialInd[q]])
        scores.append(scores[dupTrialInd[q]])
        continue

    Li = LR[q][0]
    Ri = LR[q][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)
    scores.append(score)

Submission status: Time Limit Exceeded

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)

Q = int(input())
LR = []
dupTrialFlag = []
dupTrialInd = []

for i in range(Q):
    LRi_raw = input().split()
    LRi = [int(LRi_raw[0]),int(LRi_raw[1])]
    if LRi in LR:
        # 全く同じ試験があった場合はflagを立ててindexをとっておく
        dupTrialFlag.append(1)
        dupTrialInd.append(LR.index(LRi))
    else:
        dupTrialFlag.append(0)
        dupTrialInd.append(-1)
    LR.append(LRi)

scores = []

#### 入力フェーズここまで ####
#### 計算フェーズここから ####

# 各移動で踏む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)

for q in range(Q):
    # 各実技試験につき
    score = 0

    if LR[q] == [0,0]:
        # 全く移動がない試験
        scores.append(0)
        print(0)
        continue

    if dupTrialFlag[q] == 1:
        # 全く同じ試験を以前やった場合
        # とって置いたindexを使って前回計算したscoreを参照
        print(scores[dupTrialInd[q]])
        scores.append(scores[dupTrialInd[q]])
        continue

    Li = LR[q][0]
    Ri = LR[q][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)
    scores.append(score)

Submission status: Time Limit Exceeded

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 = int(LR_raw[0])
    Ri = int(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: Time Limit Exceeded

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)

Q = int(input())
L = []
R = []
for i in range(Q):
    LRi_raw = input().split()
    L.append(int(LRi_raw[0]))
    R.append(int(LRi_raw[1]))

#### 入力フェーズここまで ####
#### 計算フェーズここから ####

# 各移動で踏む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)

for q in range(Q):
    # 各実技試験につき
    score = 0
    Li = L[q]
    Ri = R[q]
    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: Time Limit Exceeded

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:
        if numm[l]==None:
            numm[l]=abs(num[l+d-1][0]-num[l-1][0])+abs(num[l+d-1][1]-num[l-1][1])
        result+=numm[l]
        l+=d
    print(result)

Submission status: Time Limit Exceeded

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)
q=int(input())
for i in range(q):
    l,r=list(map(int,input().split()))
    result=0
    while l!=r:
        result+=abs(num[l+d-1][0]-num[l-1][0])+abs(num[l+d-1][1]-num[l-1][1])
        l+=d
    print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None

def calc_magic(src_y, src_x, dst_y, dst_x):
    return abs(dst_x - src_x) + abs(dst_y - src_y)

def main():
    H, W, D=list(map(int, input().split()))

    A = [[]]
    for h in range(H):
        A.append([None] + list(map(int, input().split())))

    Q = int(input())

    search_dict = {}
    for y in range(1, H + 1):
        for x in range(1, W + 1):
            search_dict[A[y][x]] = str(y)+"-"+str(x)

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

        tmp = search_dict[L]
        tmp = tmp.split("-")
        loc_dict = {
            "y": int(tmp[0]),
            "x": int(tmp[1])
        }

        magic = 0

        while A[loc_dict["y"]][loc_dict["x"]] != R:
            L += D

            tmp = search_dict[L]
            tmp = tmp.split("-")
            new_loc_dict = {
                "y": int(tmp[0]),
                "x": int(tmp[1])
            }

            magic += calc_magic(loc_dict["y"], loc_dict["x"], new_loc_dict["y"], new_loc_dict["x"])
            loc_dict = new_loc_dict

        print(magic)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)

# Debug output
def chkprint(*args):
    names = {id(v):k for k,v in inspect.currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

# Binary converter
def to_bin(x):
    return bin(x)[2:]

# --------------------------------------------

dp = None

def search_index(num, H, W, A):
    for y in range(1, H + 1):
        for x in range(1, W + 1):
            if A[y][x] == num:
                return {
                    "y": y,
                    "x": x
                }

def calc_magic(src_y, src_x, dst_y, dst_x):
    return abs(dst_x - src_x) + abs(dst_y - src_y)

def main():
    H, W, D=list(map(int, input().split()))

    A = [[]]
    for h in range(H):
        A.append([None] + list(map(int, input().split())))

    Q = int(input())

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

        loc_dict = search_index(L, H, W, A)
        magic = 0

        while A[loc_dict["y"]][loc_dict["x"]] != R:
            L += D

            new_loc_dict = search_index(L, H, W, A)
            magic += calc_magic(loc_dict["y"], loc_dict["x"], new_loc_dict["y"], new_loc_dict["x"])
            loc_dict = new_loc_dict

        print(magic)


main()

Submission status: Time Limit Exceeded

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 = []
for i in range(Q):
  t = list(map(int,input().split()))
  L = t[0]
  R = t[1]
  if L == R:
    print(0)
    continue
  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])
  print(ans)

Submission status: Time Limit Exceeded

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 = []
for i in range(Q):
  t = list(map(int,input().split()))
  L = t[0]
  R = t[1]
  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])
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from time import sleep
import numpy as np

tmp = input().split()
h, w, d = int(tmp[0]), int(tmp[1]), int(tmp[2])

a = np.zeros((h,w), dtype=int)
for i in range(h):
    tmp = input().split()
    for j in range(w):
        a[i][j] = int(tmp[j])

q = int(input())
lr = np.zeros((q,2), dtype=int)
for i in range(q):
    tmp = input().split()
    for j in range(2):
        lr[i][j] = int(tmp[j])

'''
print(h, w, d)
print(a)
print(q)
print(lr)'''

#sleep(0.1*a)

def place(k):
    return np.where(a == k)[0][0], np.where(a == k)[1][0]

def place_abs(t, s):
    z1, z2 = np.where(a == t)[0][0], np.where(a == t)[1][0]
    w1, w2 = np.where(a == s)[0][0], np.where(a == s)[1][0]
    return abs(z1 - w1) + abs(z2 - w2)



ans = []
mem = []
mem_mp = []
for i in range(q):
    mp = 0
    cur = lr[i][0]
    
    if [cur, lr[i][1]] in mem:
        ind = mem.index([cur, lr[i][1]])
        mp = mem_mp[ind]
    else:
        while True:
            if cur == lr[i][1]:
                break
            mp += place_abs(cur, cur+d)
            cur += d
            #print(cur, mp)
    ans.append(mp)
    mem.append([lr[i][0], lr[i][1]])
    mem_mp.append(mp)

for i in range(len(ans)):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from time import sleep
import numpy as np

tmp = input().split()
h, w, d = int(tmp[0]), int(tmp[1]), int(tmp[2])

a = np.zeros((h,w), dtype=int)
for i in range(h):
    tmp = input().split()
    for j in range(w):
        a[i][j] = int(tmp[j])

q = int(input())
lr = np.zeros((q,2), dtype=int)
for i in range(q):
    tmp = input().split()
    for j in range(2):
        lr[i][j] = int(tmp[j])

'''
print(h, w, d)
print(a)
print(q)
print(lr)'''

#sleep(0.1*a)

def place(k):
    return np.where(a == k)[0][0], np.where(a == k)[1][0]

def place_abs(t, s):
    z1, z2 = np.where(a == t)[0][0], np.where(a == t)[1][0]
    w1, w2 = np.where(a == s)[0][0], np.where(a == s)[1][0]
    return abs(z1 - w1) + abs(z2 - w2)



ans = []
for i in range(q):
    mp = 0
    cur = lr[i][0]
    while True:
        if cur == lr[i][1]:
            break
        mp += place_abs(cur, cur+d)
        cur += d
        #print(cur, mp)
    ans.append(mp)

for i in range(len(ans)):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from time import sleep
import numpy as np

tmp = input().split()
h, w, d = int(tmp[0]), int(tmp[1]), int(tmp[2])

a = np.zeros((h,w), dtype=int)
for i in range(h):
    tmp = input().split()
    for j in range(w):
        a[i][j] = int(tmp[j])

q = int(input())
lr = np.zeros((q,2), dtype=int)
for i in range(q):
    tmp = input().split()
    for j in range(2):
        lr[i][j] = int(tmp[j])

#print(h, w, d)
#print(a)
#print(q)
#print(lr)

#sleep(0.1*a)

def place(k):
    for i in range(h):
        for j in range(w):
            if a[i][j] == k:
                return i, j

ans = []
for i in range(q):
    mp = 0
    cur = lr[i][0]
    while True:
        if place(cur) == place(lr[i][1]):
            break
        mp += abs(place(cur)[0] - place(cur+d)[0]) + abs(place(cur)[1] - place(cur+d)[1])
        cur += d
        #print(cur, mp)
    ans.append(mp)

for i in range(len(ans)):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split())
n2c = {i:None for i in range(1, h*w+1)}
for i in range(h):
    i += 1
    for j,v in enumerate(input().split()):
        j = j + 1
        v = int(v)
        n2c[v] = (i,j)


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

q = int(input())
for i in range(q):
    cost = 0
    l,r = map(int, input().split())
    lt = range(l,r+1,d)
    l = list(map(lambda x:n2c[x], lt))
    for i in range(len(l)-1):
        x1,y1 = l[i]
        x2,y2 = l[i+1]
        cost += c(x1,y1,x2,y2)
    print(cost)