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:
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(nextplace[0]-place[0])
        ans+=abs(nextplace[1]-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:

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

for i in range(Q):
    reduce_MP = 0
    num = exam[i][0]
    coord1 = coord_dict[num]
    while num < exam[i][1]:
        coord2 = coord_dict[num + D]
        reduce_MP += abs(coord1[0] - coord2[0]) + abs(coord1[1] - coord2[1])
        num += D
        coord1 = coord2
    print(reduce_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 = []
    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:
HWD = input().split()
H = int(HWD[0]); W = int(HWD[1]); D = int(HWD[2])
A = []
for i in range(H):
    a = input().split()
    for j in range(W):
        a[j] = int(a[j])
    A.append(a)
Q = int(input())

def judge(L,R):
    r = R % D
    loc = [[0,0]] * (int((R-L)/D) + 1)
    for i in range(H):
        for j in range(W):
            if A[i][j] % D == r and A[i][j] >= L and A[i][j] <= R:
                loc[int((A[i][j]-L)/D)] = [i,j]
    s_mp = 0
    for i in range(len(loc) - 1):
        s_mp += abs(loc[i+1][0]-loc[i][0]) + abs(loc[i+1][1]-loc[i][1])
    return(s_mp)

mp = 0
for i in range(Q):
    a = input().split()
    L = int(a[0])
    R = int(a[1])
    print(judge(L,R))

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())
s = []
g = []
search = []
for i in range(q):
    s, g = map(int, input().split())
    search.append([])
    while(s != g):
        search[i].append([s, s + d])
        s += d

for i in range(h):
    for j in range(w):
        for l in range(q):
            for k in range(len(search[l])):
                if(search[l][k][0] == A[i][j]):
                    search[l][k][0] = (i, j)
                elif(search[l][k][1] == A[i][j]):
                    search[l][k][1] = (i, j)

for i in range(q):
    ans = 0
    for x in search[i]:
        ans += abs(x[0][0] - x[1][0]) + abs(x[0][1] - x[1][1])
    print(ans)

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]

def MP1step(s, t):
	return abs(place[t][0] - place[s][0]) + abs(place[t][1] - place[s][1])

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

