Problem:


Score : 400 points

Problem Statement

We have a grid with H rows and W columns. The square at the i-th row and the j-th column will be called Square (i,j).

The integers from 1 through H×W are written throughout the grid, and the integer written in Square (i,j) is A_{i,j}.

You, a magical girl, can teleport a piece placed on Square (i,j) to Square (x,y) by consuming |x-i|+|y-j| magic points.

You now have to take Q practical tests of your ability as a magical girl.

The i-th test will be conducted as follows:

Initially, a piece is placed on the square where the integer L_i is written.

Let x be the integer written in the square occupied by the piece. Repeatedly move the piece to the square where the integer x+D is written, as long as x is not R_i. The test ends when x=R_i.

Here, it is guaranteed that R_i-L_i is a multiple of D.

For each test, find the sum of magic points consumed during that test.

Constraints

1 \leq H,W \leq 300

1 \leq D \leq H×W

1 \leq A_{i,j} \leq H×W

A_{i,j} \neq A_{x,y} ((i,j) \neq (x,y))

1 \leq Q \leq 10^5

1 \leq L_i \leq R_i \leq H×W

(R_i-L_i) is a multiple of D.

Input

Input is given from Standard Input in the following format:

H W D
A_{1,1} A_{1,2} ... A_{1,W}
:
A_{H,1} A_{H,2} ... A_{H,W}
Q
L_1 R_1
:
L_Q R_Q

Output

For each test, print the sum of magic points consumed during that test.

Output should be in the order the tests are conducted.

Sample Input 1

3 3 2
1 4 3
2 5 7
8 9 6
1
4 8

Sample Output 1

5

4 is written in Square (1,2).

6 is written in Square (3,3).

8 is written in Square (3,1).

Thus, the sum of magic points consumed during the first test is (|3-1|+|3-2|)+(|3-3|+|1-3|)=5.

Sample Input 2

4 2 3
3 7
1 4
5 2
6 8
2
2 2
2 2

Sample Output 2

0
0

Note that there may be a test where the piece is not moved at all, and there may be multiple identical tests.

Sample Input 3

5 5 4
13 25 7 15 17
16 22 20 2 9
14 11 12 1 19
10 6 23 8 18
3 21 5 24 4
3
13 13
2 10
13 13

Sample Output 3

0
5
0



Sample input:
3 3 2
1 4 3
2 5 7
8 9 6
1
4 8


Sample output:
5

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

    MAP  = [None] * (H*W+1)
    COST = {}

    for i in range(H):
        for j, str_l in enumerate(input().split()):
            MAP[int(str_l)] = (i, j)

    Q = int(input())

    for i in range(Q):
        L, R = map(int, input().split())
        cost = 0
        keys = COST.keys()
        for j in range(int((R-L)/D)):
            try:
                cost += COST[L+D*j]
            except:
                COST[L+D*j] = abs(MAP[L][0] - MAP[L+D*j][0]) + abs(MAP[L][1] - MAP[L+D*j][1])
                cost += COST[L+D*j]
        print(cost)

func()

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
def magic(l,r,d,m):
    ans = 0
    while l < r:
        ans += abs(m[l] - m[l+d])
        l += d
    return ans

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

m = [0 for _ in range(h*w + 1)]

for i in range(h):
    a = [int(x) for x in input().split()]
    for j,k in enumerate(a):
        m[k] = i + j

q = int(input())

ans = []

for _ in range(q):
    l, r = map(int,input().split())
    ans.append(magic(l,r,d,m))

for x in ans:
    print(x)

Submission status: Wrong Answer

Solution code:
import sys

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

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

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

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

        #print(posses)

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

        for ans in res:
            print(ans)

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

Submission status: Wrong Answer

Solution code:
#input part
H,W,D = map(int, raw_input().split())
A={}
for i in range(H):
    tmp = map(int, raw_input().split())
    for j in range(W):
        A[tmp[j]]=(i+1,j+1)
