Trò chơi 3

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

24-25 HSG9 HANOI

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

Cho một bảng vuông kích thước $N \times N$ , $N$ là số lẻ. Các hàng của bảng được đánh số từ $1$ tới $N$ , từ trên xuống dưới; các cột của bảng được đánh số từ $1$ tới $N$ , từ trái sang phải. Ban đầu, các số từ $1$ đến $N^{2}$ được ghi vào bảng này lần lượt từ trái sang phải, từ trên xuống dưới. Khi $N = 5$ thì bảng vuông sẽ có dạng như sau:


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

Luật chơi: Có $Q$ lượt chơi, mỗi lượt chơi quản trò sẽ cấp cho người chơi thông tin là ba số nguyên $P, X, Y$ ( $1 \leq P \leq N^{2}$ ; $1 \leq X, Y \leq N$ ). Người chơi cần đưa số nguyên $P$ đến vị trí hàng $X$ cột $Y$ với số lần dịch bảng nhỏ nhất bằng cách sau:

Dịch các số trên hàng chứa số $P$ sang phải hoặc sang trái một ô theo vòng tròn cho đến khi số $P$ nằm trên cột $Y$ ;
Dịch các số trên cột $Y$ lên trên hoặc xuống dưới một ô theo vòng tròn cho đến khi số $P$ nằm trên hàng $X$ ;

Mỗi thao tác dịch hàng hoặc cột như trên được tính là một lần dịch bảng. Bảng đầu tiên của lượt chơi sau chính là bảng kết thúc của lượt chơi trước.

Cho thông tin của $Q$ lượt chơi. Hãy lập trình đưa ra số lần dịch bảng nhỏ nhất tìm được tương ứng với mỗi lượt.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương $N, Q$ ( $1 \leq N < 30000$ ; $1 \leq Q \leq 2000$ );
$Q$ dòng sau, mỗi dòng chứa ba số nguyên dương $P, X, Y$ ( $1 \leq P \leq N^{2}$ ; $1 \leq X, Y \leq N$ ) mô tả thông tin của một lượt chơi.

Dữ liệu ra

Gồm $Q$ dòng, dòng thứ $i$ tương ứng là số lần dịch bảng nhỏ nhất tìm được trong lượt chơi thứ $i$ .

Ràng buộc

$1 \leq N < 30000$ , $N$ là số lẻ
$1 \leq Q \leq 2000$
$1 \leq P \leq N^{2}$ ; $1 \leq X, Y \leq N$
40% số test: $N < 100$ ; $Q \leq 100$
40% số test: $N < 1500$ ; $Q \leq 1500$
20% số test: không có ràng buộc gì thêm.

Ví dụ

Input	Output	Giải thích
5 3 17 2 5 5 4 2 18 1 1	4 2 4	Lượt chơi đầu tiên: dịch số $17$ đến hàng $2$ cột $5$ cần $4$ lần dịch. Lượt chơi thứ hai: cần $2$ lần dịch bảng. Lượt chơi thứ ba: cần $4$ lần dịch bảng.

Bình luận

Không có bình luận tại thời điểm này.