def search(x):
    j = 0
    for i, Ai in enumerate(A):
        if x in Ai:
            j = Ai.index(x)
            break
    return (i+1,j+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:
# -*- coding: utf-8 -*-
"""
D - Practical Skill Test
https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

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


@lru_cache(maxsize=None)
def sub_solve(l, r, D):
    sx, sy = numbers[l]
    ans = 0
    while True:
        if l == r:
            break
        gx, gy = numbers[l+D]
        ans += abs(sx - gx) + abs(sy - gy)
        l += D
        sx, sy = gx, gy
    return ans


def solve(numbers, queries, D):
    for l, r in queries:
        ans = sub_solve(l, r, 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, D)


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

Submission status: Time Limit Exceeded

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

n=int(input())

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

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

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

    buf = H * W
    dict_buf = {}
    for i in range(1, buf+1):
        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 sys,collections
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
 
H,W,D = Is()
d = dict()
for i in range(H):
    s = Is()
    for j,e in enumerate(s):
        d[e] = (i,j)
Q = I()
for q in range(Q):
    l,r = Is()
    maho = 0
    for k in range(l,r,D):
        maho += abs(d[k+D][0] - d[k][0]) + abs(d[k+D][1] - d[k][1])
    print(maho)

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 = []
cs = []
for i in range(h * w):
    r, c = np.where(a == i + 1)
    rs.append(r[0])
    cs.append(c[0])
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
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(nextplace[0]-place[0])
        ans+=abs(nextplace[1]-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:
import numpy
H, W, D = map(int, input().split())
A = numpy.array([list(map(int, input().split())) for i in range(H)])
Q = int(input())
LR = [list(map(int, input().split())) for i in range(Q)]

num_dict = {}
y = 0
for aa in A:
    x = 0
    for a in aa:
        num_dict[a] = [x, y]
        x += 1
    y += 1

for l, r in LR:
    ans = 0
    z = l
    while z != r:
        zahyo1 = num_dict[z]
        x1, y1 = int(zahyo1[0]), int(zahyo1[1])
        zahyo2 = num_dict[z+D]
        x2, y2 = int(zahyo2[0]), int(zahyo2[1])
        ans += (abs(x1-x2)+abs(y1-y2))
        z = z + D
    print(ans)

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 += str(tmp[start][r // D] - tmp[start][l // D]) + '\n'
    return ans[:-1]

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

Submission status: Time Limit Exceeded

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

for i in range(1,H+1):
	A=list(map(int,input().split()))
	for idx,a in enumerate(A):
		X[a]=(i,idx+1)

Q=int(input())
memo=[[0 for i in range(H*W+1)] for j in range(H*W+1)]
for i in range(Q):
	mp=0
	L,R=list(map(int,input().split()))
	now=L
	if memo[L][R]!=0:
		print(memo[L][R])
	else:
		while now!=R:
			mp+=abs(X[now+D][0]-X[now][0])+abs(X[now+D][1]-X[now][1])
			memo[L][R]=mp
			now+=D
		print(mp)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import os
import sys
import math
import numpy as np


if __name__ == '__main__':
    H, W, D = list(map(int, input().split()))
    coordinates = np.zeros([H*W+1, 2], dtype=int)
    for i in range(H):
        line = list(map(int, input().split()))
        for j, x in enumerate(line):
            coordinates[x] = i, j


    # board = np.array([list(map(int, input().split())) for i in range(H)])
    Q = int(input())

    Qs = np.array([list(map(int, input().split())) for i in range(Q)])

    # coordinates = np.array([np.where(board == i+1) for i in range(H*W)]).reshape(H*W, 2)
    # coordinates = np.array([np.array(np.where(board == i+1)).reshape(-1) for i in range(H*W)])
    x_coordinates, y_coordinates = np.split(coordinates, 2, axis=1)
    x_diff = np.abs(x_coordinates[:-D] - x_coordinates[D:])
    y_diff = np.abs(y_coordinates[:-D] - y_coordinates[D:])
    # print(coordinates)

    memo = {}

    for L, R in Qs:
        if L == R:
            print(0)
            continue
        elif (L, R) in memo:
            print(memo[(L, R)])
            continue
        nums = np.arange(L, R, D)
        xs = x_diff[nums]
        ys = y_diff[nums]
        ans = int(sum(xs)+sum(ys))
        # print(nums, xs, ys)

        # ans = np.sum(np.abs(xs[1:] - xs[:-1])) + np.sum(np.abs(ys[1:] - ys[:-1]))
        print(ans)

        memo[(L, R)] = ans

Submission status: Time Limit Exceeded

Solution code:
H,W,D=map(int,input().split())
d=[[0,0] for i in range(H*W+1)]
d2=[0 for i in range(H*W+1)]
for j in range(H):
  a=[int(x) for x in input().split()]
  for k in range(W):
    d[a[k]]=[j+1,k+1]
for l in range(1,H*W+1-D):
  d2[l]=abs(d[l][0]-d[l+D][0])+abs(d[l][1]-d[l+D][1])
Q=int(input())
for i in range(Q):
  a,b=map(int,input().split())
  if a==b:
    print(0)
  else:
    cnt=int((b-a)/D)
    ans=0
    for j in range(cnt):
      ans+=d2[a+(j*D)]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def get_index(input_list, input_H, input_L):
  index_input_list=input_list.index(input_L)
  return index_input_list/input_H, index_input_list%input_H

H, W, D=map(int, raw_input().split())
tmp_list_A=[map(int, raw_input().split()) for i in range(H)]
list_A=[flatten for inner in tmp_list_A for flatten in inner]
Q=int(raw_input())
list_LQ=[map(int, raw_input().split()) for i in range(Q)]

len_list_A=H*W
for i in range(Q):
  L=list_LQ[i][0]
  Q=list_LQ[i][1]

  sum_maryoku=0
  len_loop=(Q-L)/D
  index_i, index_j=get_index(list_A, H, L)
  for j in range(len_loop):
    next_index_i, next_index_j=get_index(list_A, H, L+D)
    sum_maryoku=sum_maryoku+abs(next_index_i-index_i)+abs(next_index_j-index_j)

    index_i=next_index_i
    index_j=next_index_j
    L=L+D

  print sum_maryoku

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)

for i in range(Q):
    cost=0
    L,R = LR[i][0],LR[i][1]
    if L == R:
        print(cost)
    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)

Submission status: Time Limit Exceeded

Solution code:

H, W, D = map(int, input().split())
masu = [[] for i in range(H)]
for i in range(H):
    masu[i] = tuple([int(i) for i in input().split()])
masu = tuple(masu)
Q = int(input())

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

coord_dict = {}
for i in range(H):
    for j in range(W):
        coord_dict.update({masu[i][j] : (i,j)})

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

Submission status: Time Limit Exceeded

Solution code:
h,w,d = map(int,input().split(" "))
board = [input().split(" ") for i in range(h)]

q = int(input())
for i in range(q):
    l,r = map(int,input().split(" "))
    n = int((r-l)/d)
    count = 0
    x = []
    y = []
    for k in range(h):
        if str(l) in board[k]:
            x.append(board[k].index(str(l)))
            y.append(k)
    for j in range(n):
        for k in range(h):
            if str(l+(j+1)*d) in board[k]:
                x.append(board[k].index(str(l+(j+1)*d)))
                y.append(k)
        count = count + abs(int(x[j+1])-int(x[j])) + abs(y[j+1]-y[j])
    print(count)

Submission status: Time Limit Exceeded

Solution code:
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(" "))))

for exam in exams:
  sun_energy = 0
  current = ()
  for y in range(len(masu)):
    if exam[0] in masu[y]:
      current = (y,masu[y].index(exam[0]))
      break
  while not masu[current[0]][current[1]]== exam[1]:
    target = masu[current[0]][current[1]]+D
    target_pos = ()
    for y in range(len(masu)):
      if target in masu[y]:
        target_pos = (y,masu[y].index(target))
        break
    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:
# -*- 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][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,raw_input().split())
C={}
for i in range(H):
	A=map(int,raw_input().split())
	cnt=1
	for j in A:
		C[j]=(i+1,cnt)
		cnt+=1


Q=input()
memo={}
for i in range(Q):
	L,R=map(int,raw_input().split())

	if (L,R) in memo:
		print memo[(L,R)]
		continue
	ans=0
	for j in range(L,R,D):
		ans+=abs(C[j][0]-C[j+D][0])+abs(C[j][1]-C[j+D][1])
		memo[(j,j+D)]=abs(C[j][0]-C[j+D][0])+abs(C[j][1]-C[j+D][1])
	memo[(L,R)]=ans
	print ans

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


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

    # create l to r route
    route = np.arange(l, r + 1, d)

    points = np.squeeze([np.where(field == ch) for ch in route])
    next_points = np.vstack([points[1:], points[-1]])

    cost = np.abs(points - next_points).sum()
    return cost


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

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

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

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

Submission status: Time Limit Exceeded

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

def power(L, R):
    ans = 0
    for i in range(int((R-L)/D) + 1):
        for j in range(H):
            if L in A[j]:
                x,y = j, A[j].index(L)
                break
        if i != 0:
            ans += abs(x - px) + abs(y - py)
        px, py = x,y
        L += D
    print(ans)

for k in range(Q):
    L1, R1 = [int(i) for i in input().split()]
    power(L1,R1)

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]))
for i in range(in1[0]):
    arr[i]=input().split(" ")

#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)
    #print(start,end)
    while start != end:
        #print("ans",ans)
        nextplace=np.where(arr==start+in1[2])#[1][0]
        ans+=abs(nextplace[0][0]-place[0][0])
        ans+=abs(nextplace[1][0]-place[1][0])
        start+=in1[2]
        place=nextplace

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

Submission status: Time Limit Exceeded

Solution code:
def mahou(p2, p1):
    return abs(p2[0] - p1[0]) + abs(p2[1] - p1[1])

H, W, D = 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)]

Map = [[0, 0] for i in range(H * W + 1)]
for i in range(len(A)):
    for j in range(len(A[i])):
        Map[A[i][j]] = [i + 1, j + 1]
        
for l, r in LR:
    ans = 0
    for i in range(l, r, D):
        ans += mahou(Map[i + D], Map[i])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

H,W,D=map(int,input().split())
A=[[-1for i in range(W)]for j in range(H)]
B=[]
for i in range(H):
    A[i]=list(map(int,input().split()))
    B.append(set(A[i]))
Q=int(input())
L=[-1for i in range(Q)]
R=[-1for i in range(Q)]
for i in range(Q):
    L[i],R[i]=map(int,input().split())
    
d={}
    
for i in range(Q):
    MP=0
    x=L[i]
    for j in range(H):
        if(x in B[j]):
            Px=A[j].index(x)
            Py=j
    while(x!=R[i]):
        if(x in d):
            MP+=d[x][0]
            Px=d[x][1]
            Py=d[x][2]
            x+=D
        else:
            x+=D
            for j in range(H):
                if(x in B[j]):
                    Pnx=A[j].index(x)
                    Pny=j
                    MPd=abs(Px-Pnx)+abs(Py-Pny)
                    d[x-D]=[MPd,Pnx,Pny]
                    MP+=MPd
                    Px=Pnx
                    Py=Pny
                    break
                
    print(MP)

#print(d)
"""
x=[[0,1,2],[3,4,5],[6,7,8]]
for i in range(len(x)):
    if(5 in x[i]):
        print(i,x[i].index(5))
        break
"""

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

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:
        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
            
        
        print(nDis)

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
xy = [[0, 0] for i in range(h*w+1)]
for i in range(h):
    a = list(map(int, input().split()))
    for j in range(len(a)):
        xy[a[j]] = [j + 1, i + 1]
for i in range(int(input())):
    ans1, ans2 = 0, 0
    l, r = map(int, input().split())
    for j in range(l, r, d):
        ans1 += abs(xy[j+d][0]-xy[j][0])
        ans2 += abs(xy[j+d][1]-xy[j][1])
    print(ans1 + ans2)

Submission status: Time Limit Exceeded

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

n=int(input())


for i in range(n):
  z=0
  s,g=[int(i0) for i0 in input().split()]
  y0,x0=p[s]
  
  while s!=g:
    s = a[y0][x0]+d
    y,x = p[s]
    z +=abs(x-x0)+abs(y-y0)
    x0 = x
    y0 = y

  print(z)

Submission status: Time Limit Exceeded

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

q = int(input())
LR = []
for i in [0]*q:
  LR.append(list(map(int, input().split())))

result = {}
for i in range(q):
  if str(LR[i]) in result:
    print(result[str(LR[i])])
    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
  print(point)

Submission status: Time Limit Exceeded

Solution code:
hwd = list(map(int,input().split()))
a = [ None for x in range(hwd[0])]

idx_dic = {}

for i in range(hwd[0]):
    a = list(map(int,input().split()))
    for j in range(hwd[1]):
        idx_dic[a[j]] = (i,j)
    
q = int(input())
lr = [None for x in range(q)]
move_list = [[] for x in range(q)]

for i in range(q):
    lr[i] = list(map(int,input().split()))
    l = lr[i][0]
    move_list[i].append(l)
    while(1):
        if l == lr[i][1]:
            move_list[i].append(lr[i][1])
            break
        else:
            l += hwd[2]
            move_list[i].append(l)

def telepoto(idx_dic,move_list):
    distance = [0 for x in range(len(move_list))]
    for i in range(len(move_list)):
        current_ml = move_list[i]
        for j in range(len(current_ml)-1):
            # x,y to X,Y
            x,y = idx_dic[current_ml[j]]
            X,Y = idx_dic[current_ml[j+1]]
            distance[i] += abs(x-X) + abs(y-Y)
    return distance

ans = telepoto(idx_dic,move_list)
for i in range(q):
    print(ans[i])

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 = [[-1,-1] for _ in range(H*W)]

def MP1step(s, t):
	if place[s-1] != [-1,-1]:
		s_x = place[s-1][0]
		s_y = place[s-1][1]
	else:
		for  i in range(H):
			for j in range(W):
				if A[i][j] == s:
					s_x = i
					s_y = j
					place[s-1][0] = i
					place[s-1][1] = j
	if place[t-1] != [-1,-1]:
		t_x = place[t-1][0]
		t_y = place[t-1][1]
	else:
		for  i in range(H):
			for j in range(W):
				if A[i][j] == t:
					t_x = i
					t_y = j
					place[t-1][0] = i
					place[t-1][1] = j
	return abs(t_x - s_x) + abs(t_y - s_y)

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())
xy = [[0, 0] for i in range(h*w+1)]
for i in range(h):
    a = list(map(int, input().split()))
    for j in range(len(a)):
        xy[a[j]] = [j + 1, i + 1]
for i in range(int(input())):
    ans = []
    l, r = map(int, input().split())
    for j in range(l, r, d):
        t1 = xy[j+d]
        t2 = xy[j]
        ans.append(abs(t1[0]-t2[0])+abs(t1[1]-t2[1]))
    print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
h, w, d = map(int, input().split())
xy = [[0, 0] for i in range(h*w+1)]
for i in range(h):
    a = list(map(int, input().split()))
    for j in range(len(a)):
        xy[a[j]] = [j + 1, i + 1]
for i in range(int(input())):
    ans = 0
    l, r = map(int, input().split())
    for j in range(l, r, d):
        t1 = xy[j+d]
        t2 = xy[j]
        ans += abs(t1[0]-t2[0])+abs(t1[1]-t2[1])
    print(ans)