Q=int(raw_input())
#examination part
mana = 0
LR_list=[]
for i in range(Q):
    LR_list.append(map(int, raw_input().split()))
    # print R - L
for i in range(Q):
    L,R = LR_list[i]
    while R - L != 0:
        # print L+D
        present_loc = A[L]
        next_loc = A[L+D]
        if next_loc[0] - present_loc[0] < 0:
            mana -= next_loc[0] - present_loc[0]
        else:
            mana += next_loc[0] - present_loc[0]
        if next_loc[1] - present_loc[1] < 0:
            mana -= next_loc[1] - present_loc[1]
        else:
            mana += next_loc[1] - present_loc[1]
        # print mana
        L += D
    print mana

Submission status: Wrong Answer

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())
L=[]
R=[]
S=[0]*(H*W+1)

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

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

for i in range(Q):
	print(S[R[i]]-S[L[i]])
	
print(L,R,S)

Submission status: Wrong Answer

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())
L=R=[]
S=[0]*(H*W+1)

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

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

for i in range(Q):
	print(S[R[i]]-S[L[i]])

Submission status: Wrong Answer

Solution code:
H, W, D = tuple(map(int, input().split()))
board = dict()
for h in range(H):
    row = tuple(map(int, input().split()))
    for w in range(W):
        board[row[w]] = (h, w)
delta = dict([(i, 0) for i in range(1, H*W+1)])
for d in range(D+1, H*W):
    delta[d] = delta[d-D] + abs(board[d][0] - board[d-D][0]) + abs(board[d][1] - board[d-D][1])

Q = int(input())

LRs = [tuple(map(int, input().split())) for _ in range(Q)]
result = [delta[LR[1]] - delta[LR[0]] for LR in LRs]

for r in result:
    print(r)

Submission status: Wrong Answer

Solution code:
line = input().split(" ")
a = list(map(int, line))
data = [0] * 90001
ans = 0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i, j]

memo = [0] * 90001

for i in range(1, a[0] * a[1]):
    if i < a[2]+1:
        memo[i] = 0
    else:
        memo[i] = memo[i - a[2]] + abs(data[i][0] - data[i - a[2]][0]) + abs(data[i][1] - data[i - a[2]][1])
times = int(input())
for i in range(0, times):
    line = list(map(int, input().split(" ")))
    print(memo[line[1]] - memo[line[0]])

Submission status: Wrong Answer

Solution code:
line = input().split(" ")
a = list(map(int, line))
data = [0] * 90001
ans = 0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i, j]

memo = [0] * 90001

for i in range(0, a[0] * a[1]):
    if i < a[2]+1:
        memo[i] = 0
    else:
        memo[i] = memo[i - a[2]] + abs(data[i][0] - data[i - a[2]][0]) + abs(data[i][1] - data[i - a[2]][1])
times = int(input())
for i in range(0, times):
    line = list(map(int, input().split(" ")))
    print(memo[line[1]] - memo[line[0]])

Submission status: Wrong Answer

Solution code:
line = input().split(" ")
a = list(map(int, line))
data = [0] * 90001
ans = 0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i, j]

memo = [0] * 90001

for i in range(0, a[0] * a[1]):
    if i <= a[2]:
        memo[i] = 0
    else:
        memo[i] = memo[i - a[2]] + abs(data[i][0] - data[i - a[2]][0]) + abs(data[i][1] - data[i - a[2]][1])
times = int(input())
for i in range(0, times):
    line = list(map(int, input().split(" ")))
    print(memo[line[1]-1] - memo[line[0]-1])

Submission status: Wrong Answer

Solution code:
line = input().split(" ")
a = list(map(int, line))
data = [0] * 90001
ans = 0
for i in range(0, a[0]):
    line = input().split(" ")
    temp = list(map(int, line))
    for j in range(0, a[1]):
        data[temp[j]] = [i, j]

memo = [0] * 90001

for i in range(0, a[0] * a[1]):
    if i < a[2] + 1:
        memo[i] = 0
    else:
        memo[i] = memo[i - a[2]] + abs(data[i][0] - data[i - a[2]][0]) + abs(data[i][1] - data[i - a[2]][1])
