Trò Chơi (HSG9 Hà Nội 2025 – Bài 4)
Đề bài
TRÒ CHƠI
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ư Hình 1.
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 | 5 |
| 2 | 6 | 7 | 8 | 9 | 10 |
| 3 | 11 | 12 | 13 | 14 | 15 |
| 4 | 16 | 17 | 18 | 19 | 20 |
| 5 | 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 \le P \le N^2;\ 1 \le X, Y \le 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.
Ví dụ: Xét bảng vuông $5 \times 5$, cần dịch số $17$ trên bảng ban đầu đến vị trí hàng $2$ cột $5$. Để số lần dịch bảng nhỏ nhất thực hiện như Hình 2.
| 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 |
| 1 | 2 | 3 | 4 | 5 |
| 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 |
| 17 | 18 | 19 | 20 | 16 |
| 21 | 22 | 23 | 24 | 25 |
| 1 | 2 | 3 | 4 | 5 |
| 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 |
| 18 | 19 | 20 | 16 | 17 |
| 21 | 22 | 23 | 24 | 25 |
| 1 | 2 | 3 | 4 | 10 |
| 6 | 7 | 8 | 9 | 15 |
| 11 | 12 | 13 | 14 | 17 |
| 18 | 19 | 20 | 16 | 25 |
| 21 | 22 | 23 | 24 | 5 |
| 1 | 2 | 3 | 4 | 15 |
| 6 | 7 | 8 | 9 | 17 |
| 11 | 12 | 13 | 14 | 25 |
| 18 | 19 | 20 | 16 | 5 |
| 21 | 22 | 23 | 24 | 10 |
Yêu cầu: 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 từ file văn bản TROCHOI.INP:
- Dòng đầu tiên chứa hai số nguyên dương $N, Q$ $(1 \le N \lt 30000;\ 1 \le Q \le 2000)$;
- $Q$ dòng sau, mỗi dòng chứa ba số nguyên dương $P, X, Y$ $(1 \le P \le N^2;\ 1 \le X, Y \le N)$ mô tả thông tin của một lượt chơi.
Kết quả ghi ra file văn bản TROCHOI.OUT: 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:
- Có $40\%$ số test ứng với $40\%$ số điểm của bài thoả mãn: $N \lt 100;\ Q \le 100$;
- $40\%$ số test khác ứng với $40\%$ số điểm của bài thoả mãn: $N \lt 1500;\ Q \le 1500$;
- $20\%$ số test còn lại ứng với $20\%$ số điểm không có ràng buộc gì thêm.
Lưu ý: đề thi gốc đọc/ghi file TROCHOI.INP / TROCHOI.OUT; trên CLUE OJ thì đọc từ bàn phím và in ra màn hình (code bên dưới có đoạn if(fopen(...)) nên nộp kiểu nào cũng chạy đúng).
5 3
17 2 5
5 4 2
18 1 14
2
4Giải thích (theo đề):
- Lượt chơi đầu tiên được mô tả bởi Hình 2;
- Lượt chơi thứ hai thực hiện 2 lần dịch bảng như sau:
| 1 | 2 | 3 | 4 | 15 |
| 6 | 7 | 8 | 9 | 17 |
| 11 | 12 | 13 | 14 | 25 |
| 18 | 19 | 20 | 16 | 5 |
| 21 | 22 | 23 | 24 | 10 |
| 1 | 2 | 3 | 4 | 15 |
| 6 | 7 | 8 | 9 | 17 |
| 11 | 12 | 13 | 14 | 25 |
| 5 | 18 | 19 | 20 | 16 |
| 21 | 22 | 23 | 24 | 10 |
| 1 | 2 | 3 | 4 | 15 |
| 6 | 7 | 8 | 9 | 17 |
| 11 | 12 | 13 | 14 | 25 |
| 16 | 5 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 10 |
- Lượt chơi thứ ba thực hiện 2 lần dịch hàng 4 sang trái và 2 lần dịch cột 1 xuống dưới.
Lời mở đầu
Đây là bài 4 trong đề thi học sinh giỏi Tin học lớp 9 thành phố Hà Nội năm 2025. Đề nhìn thì dài, nhiều hình nhưng thực chất là một bài mô phỏng kết hợp vài nhận xét khá thú vị. Mình viết lời giải theo đúng 3 subtask của đề: từ dịch bảng trâu, đến dịch nhanh bằng chia lấy dư, rồi cuối cùng là bỏ hẳn cái bảng đi, chỉ theo dõi toạ độ. Hy vọng mang đến được giá trị cho các bạn 😇.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:
Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.
Nộp bài trên CLUE OJMình giải thích thêm ví dụ để bạn nào chưa hiểu đề sẽ hiểu rõ. Mỗi lượt chơi luôn gồm 2 giai đoạn theo đúng thứ tự:
- Dịch hàng đang chứa $P$ (sang trái hoặc sang phải, vòng tròn) cho tới khi $P$ nằm ở cột $Y$. "Vòng tròn" nghĩa là dịch sang trái thì số ở cột $1$ sẽ quay vòng về cột $N$, dịch sang phải thì số ở cột $N$ quay về cột $1$.
- Dịch cột $Y$ (lên hoặc xuống, vòng tròn) cho tới khi $P$ nằm ở hàng $X$.
Lượt 1: số $17$ đang ở hàng $4$ cột $2$, cần tới hàng $2$ cột $5$. Trên hàng, đi sang trái: cột $2 \to 1 \to 5$ mất 2 lần; đi sang phải: $2 \to 3 \to 4 \to 5$ mất 3 lần ⇒ chọn sang trái. Trên cột $5$, đi lên: hàng $4 \to 3 \to 2$ mất 2 lần; đi xuống: $4 \to 5 \to 1 \to 2$ mất 3 lần ⇒ chọn lên trên. Tổng $2 + 2 = 4$.
Lượt 2 dùng tiếp bảng sau lượt 1: số $5$ đang ở hàng $4$ cột $5$, cần tới hàng $4$ cột $2$: dịch phải $2$ lần là xong ($5 \to 1 \to 2$), cột thì đã đúng hàng rồi nên không cần dịch ⇒ $2$. Lượt 3: số $18$ ở hàng $4$ cột $3$ → dịch trái $2$ lần về cột $1$, rồi trên cột $1$ đi từ hàng $4$ xuống $5 \to 1$ mất $2$ lần ⇒ $4$.
Lộ trình lời giải, bấm vào từng phần để nhảy tới:
Subtask 1Dịch bảng trâu – O(Q·N²)
Ở subtask này $N \lt 100$, $Q \le 100$ nên ta cứ lưu nguyên cái bảng và làm đúng như đề. Trước hết là một nhận xét quan trọng:
Thêm nữa, việc chọn dịch trái hay phải (trên hàng) và việc chọn dịch lên hay xuống (trên cột) có thể coi là hai thao tác độc lập: dịch hàng xong thì $P$ chắc chắn nằm ở cột $Y$, còn đang ở hàng nào thì vẫn là hàng cũ, nên số lần dịch cột ít nhất không phụ thuộc vào việc lúc nãy ta dịch hàng theo hướng nào. Và tất nhiên cũng không phụ thuộc vào các lượt trước dịch như thế nào – các lượt trước chỉ quyết định $P$ đang nằm ở đâu thôi.
Mình viết 2 hàm tính số lần dịch:
left(val, tag): số lần dịch sang trái (hoặc lên trên nếu là cột) để đưa vị trí $val$ về vị trí $tag$. Mỗi lần dịch trái, vị trí giảm đi $1$ (từ $1$ quay vòng về $N$). Nếu $val \gt tag$ thì cần $val - tag$ lần; nếu $val \le tag$ thì phải đi về $1$ rồi vòng qua $N$: cần $val + (N - tag)$ lần.right(val, tag): số lần dịch sang phải (hoặc xuống dưới). Nếu $val \le tag$ thì cần $tag - val$ lần; ngược lại cần $N - val + tag$ lần.
Để ý khi $val = tag$ thì left trả về $N$ còn right trả về $0$, nên code (chọn trái chỉ khi mn_l < mn_r) sẽ chọn "dịch phải 0 lần" – đúng là không dịch gì cả.
Với mỗi lượt chơi, ta tìm xem số $P$ hiện đang nằm ở ô $(u, v)$ nào trên bảng, tính hướng dịch tốt nhất trên hàng $u$, rồi thực hiện dịch trâu từng lần một (mỗi lần dịch hàng là dời cả $N$ số). Sau đó $P$ đã ở cột $Y$, ta làm tương tự với cột $Y$. Các bạn nhập thử vài lượt chơi vào khung minh hoạ dưới đây để xem từng lần dịch bảng nha:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int n, q, p, x, y;
int a[105][105];
int left(int val, int tag){
if (val <= tag) return val + (n - tag);
else return abs(tag - val);
}
int right(int val, int tag){
if (val <= tag) return abs(tag - val);
else return n - val + tag;
}
int main(){
if(fopen("trochoi.inp", "r")){
freopen("trochoi.inp", "r", stdin);
freopen("trochoi.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++) a[i][j] = (i - 1) * n + j;
}
for (int i = 1; i <= q; i++){
cin >> p >> x >> y;
int res = 0;
bool ok = 0;
for (int u = 1; u <= n; u++){
for (int v = 1; v <= n; v++){
if (a[u][v] == p){
int mn_l = left(v, y);
int mn_r = right(v, y);
if (mn_l < mn_r){
res += mn_l;
while (mn_l--){
int g = a[u][1];
for (int j = 1; j < n; j++) a[u][j] = a[u][j + 1];
a[u][n] = g;
}
}
else{
res += mn_r;
while (mn_r--){
int g = a[u][n];
for (int j = n; j > 1; j--) a[u][j] = a[u][j - 1];
a[u][1] = g;
}
}
v = y;
mn_l = left(u, x);
mn_r = right(u, x);
if (mn_l < mn_r){
res += mn_l;
while (mn_l--){
int g = a[1][v];
for (int j = 1; j < n; j++) a[j][v] = a[j + 1][v];
a[n][v] = g;
}
}
else{
res += mn_r;
while (mn_r--){
int g = a[n][v];
for (int j = n; j > 1; j--) a[j][v] = a[j - 1][v];
a[1][v] = g;
}
}
ok = 1;
cout << res << endl;
break;
}
}
if (ok) break;
}
}
}import sys, os
def left(val, tag):
# số lần dịch sang TRÁI để đi từ vị trí val tới vị trí tag
if val <= tag:
return val + (n - tag)
return abs(tag - val)
def right(val, tag):
# số lần dịch sang PHẢI để đi từ vị trí val tới vị trí tag
if val <= tag:
return abs(tag - val)
return n - val + tag
if os.path.exists('trochoi.inp'):
sys.stdin = open('trochoi.inp')
sys.stdout = open('trochoi.out', 'w')
data = sys.stdin.read().split()
n, q = int(data[0]), int(data[1])
a = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, n + 1):
a[i][j] = (i - 1) * n + j
out = []
pos = 2
for _ in range(q):
p, x, y = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])
pos += 3
res = 0
found = False
for u in range(1, n + 1):
for v in range(1, n + 1):
if a[u][v] == p:
mn_l, mn_r = left(v, y), right(v, y)
if mn_l < mn_r:
res += mn_l
for _t in range(mn_l): # dịch hàng u sang trái 1 ô
g = a[u][1]
for j in range(1, n):
a[u][j] = a[u][j + 1]
a[u][n] = g
else:
res += mn_r
for _t in range(mn_r): # dịch hàng u sang phải 1 ô
g = a[u][n]
for j in range(n, 1, -1):
a[u][j] = a[u][j - 1]
a[u][1] = g
v = y
mn_l, mn_r = left(u, x), right(u, x)
if mn_l < mn_r:
res += mn_l
for _t in range(mn_l): # dịch cột v lên trên 1 ô
g = a[1][v]
for j in range(1, n):
a[j][v] = a[j + 1][v]
a[n][v] = g
else:
res += mn_r
for _t in range(mn_r): # dịch cột v xuống dưới 1 ô
g = a[n][v]
for j in range(n, 1, -1):
a[j][v] = a[j - 1][v]
a[1][v] = g
found = True
out.append(str(res))
break
if found:
break
print('\n'.join(out))
sys.stdout.flush()Giải thích 1 số chỗ trong code ở trên:
- Dịch hàng $u$ sang trái 1 ô: cất
g = a[u][1], dờia[u][j] = a[u][j + 1]với $j$ từ $1$ tới $N - 1$, rồi đặta[u][n] = g(số ở đầu quay vòng về cuối). Dịch sang phải thì ngược lại: cấta[u][n], dời từ cuối về đầu, rồi đặt vàoa[u][1]. Dịch cột lên/xuống cũng y hệt, chỉ đổi chỉ số hàng thành chỉ số cột. while (mn_l--): lặp đúngmn_llần (kiểm tra giá trị hiện tại khác $0$ rồi mới giảm).- Sau khi dịch hàng xong, $P$ chắc chắn nằm ở cột $Y$ nên mình gán luôn
v = y, còn hàng vẫn là $u$. - Biến
okdùng để thoát cả 2 vòng lặp tìm kiếm khi đã xử lý xong số $P$.
Đánh giá độ phức tạp của cách làm này:
- Không gian: lưu cả bảng $N \times N$: $O(N^2)$.
- Thời gian: mỗi lượt, tìm số $P$ tốn $O(N^2)$; dịch hàng/cột tối đa khoảng $N/2$ lần, mỗi lần dời $N$ số nên cũng $O(N^2)$. Tổng là $O(Q \cdot N^2)$. Với $N \lt 100$, $Q \le 100$ thì chỉ cỡ $10^6$ phép tính.
Subtask 2Dịch nhanh bằng chia lấy dư – O(Q·N²)
Thay vì thực hiện xoay trâu từng lần một, ta nhận thấy rằng nếu ta biết hướng xoay và số lượt xoay nhỏ nhất thì ta luôn suy ra được vị trí của một ô sau khi xoay. Chép hàng (hoặc cột) cũ ra mảng old, rồi tính luôn hàng mới chỉ với một vòng lặp:
- Dịch trái $k$ ô: ô thứ $i$ của hàng mới nhận số ở ô thứ $i + k$ của hàng cũ (vòng tròn), tức là
a[u][i] = old[(i + k - 1) % n + 1]. - Dịch phải $k$ ô: ô thứ $i$ nhận số ở ô thứ $i - k$ của hàng cũ, tức là
a[u][i] = old[(i - k - 1 + n * n) % n + 1].
% cho kết quả từ $0$ đến $N - 1$. Nên ta trừ $1$ để đưa về hệ đếm từ $0$, lấy dư, rồi cộng $1$ lại. Còn i - k - 1 có thể âm, mà trong C++ phép % với số âm cho ra số âm (ví dụ -2 % 5 = -2), nên ta cộng thêm một bội của $N$ (ở đây là $N \cdot N$) cho chắc chắn không âm. Vì $k \lt N$ nên thật ra cộng $N$ là đủ rồi.Ví dụ hàng $4$ của bảng ban đầu khi $N = 5$ là 16 17 18 19 20, dịch trái $k = 2$: ô $1$ nhận old[(1 + 2 - 1) % 5 + 1] = old[3] = 18, ô $4$ nhận old[(4 + 1) % 5 + 1] = old[1] = 16… ra đúng 18 19 20 16 17 như Hình 2.
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int n, q, p, x, y;
int a[1505][1505];
int old[1505];
int left(int val, int tag){
if (val <= tag) return val + (n - tag);
else return abs(tag - val);
}
int right(int val, int tag){
if (val <= tag) return abs(tag - val);
else return n - val + tag;
}
int main(){
if(fopen("trochoi.inp", "r")){
freopen("trochoi.inp", "r", stdin);
freopen("trochoi.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++) a[i][j] = (i - 1) * n + j;
}
for (int i = 1; i <= q; i++){
cin >> p >> x >> y;
int res = 0;
bool ok = 0;
for (int u = 1; u <= n; u++){
for (int v = 1; v <= n; v++){
if (a[u][v] == p){
int mn_l = left(v, y);
int mn_r = right(v, y);
if (mn_l < mn_r){
res += mn_l;
for (int i = 1; i <= n; i++) old[i] = a[u][i];
for (int i = 1; i <= n; i++) a[u][i] = old[(i + mn_l - 1) % n + 1];
}
else{
res += mn_r;
for (int i = 1; i <= n; i++) old[i] = a[u][i];
for (int i = 1; i <= n; i++) a[u][i] = old[(i - mn_r - 1 + n * n) % n + 1];
}
v = y;
mn_l = left(u, x);
mn_r = right(u, x);
if (mn_l < mn_r){
res += mn_l;
for (int i = 1; i <= n; i++) old[i] = a[i][v];
for (int i = 1; i <= n; i++) a[i][v] = old[(i + mn_l - 1) % n + 1];
}
else{
res += mn_r;
for (int i = 1; i <= n; i++) old[i] = a[i][v];
for (int i = 1; i <= n; i++) a[i][v] = old[(i - mn_r - 1 + n * n) % n + 1];
}
ok = 1;
cout << res << endl;
break;
}
}
if (ok) break;
}
}
}import sys, os
def left(val, tag):
if val <= tag:
return val + (n - tag)
return abs(tag - val)
def right(val, tag):
if val <= tag:
return abs(tag - val)
return n - val + tag
if os.path.exists('trochoi.inp'):
sys.stdin = open('trochoi.inp')
sys.stdout = open('trochoi.out', 'w')
data = sys.stdin.read().split()
n, q = int(data[0]), int(data[1])
# a[u][v] với u, v tính từ 1 (cột 0, hàng 0 bỏ trống)
a = [[0] * (n + 1)] + [[0] + [(i - 1) * n + j for j in range(1, n + 1)] for i in range(1, n + 1)]
out = []
pos = 2
for _ in range(q):
p, x, y = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])
pos += 3
res = 0
for u in range(1, n + 1):
if p in a[u]: # tìm hàng chứa p
v = a[u].index(p)
break
mn_l, mn_r = left(v, y), right(v, y)
old = a[u][:]
if mn_l < mn_r:
res += mn_l
for i in range(1, n + 1):
a[u][i] = old[(i + mn_l - 1) % n + 1]
else:
res += mn_r
for i in range(1, n + 1):
a[u][i] = old[(i - mn_r - 1) % n + 1]
v = y
mn_l, mn_r = left(u, x), right(u, x)
old = [a[i][v] for i in range(n + 1)]
if mn_l < mn_r:
res += mn_l
for i in range(1, n + 1):
a[i][v] = old[(i + mn_l - 1) % n + 1]
else:
res += mn_r
for i in range(1, n + 1):
a[i][v] = old[(i - mn_r - 1) % n + 1]
out.append(str(res))
print('\n'.join(out))
sys.stdout.flush()Đánh giá độ phức tạp của cách làm này:
- Không gian: vẫn lưu cả bảng: $O(N^2)$ (bảng $1505 \times 1505$ số
intkhoảng 9 MB). - Thời gian: phần dịch bảng giờ chỉ còn $O(N)$ mỗi lượt. Nhưng phần tìm số $P$ trên bảng vẫn tốn $O(N^2)$ mỗi lượt, nên tổng vẫn là $O(Q \cdot N^2)$ – chỉ nhanh hơn subtask 1 ở hằng số.
hang[P], cot[P] (kích thước $N^2$) và cập nhật lại chúng mỗi khi dịch một hàng/cột (mất $O(N)$) – khi đó mỗi lượt chỉ còn $O(N)$. Tuy nhiên ý tưởng ở subtask 3 dưới đây còn gọn hơn và ăn trọn $100\%$ luôn.Subtask 3Bỏ cái bảng đi, chỉ truy vết toạ độ – O(Q²)
Ở subtask cuối $N$ lên tới gần $30000$: bảng có tới $9 \cdot 10^8$ ô, không thể lưu nổi. Nhưng $Q \le 2000$ lại khá nhỏ. Hướng đi của chúng ta sẽ thay đổi một chút: không lưu bảng nữa, chỉ theo dõi toạ độ của đúng số $P$ cần hỏi.
Với mỗi ván $i$, ta gọi $(idx, idy)$ là toạ độ của số $P$ ngay trước ván chơi thứ $i$. Ban đầu (trước ván $1$) số $P$ nằm ở hàng $\left\lfloor \dfrac{P - 1}{N} \right\rfloor + 1$, cột $(P - 1) \bmod N + 1$. Ta nhận thấy rằng toạ độ của $P$ chỉ thay đổi khi có một ván $j$ nào đó dịch đúng hàng $idx$ hoặc đúng cột $idy$ đang chứa nó. Các số khác bị dịch đi đâu thì kệ chúng, ta không quan tâm!
choose_x[j] và độ dời cột chg_x[j] (âm = dịch trái, dương = dịch phải); cột đã dịch choose_y[j] và độ dời hàng chg_y[j] (âm = dịch lên, dương = dịch xuống). Đến ván $i$, ta "chơi lại" các ván $j = 1, 2, \ldots, i - 1$ chỉ với toạ độ của $P$:
- Nếu
choose_x[j] == idx(hàng chứa $P$ bị dịch) thì $idy \leftarrow (idy - 1 + chg\_x[j]) \bmod N + 1$. - Sau đó nếu
choose_y[j] == idy(cột chứa $P$ bị dịch) thì $idx \leftarrow (idx - 1 + chg\_y[j]) \bmod N + 1$.
Phải xét hàng trước rồi mới tới cột đúng như thứ tự trong một ván chơi, vì có thể việc dịch hàng ở ván $j$ đẩy $P$ vào đúng cột sắp bị dịch của ván $j$. Biết toạ độ của số đó trước ván $i$ rồi thì ta dễ dàng tính được số lượt xoay, hướng xoay trên hàng và cột để đưa số tới đúng vị trí mục tiêu bằng 2 hàm left, right như cũ. Lưu ý là phải lưu lại số lượt xoay cần thực hiện, hướng xoay trên hàng và cột, địa chỉ hàng và cột thực hiện xoay tại ván $i$ để có dữ liệu cho việc tìm toạ độ ở những ván tiếp theo: hàng bị dịch ở ván $i$ chính là $idx$, còn cột bị dịch chính là $Y$.
Các bạn xem khung minh hoạ dưới đây: bảng chỉ để vẽ cho dễ nhìn thôi, các ô đều trống – thuật toán chỉ cần biết số $P$ đang ở đâu và nhật ký các ván trước:
Source code để các bạn tham khảo nếu làm theo hướng này:
#include<bits/stdc++.h>
using namespace std;
int n, q, p, x, y;
int choose_x[2005];
int choose_y[2005];
int chg_x[2005];
int chg_y[2005];
int left(int val, int tag){
if (val <= tag) return val + (n - tag);
else return abs(tag - val);
}
int right(int val, int tag){
if (val <= tag) return abs(tag - val);
else return n - val + tag;
}
int main(){
if(fopen("trochoi.inp", "r")){
freopen("trochoi.inp", "r", stdin);
freopen("trochoi.out", "w", stdout);
}
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= q; i++){
cin >> p >> x >> y;
int idx = (p - 1) / n + 1;
int idy = (p - 1) % n + 1;
for (int j = 1; j < i; j++){
if (choose_x[j] == idx){
idy--;
idy += chg_x[j];
idy += n * n;
idy %= n;
idy++;
}
if (choose_y[j] == idy){
idx--;
idx += chg_y[j];
idx += n * n;
idx %= n;
idx++;
}
}
choose_x[i] = idx;
choose_y[i] = y;
int mn_x_left = left(idy, y);
int mn_x_right = right(idy, y);
if (mn_x_left < mn_x_right) chg_x[i] += -mn_x_left;
else chg_x[i] += mn_x_right;
int mn_y_left = left(idx, x);
int mn_y_right = right(idx, x);
if (mn_y_left < mn_y_right) chg_y[i] += -mn_y_left;
else chg_y[i] += mn_y_right;
cout << min(mn_y_left, mn_y_right) + min(mn_x_left, mn_x_right) << '\n';
}
}import sys, os
def left(val, tag):
if val <= tag:
return val + (n - tag)
return abs(tag - val)
def right(val, tag):
if val <= tag:
return abs(tag - val)
return n - val + tag
if os.path.exists('trochoi.inp'):
sys.stdin = open('trochoi.inp')
sys.stdout = open('trochoi.out', 'w')
data = sys.stdin.read().split()
n, q = int(data[0]), int(data[1])
choose_x = [0] * (q + 1) # hàng đã dịch ở lượt j
choose_y = [0] * (q + 1) # cột đã dịch ở lượt j
chg_x = [0] * (q + 1) # độ dời cột khi dịch hàng (âm = sang trái)
chg_y = [0] * (q + 1) # độ dời hàng khi dịch cột (âm = lên trên)
out = []
pos = 2
for i in range(1, q + 1):
p, x, y = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])
pos += 3
idx = (p - 1) // n + 1
idy = (p - 1) % n + 1
for j in range(1, i):
if choose_x[j] == idx:
idy = (idy - 1 + chg_x[j]) % n + 1
if choose_y[j] == idy:
idx = (idx - 1 + chg_y[j]) % n + 1
choose_x[i] = idx
choose_y[i] = y
mn_x_left, mn_x_right = left(idy, y), right(idy, y)
chg_x[i] = -mn_x_left if mn_x_left < mn_x_right else mn_x_right
mn_y_left, mn_y_right = left(idx, x), right(idx, x)
chg_y[i] = -mn_y_left if mn_y_left < mn_y_right else mn_y_right
out.append(str(min(mn_y_left, mn_y_right) + min(mn_x_left, mn_x_right)))
print('\n'.join(out))
sys.stdout.flush()Giải thích 1 số chỗ trong code ở trên:
- Đoạn
idy--; idy += chg_x[j]; idy += n * n; idy %= n; idy++;chính là công thức $idy \leftarrow (idy - 1 + chg\_x[j]) \bmod N + 1$ viết tách ra từng bước. Cộng thêmn * nđể số không bị âm trước khi lấy dư (vìchg_x[j]có thể âm). $N \lt 30000$ nên $N^2 \lt 9 \cdot 10^8$ vẫn vừa kiểuint. chg_x[i] += -mn_x_left: dịch trái thì cột giảm nên lưu số âm, dịch phải thì lưu số dương. Mảng toàn cục ban đầu bằng $0$ nên+=ở đây cũng như gán.- Tên biến hơi dễ nhầm các bạn để ý nha:
mn_x_left/rightlà số lần dịch trên hàng (làm thay đổi cột $idy$), cònmn_y_left/rightlà số lần dịch trên cột (làm thay đổi hàng $idx$).
Đánh giá độ phức tạp của cách làm này:
- Không gian: chỉ 4 mảng nhật ký độ dài $Q$: $O(Q)$. Không còn phụ thuộc vào $N$ nữa.
- Thời gian: ván thứ $i$ phải chơi lại $i - 1$ ván trước, mỗi ván $O(1)$: tổng $1 + 2 + \ldots + (Q - 1) = O(Q^2)$. Với $Q = 2000$ chỉ khoảng $2 \cdot 10^6$ phép tính.
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét