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:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input()) # n=1
def inpm(): return map(int,input().split()) # x=1,y=2
def inpl(): return list(map(int, input().split())) # a=[1,2,3,4,5,...,n]
def inpls(): return list(input().split())  # a=['1','2','3',...,'n']
def inplm(n): return list(int(input()) for _ in range(n)) # x=[] 複数行
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)] # [[2,2,2,2],[1,1,1,1],[3,3,3,3]] 
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)]) # [[1,1,1,1],[2,2,2,2],[3,3,3,3]] 
def graph():
    n=inp()
    g=[[] for _ in range(n)]
    for i in range(n):
        a = inp()
        a -= 1
        g[i].append(a)
        g[a].append(i)
    return n,g

def main():
    h,w,d = inpm()
    a = inpll(h)
    MAP = [0 for _ in range(h*w)]
    for i in range(h):
        for j in range(w):
            MAP[a[i][j]-1] = (i,j)
    cnt = []
    for i in range(h*w-d):
        x = MAP[i]
        y = MAP[i+d]
        cost = abs(x[0]-y[0]) + abs(x[1]-y[1])
        cnt.append(cost)
    q = inp()
    dic = defaultdict(int)
    for i in range(h*w-d):
        sumation = 0
        for j in range((h*w-i)//d):
            key = [str(i),' ',str(i+d*j)]
            key = ''.join(key)
            if j > 0:
                sumation += cnt[i+d*(j-1)]
            dic[key] = sumation
    for _ in range(q):
        l,r = inpm()
        key = [str(l-1),' ',str(r-1)]
        key = ''.join(key)
        print(dic[key])
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
H, W, D = map(int, input().split())
status = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        status[A[j]] = (i+1, j+1)
Q = int(input())
Q = [list(map(int, input().split())) for _ in range(Q)]
memo = {}
# print(status)
for s, t in Q:
    ans = 0
    original_s = s
    if (s, t) in memo:
        print(memo[(s, t)])
        continue
    while s != t:
        tmp_t = s+D
        ans += abs((status[tmp_t][0] - status[s][0])) + abs(status[tmp_t][1]-status[s][1])
        memo[(s, tmp_t)] = ans
        s = tmp_t
    print(ans)

Submission status: Wrong Answer

Solution code:
H, W, D = map(int, input().split())
status = {}
for i in range(H):
    A = list(map(int, input().split()))
    for j in range(W):
        status[A[j]] = (i+1, j+1)
Q = int(input())
Q = [list(map(int, input().split())) for _ in range(Q)]
# print(status)
for s, t in Q:
    ans = 0
    while s != t:
        tmp_t = s+D
        ans += abs((status[tmp_t][0] - status[s][0]) + abs(status[tmp_t][1]-status[s][1]))
        s = tmp_t
    print(ans)

Submission status: Wrong Answer

Solution code:
import math
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
lis = [[0,0] for i in range(h * w)]
num = [[0] * math.ceil((h * w) // d + 1) for i in range(d)]
if d == 1:
    print("!!!!")

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

for i in range(h * w-d):
    num[i%d][i//d] = abs(lis[i][0]-lis[i+d][0])+abs(lis[i][1]-lis[i+d][1])

q = int(input())
for _ in range(q):
    now,goal = map(int,input().split())
    if now % d == 0:
        print(sum(num[now % d - 1][(now - now % d) // d-1:(goal - now % d) // d-1]))
    else:
        print(sum(num[now%d-1][(now-now%d)//d:(goal-now%d)//d]))

Submission status: Wrong Answer

Solution code:
import math
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
lis = [[0,0] for i in range(h * w)]
num = [[0] * math.ceil((h * w) // d + 1) for i in range(d)]

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

for i in range(h * w-d):
    num[i%d][i//d] = abs(lis[i][0]-lis[i+d][0])+abs(lis[i][1]-lis[i+d][1])
  #print(num)

q = int(input())
for _ in range(q):
    now,goal = map(int,input().split())
  #    print(num[now%d-1])
  #    print(num[now%d-1][(now-now%d)//d:(goal-now%d)//d])
    print(sum(num[now%d-1][(now-now%d)//d:(goal-now%d)//d]))

Submission status: Wrong Answer

Solution code:
import math
h,w,d = map(int,input().split())
a = [list(map(int,input().split())) for i in range(h)]
lis = [[0,0] for i in range(h * w)]
num = [[0] * math.ceil((h * w) // d + 1) for i in range(d)]

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

for i in range(h * w-d):
    num[i%d][i//d] = abs(lis[i][0]-lis[i+d][0])+abs(lis[i][1]-lis[i+d][1])
  #print(num)

q = int(input())
for _ in range(q):
    now,goal = map(int,input().split())
  #    print(num[now%d-1])
  #    print(num[now%d-1][now//d:goal//d])
    print(sum(num[now%d-1][now//d:goal//d]))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline


def main():
    H, W, D = map(int, input().split())
    A = []
    d = [0]*(H*W)
    for h in range(H):
        a = list(map(int, input().split()))
        A.append(a)
        for i, x in enumerate(a):
            d[x-1] = h*W + i
    Q = int(input())
    mp = [0]*(H*W+1)
    for i in range(H*W):
        if i >= D:
            mp[i] = mp[i-D] + abs(d[i-1]//W - d[i-D-1]//W) + abs(d[i-1]%W - d[i-D-1]%W)
    for q in range(Q):
        ans = 0
        l, r = map(int, input().split())
        print(mp[r] - mp[l])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
H,W,D = [int(x) for x in stdin.readline().rstrip().split()]
data = dict()
for i in range(H):
    for j,A in enumerate([int(x) for x in stdin.readline().rstrip().split()]):
        data[A] = (i,j)
dp = [0]*(H*W+1)
for j in range(H*W+1):
    if j > D:
        dp[j] = dp[j-D] + abs(data[j][0]-data[j-D][0] + abs(data[j][1]-data[j-D][1]))
Q = int(stdin.readline().rstrip())
for _ in range(Q):
    L,R = [int(x) for x in stdin.readline().rstrip().split()]
    print(dp[R]-dp[L])

Submission status: Wrong Answer

Solution code:
from sys import stdin
H,W,D = [int(x) for x in stdin.readline().rstrip().split()]
data = [0]*(H*W+1)
for i in range(H):
    for j,A in enumerate([int(x) for x in stdin.readline().rstrip().split()]):
        data[A] = (i,j)
dp = [0]*(H*W+1)
for j in range(H*W+1):
    if j > D:
        dp[j] = dp[j-D] + abs(data[j][0]-data[j-D][0] + abs(data[j][1]-data[j-D][1]))
Q = int(stdin.readline().rstrip())
for _ in range(Q):
    L,R = [int(x) for x in stdin.readline().rstrip().split()]
    print(dp[R]-dp[L])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)

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

dic = {}
K = H*W
memo = [[-1]*(K+1) for _ in range(K+1)]


def magic_test(L, R, power):
    if memo[L][R] != -1:
        return memo[L][R]
    if L == R:
        return power
    x, y = dic[L]
    nx, ny = dic[L+D]
    power += abs(x-nx) + abs(y-ny)
    memo[L][R] = magic_test(L+D, R, power)
    return memo[L][R]


for y in range(1, H+1):
    A = list(map(int, input().split()))

    for x, a in enumerate(A, 1):
        dic[a] = [x, y]

Q = int(input())
for _ in range(Q):
    L, R = map(int, input().split())
    ans = magic_test(L, R, 0)
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import itertools
from itertools import accumulate
def main():
    input = sys.stdin.readline
    def inputs():return [int(x) for x in input().split()]
    H,W,D = inputs()
    w = [[None]*W for i in range(H)]
    A = []
    for i in  range(H):
        B = inputs()
        A.append(B)
    E={i:[] for i in range(1,H*W+1)}
    for i in range(H):
        for j in range(W):
            a = A[i][j]
            if a<=H*W:
                E[a].append((i+1,j+1))
    dis = [0]*(H*W+1)
    for i in range(1,H*W+1):
        if i+D<H*W:
            #print(i+D)
            x = E[i][0][0]
            y = E[i][0][1]
            a = E[i+D][0][0]
            b = E[i+D][0][1]
            dis[i+D] = dis[i]+abs(a-x)+abs(b-y)
    Q = int(input())
    for i in range(Q):
        r,l = inputs()
        print(dis[l]-dis[r])
main()

Submission status: Wrong Answer

Solution code:
import sys
import itertools
from itertools import accumulate
def main():
    input = sys.stdin.readline
    def inputs():return [int(x) for x in input().split()]
    H,W,D = inputs()
    w = [[None]*W for i in range(H)]
    A = []
    for i in  range(H):
        B = inputs()
        A.append(B)
    E={i:[] for i in range(1,H*W+1)}
    for i in range(H):
        for j in range(W):
            a = A[i][j]
            if a<=H*W:
                E[a].append((i+1,j+1))
    print(E)
    dis = [0]*(H*W+1)
    for i in range(1,H*W+1):
        if i+D<H*W:
            print(i+D)
            x = E[i][0][0]
            y = E[i][0][1]
            a = E[i+D][0][0]
            b = E[i+D][0][1]
            dis[i+D] = dis[i]+abs(a-x)+abs(b-y)
    Q = int(input())
    for i in range(Q):
        r,l = inputs()
        print(dis[l]-dis[r])
main()

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

Point = {}
for y in range(H) :
    for x in range(W) :
        Point[A[y][x]] = (y, x)

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

for i in range(Q) :
    res = 0
    l,r = LR[i][0], LR[i][1]
    while l != r :
        l += D
        res += dist(Point[l][0], Point[l][1], Point[l-D][0], Point[l-D][0])
    print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np
H, W, D = map(int, input().split())
grid = [[] for h in range(H)]

for h in range(H):
    grid[h] = [int(_) for _ in input().split()]

distance = [0 for i in range(H * W + 1)]
np_grid = np.array(grid).ravel()
for d in range(D + 1, H * W + 1):
    y = np.where(np_grid == d)[0][0] // 3
    x = np.where(np_grid == d)[0][0] % 3
    j = np.where(np_grid == d - D)[0][0] // 3
    i = np.where(np_grid == d - D)[0][0] % 3
    dist = abs(y - j) + abs(x - i)
    #print(d, ':', dist)
    distance[d] = distance[d - D] + dist

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

Submission status: Wrong Answer

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

Q = int(input())
dp = [H*W+2]*(H*W+1)

for i in range(1,H*W+1):
    if i > D:
        dp[i] = min(dp[i], dp[i-D] + abs(mass[i][0] - mass[i-D][0]) + abs(mass[i][1] - mass[i-D][1]))
    else:
        dp[i] = mass[i][0] + mass[i][1]

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

Submission status: Wrong Answer

Solution code:
H,W,D=map(int,input().split());A=[list(map(int,input().split())) for _ in range(H)];Q=int(input());d=[0]*(H*W+1);g=[0]*(H*W+1)
for i in range(H):
  for j in range(W):d[A[i][j]]=[i,j]
for i in range(1,H*W-D):
  g[i+D]=abs(d[i+D][0]-d[i][0])+abs(d[i+D][1]-d[i][1])+g[i]
for q in range(Q):
  l,r=map(int,input().split());print(g[r]-g[l])

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def solve():
  h,w,d  = (int(i) for i in input().split())
  a = []
  for i in range(h):
    tmp = list(int(i) for i in input().split())
    a.append(tmp)

  query = [False]*(h*w)
  distance = [0]*(h*w+1)
  for i in range(h):
    for j in range(w):
      number = a[i][j] - 1
      query[number] = (i,j)
  q = int(input())
  
  for i in range(d+1,h*w):
    leftx,lefty = query[i-d]
    rightx,righty = query[i]
    distance[i] = distance[i-d]+abs(rightx-leftx)+abs(righty-lefty)

  
  for i in range(q):
    l,r = (int(m) for m in input().split())
    print(distance[r-1]-distance[l-1])
  
solve()

Submission status: Wrong Answer

Solution code:
# 14:59

H, W, D = map(int, input().split())
G = [0] * (H*W)
for h in range(H):
    l = [int(x) for x in input().split()]
    for w in range(W):
        G[l[w]-1] = (h, w)

stepCost = [-100]*(H*W+1)
for s in range(0, H*W-D):
    sx, sy = G[s]
    tx, ty = G[s+D]
    stepCost[s] = abs(sx - tx) + abs(sy - ty)
#print(stepCost)

C = [([0] * ((H*W)//D+1)) for i in range(D)]

for rem in range(0, D):
    Crem = C[rem]
    a = 0
    for j in range(rem, H*W+1, D):
        a += stepCost[j]
        Crem[(j-rem)//D] = a

Q = int(input())
for i in range(Q):
    L, R = map(int, input().split())
    L -= 1
    R -= 1
    rem = L % D 
    Crem = C[rem]
    #print(Crem)
    #print((R-rem)//D, (L-rem)//D)
    print(Crem[(R-rem)//D-1] - max(0, Crem[(L-rem)//D-1]))

Submission status: Wrong Answer

Solution code:
h, w, d = map(int, input().split())
a = []
for i in range(h):
  a.append(list(map(int, input().split())))
numlist = [[0, 0]] * (h * w)
for i in range(h):
  for j in range(w):
    numlist[a[i][j]-1][0] += i + 1
    numlist[a[i][j]-1][1] += j + 1
    
q = int(input())
mp = 0

for k in range(q):
  l, r = map(int, input().split())
  for n in range(r, l, d):
    mp += abs(numlist[n-1][0] - numlist[n+d-1][0]) + abs(numlist[n-1][1] - numlist[n+d-1][1])
  print(mp)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict


def solve(row, col, d):
    x_map = defaultdict()

    for i in range(row):
        a_i = list(map(int, input().split()))
        for j in range(col):
            x_map[a_i[j]-1] = (i, j)

    q = int(input())

    mp = 0
    dp = [[None]*(row*col)]*(row*col)

    for _ in range(q):
        l, r = map(int, input().split())
        if dp[l-1][r-1] is None:
            for current_pos in range(l+d-1, r, d):
                cp = x_map[current_pos]
                pp = x_map[current_pos-d]
                mp += abs(cp[1] - pp[1]) + abs(cp[0] - pp[0])
            dp[l-1][r-1] = mp
        print(dp[l-1][r-1])
        mp = 0


if __name__ == '__main__':
    row, col, d = map(int, input().split())
    solve(row, col, d)

Submission status: Wrong Answer

Solution code:
import numpy as np

H, W, D = map(int, input().split())
px = np.zeros((H*W+1+D))
py = np.zeros((H*W+1+D))
d = np.zeros((H*W+D), dtype='int64')

j = np.arange(H)
for i in range(H):
    A = list(map(int, input().split()))
    px[A] = i
    py[A] = j

idx = np.arange(D+1, H*W+1, D)
for i in range(D):
    x = np.cumsum(np.abs(px[idx+i]-px[idx+i-D]) + np.abs(py[idx+i]-py[idx+i-D]))
    d[idx+i] = x

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

Submission status: Wrong Answer

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

#a = [0] * (H*W+1)
a = {}

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

#table = [0] * (H*W+1)
table = {i:0 for i in range(H*W+1)}

for i in range(D+1, H*W):
    x, y = a[i]
    x_, y_ = a[i-D]
    table[i] = table[i-D] + abs(x - x_) + abs(y - y_)

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

Submission status: Wrong Answer

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

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

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

table = [0] * (H*W+1)
for i in range(D+1, H*W):
    x, y = a[i]
    x_, y_ = a[i-D]
    table[i] = table[i-D] + abs(x - x_) + abs(y - y_)

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

Submission status: Wrong Answer

Solution code:
H,W,D = map(int, input().split())
grid = []
grid_dict = {}
for i in range(H):
    grid.append([])
    for j,s in enumerate(input().split()):
        grid[i].append(int(s))
        grid_dict[int(s)] = [i,j]

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

man = lambda x,y: abs(x[0]-y[0])+abs(x[1]-y[1])
# [print(i) for i in grid]
# [print(i) for i in exam]
# [print(i) for i in grid_dict.items()]

power = [[0] for i in range(D)]
for i in range(1,H*W+1):
    if i + D not in grid_dict:
        break
    power[i%D].append(power[i%D][-1] + man(grid_dict[i], grid_dict[i+D]))
# [print(i) for i in power]
for l,r in exam:
    if r == l:
        print(0)
        continue
    dif = (r-l)//D
    tmp = (l-D)//D
    if tmp < 0:
        tmp = 0
    print(power[r%D][tmp+dif]-power[r%D][tmp])

Submission status: Wrong Answer

Solution code:
h, w, d = map(int, input().split())
a_array = [[int(x) for x in input().split()] for y in range(h)]
q = int(input())
lr_array = [[int(x) for x in input().split()] for y in range(q)]

whole = []
for i in range(h):
    for j in range(w):
        whole.append([a_array[i][j], i+1, j+1])
whole = [[x[1], x[2]] for x in sorted(whole, key=lambda x: x[0])]
for l, r in lr_array:
    res = 0
    now_x, now_y = whole[l-1]
    for i in range(l-1+d, r, d):
        next_x, next_y = whole[i]
        res += abs(now_x- next_x) + abs(now_y-next_y)
        now_x, now_y = whole[l]
    print(res)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import collections


def solve(H: int, W: int, D: int, A: "List[List[int]]", Q: int, L: "List[int]", R: "List[int]"):
    pdic = {}

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

    dp = [[0 for _ in range(H*W // D + 1)] for _ in range(D)]

    for i in range(D):
        for j in range(1,H*W//D):
            dp[i][j] = dp[i][j-1]
            c = j*D + i
            if (c-D) > 0:
                dp[i][j] += abs(pdic[c][0] - pdic[c-D][0])
                dp[i][j] += abs(pdic[c][1] - pdic[c-D][1])

    for l,r in zip(L,R):
        res = 0
        l1 = l % D
        r1 = l1

        l2 = l // D
        r2 = r // D

        if l1 == 0:
            l2 -= 1
            r2 -= 1

        print(dp[r1][r2]-dp[l1][l2])


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    A = [ [ int(next(tokens)) for _ in range(W) ] for _ in range(H) ]  # type: "List[List[int]]"
    Q = int(next(tokens))  # type: int
    L = [int()] * (Q)  # type: "List[int]" 
    R = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    solve(H, W, D, A, Q, L, R)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

res = 0
for i in range(10 **8):
  res += 1
  
  
print(res)

Submission status: Wrong Answer

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

res = 0
for i in range(10 **7):
  res += 1
  
  
print(res)

Submission status: Wrong Answer

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

for _ in range(q):
    start, end = map(int, input().split())
    cand = [i for i in range(start, end+1, d)]
    dist = 0
    for time in range(len(cand)):
        if time == 0:
            x_prev = [k for k in range(h) if cand[time] in loca[k]][0]
            y_prev = [k for k in range(w) if cand[time] == loca[x_prev][k]][0]
        else:
            x_next = [k for k in range(h) if cand[time] in loca[k]][0]
            y_next = [k for k in range(w) if cand[time] == loca[x_next][k]][0]
            dist += (abs(x_next- x_prev) + abs(y_next - y_prev))
            x_prev= x_next
            y_prev = x_next
    print(dist)

Submission status: Wrong Answer

Solution code:
h, w, d = map(int, input().split())
loca = []
for _ in range(h):
    tmp = list(map(int, input().split()))
    loca.append(tmp)
q = int(input())
x_cor = []
y_cor = []
for _ in range(q):
    start, end = map(int, input().split())
    cand = [i for i in range(start, end+1, d)]
    for num in cand:
        x = [k for k in range(h) if num in loca[k]][0]
        y = [k for k in range(w) if num == loca[x][k]][0]
        x_cor.append(x)
        y_cor.append(y)
    dist = 0
    for i in range(len(x_cor)-1):
        dist += (abs(x_cor[i+1]- x_cor[i]) + abs(y_cor[i+1] - y_cor[i]))
    print(dist)

Submission status: Wrong Answer

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

sumL=[0 for i in range(h*w+1)]
for i in range(h*w):
  if i>=d:
    sumL[i+1]=sumL[i+1-d]+abs(L[i][0]-L[i-d][0])+abs(L[i][1]-L[i-d][1])
print(sumL)
q=int(input())
QL=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  print(sumL[QL[i][1]]-sumL[QL[i][0]])

Submission status: Wrong Answer

Solution code:
def sol():
    h,w,d=map(int,input().split())
    a=[[int(i) for i in input().split()] for i in range(h)]
    t,ans={},{}
    for i in range(h):
        for j in range(w):
            t[a[i][j]]=(i,j)
    for i in t:
        o,p=t[i]
        if i+d in t: ans[i]=abs(o-t[i+d][0])+abs(p-t[i+d][1])
    q=int(input())
    x={}
    for i in range(q):
        chk=0
        l,r=map(int,input().split())
        s=l
        for j in range(300*300):
            if l in x: 
                chk=x[l]
                break
            if s==r: break
            chk+=ans[s]
            s+=d
        if l not in x: x[l]=chk
        print(chk)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
def sol():
    h,w,d=map(int,input().split())
    a=[[int(i) for i in input().split()] for i in range(h)]
    t,ans={},{}
    for i in range(h):
        for j in range(w):
            t[a[i][j]]=(i,j)
    for i in t:
        o,p=t[i]
        if i+d in t: ans[i]=abs(o-t[i+d][0])+abs(p-t[i+d][1])
    q=int(input())
    x={}
    for i in range(q):
        chk=0
        l,r=map(int,input().split())
        s=l
        for j in range(300*300):
            if l in x: break
            if s==r: break
            chk+=ans[s]
            s+=d
        if l not in x: x[l]=chk
        print(chk)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
def sol():
    h,w,d=map(int,input().split())
    a=[[int(i) for i in input().split()] for i in range(h)]
    t,ans={},{}
    for i in range(h):
        for j in range(w):
            t[a[i][j]]=(i,j)
    for i in t:
        o,p=t[i]
        print(i,o,p)
        if i+d in t: ans[i]=abs(o-t[i+d][0])+abs(p-t[i+d][1])
    print(ans)
    exit()
    q=int(input())
    for i in range(q):
        chk=0
        l,r=map(int,input().split())
        for j in range(300*300):
            if l==r: break
            chk+=ans[l]
            l+=d
        print(chk)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
def sol():
    h,w,d=map(int,input().split())
    a=[[int(i) for i in input().split()] for i in range(h)]
    t,ans={},{}
    for i in range(h):
        for j in range(w):
            t[a[i][j]]=(i,j)
    for i in t:
        o,p=t[i]
        if i+d in t: ans[i]=abs(o-t[i+d][0])+abs(p-t[i+d][1])
    q=int(input())
    for i in range(q):
        chk=0
        l,r=map(int,input().split())
        for j in range(300):
            if l==r: break
            chk+=ans[l]
            l+=d
        print(chk)

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

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

    q=int(input())
    ans={}
    for i in range(q):
        chk=0
        l,r=map(int,input().split())
        s=l
        o,p=t[l]
        for j in range(300):
            if (l,r) in ans:
                chk=ans[(l,r)]
                break
            if s==r: break
            chk+=abs(o-t[s+d][0])+abs(p-t[s+d][1])
            o=t[s+d][0]
            p=t[s+d][1]
            s+=d
        print(chk)
        if (l,r) not in ans: ans[(l,r)]=chk

if __name__=="__main__":
    sol()

Submission status: Wrong Answer

Solution code:
n=0
h,w,d=map(int,input().split())
x=[0]*(h*w)
y=[0]*(h*w)
for i in range(h):
    for a in input().split():
        A=int(a)-1
        x[A]=n%w
        y[A]=n//h
        n+=1
        
c=[0]*(h*w)
for i in range(h*w):
    if i>=d:
        c[i]=c[i-d]+abs(x[i]-x[i-d])+abs(y[i]-y[i-d])
q=int(input())
for i in range(q):
    l,r=map(int,input().split())
    print(c[r-1]-c[l-1])

Submission status: Wrong Answer

Solution code:
h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
T=[[0 for _ in range((h*w)//d)] for _ in range(d)]
for i in range(d):
  for j in range((h*w)//d):
    if i+1+d*(j+1)>h*w:
      continue
    elif j==0:
      T[i][j]=Dist(i+1,i+1+d)
    else:  
      T[i][j]=T[i][j-1]+Dist(i+1+d*j,i+1+d*(j+1))
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  x=l%d
  ll=(l-x)//d-1
  rr=(r-x)//d-1
  if x==0:
    ll-=1
    rr-=1
  print(T[x-1][rr]-T[x-1][ll] if ll>=0 and rr>=0 else T[x-1][rr])

Submission status: Wrong Answer

Solution code:
h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
T=[[0 for _ in range((h*w)//d)] for _ in range(d)]
for i in range(d):
  for j in range((h*w)//d):
    if i+1+d*(j+1)>h*w:
      continue
    elif j==0:
      T[i][j]=Dist(i+1,i+1+d)
    else:  
      T[i][j]=T[i][j-1]+Dist(i+1+d*j,i+1+d*(j+1))
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  x=l%d
  ll=(l-x)//d-1
  rr=(r-x)//d-1
  if x==0:
    ll-=1
    rr-=1
  print(T[x-1][rr]-T[x-1][ll] if l>=0 and r>=0 else T[x-1][rr])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

h, w, d = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(h)]
q = int(input())
piece = [list(map(int, input().split())) for _ in range(q)]

mp = 0
dict = defaultdict(int)

for i, row in enumerate(grid):
    for j, col in enumerate(row):
        dict[col] = (i+1, j+1)

for i in range(q):
    start, end = piece[i]
    while True:
        if start == end:
            break
        i, j = dict[start]
        start += d
        x, y = dict[start]
        mp += abs(x-i) + abs(y-j)

print(mp)

Submission status: Wrong Answer

Solution code:
#D問題
import math
H,W,D=map(int,input().split())
A=[]
amap=[[-1,-1] for i in range(H*W+D)]
for i in range(H):
    a=list(map(int,input().split()))
    for j in range(W):
        amap[a[j]]=[i,j]
    A.append(a)
Q=int(input())
LR=[list(map(int,input().split())) for i in range(Q)]
syo=int(H*W/D)
dp=[[0 for i in range(syo+1)] for j in range(D)] #dp[modD][/D]=(modDまでの距離)
for i in range(1,syo+1):
    j=0
    if i == syo:
        d=H*W%D
        for j in range(d):
            dp[j][i]=dp[j][i-1]+abs(amap[i*D+j][0]-amap[i*D+j-i][0])+abs(amap[i*D+j][1]-amap[i*D+j-i][1])  
    for j in range(D):
        dp[j][i]=dp[j][i-1]+abs(amap[i*D+j][0]-amap[i*D+j-i][0])+abs(amap[i*D+j][1]-amap[i*D+j-i][1])
for i in range(Q):
    L=LR[i][0]
    R=LR[i][1]
    mod=L%D
    l=int(L/D)
    r=int(R/D)
    print(dp[mod][r]-dp[mod][l])

Submission status: Wrong Answer

Solution code:
#D問題
import math
H,W,D=map(int,input().split())
A=[]
amap=[[-1,-1] for i in range(H*W+1)]
for i in range(H):
    a=list(map(int,input().split()))
    for j in range(W):
        amap[a[j]]=[i,j]
    A.append(a)
Q=int(input())
LR=[list(map(int,input().split())) for i in range(Q)]
syo=int(H*W/D)
dp=[[0 for i in range(syo+1)] for j in range(D)] #dp[modD][/D]=(modDまでの距離)
for i in range(1,syo):
    j=0
    if i == syo-1:
        d=H*W%D
        for j in range(d):
            dp[j][i]=dp[j][i-1]+abs(amap[i*D+j][0]-amap[i*D+j-i][0])+abs(amap[i*D+j][1]-amap[i*D+j-i][1])  
    for j in range(D):
        dp[j][i]=dp[j][i-1]+abs(amap[i*D+j][0]-amap[i*D+j-i][0])+abs(amap[i*D+j][1]-amap[i*D+j-i][1])
for i in range(Q):
    L=LR[i][0]
    R=LR[i][1]
    mod=L%D
    l=int(L/D)
    r=int(R/D)
    print(dp[mod][r]-dp[mod][l])

Submission status: Wrong Answer

Solution code:
import sys
import math
import numpy as np
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, input().split()))
ns = lambda: input()
H,W,D = na()
f= [list(map(int,input().split())) for i in range(H)]
#print(f)
f = np.array(f)
Q=int(input())
'''
li = [0]*(H*W+2)
for i in range(1,D+1):
    li[i]=0
    h_=int(np.where(f==i)[0])
    w_=int(np.where(f==i)[1])
    for j in range(i+D,H*W+1,D):
        h_n=int(np.where(f==j)[0])
        w_n=int(np.where(f==j)[1])
        li[j] = li[j-D]+abs(h_ - h_n)+abs(w_ - w_n)
        h_ = h_n
        w_ = w_n
for i in range(Q):
    L,R = na()
    print(li[R]-li[L])
'''

li ={}
for i in range(H):
    for j in range(W):
        li[f[i][j]]=[i,j]
res=[0]*(H*W+1)
for i in range(1,D+1):
    for j in range(i+D,W*H+1,D):
        res[j] += abs(li[j-D][0]-li[j][0]) + abs(li[j-D][1]-li[j][1])

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