times = int(input())
for i in range(0, times):
    line = list(map(int, input().split(" ")))
    print(memo[line[1]] - memo[line[0]])

Submission status: Wrong Answer

Solution code:
H, W, D = list(map(int, input().split()))
 
dic = {}
for i in range(H):
    for j,v in enumerate(list(map(int, input().split()))):
        dic[v] = (i,j)
 
Q = int(input())
 
Qs = []
mi = 100000
ma = 1
for i in range(Q):
    l,r = list(map(int, input().split()))
    Qs.append((l,r))
    mi = min(mi, l)
    ma = max(ma, r)
 
S = [0 for i in range(100000)]
acm = 0
pi, pj = dic[mi]
for start in range(1, D):
    for i in range(start, ma+1, D):
        x,y = dic[i]
        acm += abs(x-pi) + abs(y-pj)
        S[i] = acm
        pi,pj = x,y
    
for i in Qs:
    l,r = i
    print(S[r] - S[l])

Submission status: Wrong Answer

Solution code:
import numpy as np

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 = np.zeros([H * W + 1])
for i in range(H * W, 0, -1):
    if i + D > H * W:
        scores[i] = 0
    else:
        x, y = stage[i]
        ox, oy = stage[i + D]
        scores[i] = scores[i + D] + abs(x - ox) + abs(y - oy)

for i in range(Q):
    L, R = tests[i]
    print(scores[L] - scores[R])

Submission status: Wrong Answer

Solution code:
b = str(input()).split()
h = int(b[0])
w = int(b[1])
d = int(b[2])
c =[]

def abs(a):
    if a > 0:
        return(a)
    else:
        return(-a)

for i in range(0,h):
    c.append(str(input()).split())

q = int(input())
lr = []
check = []
energy = 0

for i in range(0,q):
    lr.append(str(input()).split())
    
for i in range(0,h*w):
    check.append([])

for i in range(0,h):
    for j in range(0,w):
        check[int(c[i][j]) - 1]= [i,j]
        
for i in range(0,q):
    l = int(lr[i][0])
    r = int(lr[i][1])
    while l != r:
        energy += abs(check[l-1][0]-check[l+d-1][0]) + abs(check[l-1][1]-check[l+d-1][1])
        l += d
    print(energy)

Submission status: Wrong Answer

Solution code:
import sys
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

dp = {}

def dp_search(L, R, D, num_dic):
    global dp
    if (L, R) in dp:
        return dp[(L, R)]
    if L== R:
        return 0

    if L + D == R:
        now_pos = num_dic[L]
        next_pos = num_dic[R]
        dp[(L, R)] =  abs(next_pos[0] - now_pos[0]) + abs(next_pos[1] - now_pos[1])
        return dp[(L, R)]

    dp[(L, R)] = dp_search(L , R - D, D , num_dic) + dp_search(L + D , R, D , num_dic)

    return dp[(L, R)]


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [H, W, D] = [int(input_raw[0]), int(input_raw[1]), int(input_raw[2])]
    num_dic= {}
    for i in range(H):
        input_raw = read_func().strip().split()
        for j in range(W):
            num_dic[int(input_raw[j])] = (i, j)
    input_raw = read_func().strip().split()
    [Q] = [int(input_raw[0])]
    test_list = []
    for i in range(Q):
        input_raw = read_func().strip().split()
        test_list.append((int(input_raw[0]), int(input_raw[1])))

    dp = [[] for i in range(D)]

    for i in range(0, H * W):
        A = i + 1
        if len(dp[A % (D)]) == 0:
            dp[A % (D)].append((A, 0))
        else:
            (prev_point, prev_cost)= dp[A % D][len(dp[A % D]) - 1]
            prev_pos = num_dic[prev_point]
            now_pos = num_dic[A]
            dp[A % (D)].append((A, prev_cost +abs(prev_pos[0] - now_pos[0]) + abs(prev_pos[1] - now_pos[1])))

    for test in test_list:
        L = test[0]
        R = test[1]
        if L==R:
            print 0
        else:
            print (dp[L % (D)] [R/(D) - 1 + (1 if R % D != 0 else 0)][1] -
                    (dp[L % (D)] [L/(D) - 1 + (1 if L % D != 0 else 0)][1] if L/(D) > 1 else 0))




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding=utf-8
line = input().split(" ")
h = int(line[0])
w = int(line[1])
d = int(line[2])

table = [0 for _ in range(h*w+1)]
for hi in range(h):
    line = list(map(int, input().split(" ")))

    for wi in range(w):
        table[line[wi]] = (hi+1, wi+1)

def calc(l,r):
    ret = 0
    if l!=r:
        c1 = table[l]
        c2 = table[r]
        ret += abs(c1[0]-c2[0])+abs(c1[1]-c2[1])
    return ret

acc = [0 for _ in range(h*w+1)]
for dd in range(1,d+1):
    s = dd+d
    while s+d<=h*w:
        acc[s] = calc(s-d,s)+acc[s-d]
        s += d

q = int(input())
for _ in range(q):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])

    ret = acc[r] - acc[l]
    print(ret)

Submission status: Wrong Answer

Solution code:

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)]
d = [0] * ((H*W)+1)
num_dict = {}
y = 0
for aa in A:
    x = 0
    for a in aa:
        num_dict[a] = [x, y]
        x += 1
    y += 1

for i in range(D+1, H*W):
    d[i] = d[i-D] + abs(num_dict[i][0]-num_dict[i-D][0]) + abs(num_dict[i][1]-num_dict[i-D][1])
for l, r in LR:
    print(d[r]-d[l])

Submission status: Wrong Answer

Solution code:
h, w, D = map(int, raw_input().split())

d = dict()
for i in xrange(h):
    j = 0
    for n in map(int, raw_input().split()):
        d[n] = (i+1, j+1)
        j += 1

li = list()
for i in xrange(D):
    li.append(list())
for i in xrange(D):
    p = 1+i
    px, py = d[p]
    while p+D <= h*w:
        p += D
        x, y = d[p]
        li[p%D].append(abs(px-x)+abs(py-y))
        px = x
        py = y

for i in xrange(input()):
    l, r = map(int, raw_input().split())
    t = l%D
    s = l/D-1
    e = (r-l)/D
    if s == e:
        print 0
        continue
    if D > s:
        print sum(li[t][:e])
    else:
        print sum(li[t][s:e])

    # px, py = d[l]
    # while l <= r:
    #     x, y = d[l]
    #     ans += abs(px-x)+abs(py-y)
    #     px = x
    #     py = y
    #     l += D
    # print ans

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
        while L < R:
            if (L, R) in done:
                score += done[(L, R)]
                break
            new_x, new_y = stage[L + D]
            score += abs(new_x - x) + abs(new_y - y)
            x = new_x
            y = new_y
            L += D
        scores.append(score)
        done[(L, R)] = score

for score in scores:
    print(score)

Submission status: Wrong Answer

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

A = [[0 for i in range(W)] for j in range(H)]
dic = {}
for i in range(H):
    for j,v in enumerate(list(map(int, input().split()))):
        A[i][j] = v
        dic[v] = (i,j)

Q = int(input())

Qs = []
mi = 10000000
for i in range(Q):
    l,r = list(map(int, input().split()))
    Qs.append((l,r))
    mi = min(mi, l)

Sum = [0 for i in range(100000)]

Submission status: Wrong Answer

Solution code:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

def search_index(num, arr, height):
	for i in range(height):
		if num in arr[i]:
			return i,arr[i].index(num)
	return -1,-1

maryoku = 0
for i in range(Q):
	ori_i,ori_j = search_index(LR[i][0], A, H)
	x = A[ori_i][ori_j]
	for i in range(LR[i][1] - LR[i][0]):
		x += D
		tra_i,tra_j = search_index(x, A, H)
		maryoku += abs(tra_i-ori_i) + abs(tra_j-ori_j)
		ori_i, ori_j = tra_i, tra_j
print maryoku

Submission status: Wrong Answer

Solution code:
h,w,d=map(int,input().split())
a=[]
www=[]
for i in range(h):
    www=list(map(int,input().split()))
    for j in range(len(www)):
        a.append(www[j])
q=int(input())
e=[list(map(int,input().split())) for i in range(q)]
n=0
val1=0
xx1,xx2,yy1,yy2=0,0,0,0
for k in range(q):
    val1=e[k][0]
    val2=0
    tot=0
    n=int((e[k][1]-e[k][0])/d)
    for i in range(1,n+1):
        val2=val1+d
        xx1=a.index(val1)//w #上から何番目か
        xx2=a.index(val2)//w
        yy1=a.index(val1)%w
        yy2=a.index(val2)%w
        if yy1==0: yy1=w
        if yy2==0: yy2=w
        tot+=abs(xx1-xx2)+abs(yy1-yy2)
        val1=val2
    print(tot)

Submission status: Wrong Answer

Solution code:
def d_practical_skill_test(H, W, D, A, Q, I):
    a = []
    for s in A:
        a.extend(s)
    tmp = []
    for i in range(D):
        i += 1 + D
        t = [0]
        while i <= H * W:
            t1 = a.index(i)
            t2 = a.index(i - D)
            j, k = t1 // W, t1 % H
            l, m = t2 // W, t2 % H
            t.append(t[-1] + abs(j - l) + abs(k - m))
            i += D
        tmp.append(t)
    print(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))

Submission status: Wrong Answer

Solution code:
h, w, D = map(int, raw_input().split())

d = dict()
for i in xrange(h):
    j = 0
    for n in map(int, raw_input().split()):
        d[n] = (i+1, j+1)
        j += 1

li = list()
for i in xrange(D):
    li.append(list())
    p = 1+i
    px, py = d[p]
    while p+D <= h*w:
        p += D
        x, y = d[p]
        li[i].append(abs(px-x)+abs(py-y))
        px = x
        py = y

for i in xrange(input()):
    l, r = map(int, raw_input().split())
    t = l%D
    s = l/D
    e = r/D
    ans = 0
    e-=1
    t -= 1
    if t <0:
        t = D-1
    if s == e:
        print 0
        continue
    if s-1 < 0:
        print sum(li[t][s:e])
    else:
        print sum(li[t][s-1:e])

    # px, py = d[l]
    # while l <= r:
    #     x, y = d[l]
    #     ans += abs(px-x)+abs(py-y)
    #     px = x
    #     py = y
    #     l += D
    # print ans

Submission status: Wrong Answer

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(D+1,H*W+1-D):
  d2[l]=abs(d[l][0]-d[l-D][0])+abs(d[l][1]-d[l-D][1])
for m in range(D+1,H*W+1-D):
  d2[m]+=d2[m-D]
Q=int(input())
for i in range(Q):
  a,b=map(int,input().split())
  if a==b:
    print(0)
  else:
    ans=d2[b]-d2[a]
    print(ans)

Submission status: Wrong Answer

Solution code:

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

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]
        zahyo2 = num_dict[z+D]
        ans += (abs(sum(zahyo1)-sum(zahyo2)))
        z = z + D
    print(ans)

Submission status: Wrong Answer

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

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

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

dic = [0] * (h * w)

for i in range(h):
    for j in range(w):
        dic[a[i][j] - 1] = i, j

s = [[0] * (h * w // d + 1) for i in range(d)]

for i in range(d):
    for j in range(1, h * w // d):
        b = i + d * (j - 1)
        c = i + d * j
        
        y, x = dic[b]
        ny, nx = dic[c]
        s[i][j] = s[i][j - 1] + abs(ny - y) + abs(nx - x)

q = int(input())

for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    print(s[l % d][r // d] - s[l % d][l // d])

Submission status: Wrong Answer

Solution code:
mozi=raw_input()
H=int(mozi.split(" ")[0])
W=int(mozi.split(" ")[1])
D=int(mozi.split(" ")[2])


maholist=[]
for _ in range(H):
    maholist.append(raw_input().split(" "))
Q=int(raw_input())
zahyo=[]
zahyo.append(len(maholist))
zahyo.append(len(maholist[0]))
zax1=0
zay1=0
zax2=0
zay2=0
MP=-1
for i in range(Q):
    mozi=raw_input()
    L=int(mozi.split(" ")[0])
    R=int(mozi.split(" ")[1])
    for j in range(zahyo[0]):
        for k in range(zahyo[1]):
            if L==maholist[j][k]:
                zax1=j
                zay1=k
            if R==maholist[j][k]:
                zax2=j
                zax2=k
    lrd=(R-L)/D
    for _ in range(lrd):
        if L==R:
            break
        for j in range(zahyo[0]):
            for k in range(zahyo[1]):
                ld=L+D
                if ld==int(maholist[j][k]):
                    MP+=abs(zax1-j)+abs(zay1-k)
                    L=L+D
                    zax1 = j
                    zay1 = k
print(MP)

Submission status: Wrong Answer

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(1, W * H + 1):
        for j in range(i + 1, W * H + 1):
            for k in range(j + 1, 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]
    start = [(y, x) for x in range(W) for y in range(H) if A[y][x] == L[i]][0]
    while curr < R[i]:
        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
        start = end
    print(tot)

Submission status: Wrong Answer

Solution code:
H, W, D = [int(i) for i in input().split()]
A = []
pos = [0] * (H*W+1) # keyに対応する値の書かれたAの座標を返す
for i in range(H):
    a = [int(k) for k in input().split()]
    for j in range(W):
        pos[a[j]] = (i+1, j+1) # a[j]がある、Aの座標
    A.append(a)
Q = int(input())
print(pos)
past = {}
for i in range(Q):
    ans = 0
    moumita = False
    initL, initR = [int(h) for h in input().split()]
    if (initL,initR) in past.keys():
        ans = past[(initL,initR)]
        moumita = True
    x = initL
    L,R = pos[x]
    while (not moumita) and x != initR:
        l, r = pos[x + D]
        ans += (abs(L-l) + abs(R-r))
        x = A[l - 1][r - 1]
        if x == initR:
            break
        
        L, R = l, r
    past[(L,R)] = ans
    print(ans)

Submission status: Wrong Answer

Solution code:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

def search_index(num, arr, height):
	for i in range(height):
		if num in arr[i]:
			return i,arr[i].index(num)
	return -1,-1

maryoku = 0
for i in range(Q):
	ori_i,ori_j = search_index(LR[i][0], A, H)
	x = A[ori_i][ori_j]
	while x == LR[i][1]:
		x += D
		tra_i,tra_j = search_index(x, A, H)
		maryoku += abs(tra_i-ori_i) + abs(tra_j-ori_j)
		ori_i, ori_j = tra_i, tra_j
print maryoku

Submission status: Wrong Answer

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

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

Solution code:
H,W,D = map(int,input().split(" "))
field = []
power = 0
for i in range(H):
    field.extend(list(map(int,input().split(" "))))
print(field)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split(" "))

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

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

Solution code:
H,W,D = map(int,input().split(" "))
field = []
power = 0
for i in range(H):
    field.extend(list(map(int,input().split(" "))))
print(field)
Q = int(input())
for i in range(Q):
    L,R = map(int,input().split(" "))
    point = field.index(L)

    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(point/W)+1
        y2 = point%W + 1

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

Submission status: Wrong Answer

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

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)
    for l, r in I:
        l = l - 1
        r = r - 1
        start = l % D
        print(tmp[start][r // D] - tmp[start][l // D])

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

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)
    for l, r in I:
        l = l - 1
        r = r - 1
        start = l % D
        print(tmp[start][r // D] - tmp[start][l // D])
    return None

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