Vườn thanh long xoắn ốc (Đề tự luyện HSG Tin 12 – Bài 1)
Đề bài
Vườn thanh long xoắn ốc. Vườn thanh long của thầy Sơn có $N$ hàng, $M$ cột trụ; trụ ở hàng $x$, cột $y$ là trụ $(x, y)$. Thầy bón phân cho mọi trụ theo lộ trình xoắn ốc: bắt đầu ở $(1, 1)$ quay mặt sang phải, cứ bón trụ đang đứng rồi bước tiếp; nếu trụ phía trước nằm ngoài vườn hoặc đã bón thì rẽ phải (phải → xuống → trái → lên → ...). Trụ $(1, 1)$ là trụ thứ $1$. Với mỗi câu hỏi $(x_j, y_j)$, hãy cho biết trụ đó là trụ thứ mấy được bón phân.
Dữ liệu vào: dòng đầu $N, M, Q$ ($1 \le N, M \le 10^9$, $1 \le Q \le 2 \cdot 10^5$); $Q$ dòng sau mỗi dòng một cặp $x_j, y_j$.
Kết quả: $Q$ dòng, mỗi dòng là thứ tự bón phân của trụ được hỏi.
- Subtask 1 (30%): $N \times M \le 10^6$.
- Subtask 2 (30%): mọi trụ được hỏi nằm ở rìa vườn ($x_j = 1$, $x_j = N$, $y_j = 1$ hoặc $y_j = M$).
- Subtask 3 (40%): không có ràng buộc gì thêm.
5 6 6
1 1
3 1
2 4
5 6
3 3
4 21
17
21
10
29
27Thứ tự bón phân theo từng hàng: hàng 1: $1..6$; hàng 2: $18, 19, 20, 21, 22, 7$; hàng 3: $17, 28, 29, 30, 23, 8$; hàng 4: $16, 27, 26, 25, 24, 9$; hàng 5: $15, 14, 13, 12, 11, 10$.
Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.
Nộp bài Vườn thanh long xoắn ốcLời mở đầu
"Ma trận xoắn ốc" chắc các bạn đã gặp từ hồi mới học mảng hai chiều: điền các số $1, 2, 3, \ldots$ vào bảng theo đường xoắn ốc. Bài này hỏi ngược lại: cho một ô, hỏi số điền vào ô đó là bao nhiêu. Khó khăn duy nhất là vườn có thể rộng tới $10^9 \times 10^9 = 10^{18}$ trụ, không thể điền cả bảng ra được 😅.
Nhận xét quan trọng. Lộ trình xoắn ốc thật ra là đi hết vòng ngoài cùng (rìa vườn), rồi đi hết vòng thứ hai (rìa của hình chữ nhật còn lại khi bỏ rìa ngoài), rồi vòng thứ ba... Mỗi lần bỏ một vòng, hình chữ nhật còn lại hụt đi $2$ hàng và $2$ cột. Vậy muốn biết trụ $(x, y)$ là trụ thứ mấy, ta chỉ cần biết: trụ nằm ở vòng nào, trước vòng đó có bao nhiêu trụ, và trong vòng của nó thì trụ đứng thứ mấy.
Hình 1. Vườn $5 \times 6$ của ví dụ chia thành $3$ vòng. Vòng trong cùng có thể "suy biến" chỉ còn một hàng (hoặc một cột, hoặc một trụ).
Ba cách dưới đây đi từ dễ đến khó:
Cách 1Mô phỏng cả vườn – O(N·M + Q) · 30%
Làm đúng như đề kể. Dùng mảng a có $N \cdot M$ phần tử (trụ $(x, y)$ ứng với chỉ số (x-1)*m + (y-1)), ban đầu toàn $0$ (chưa bón). Thầy Sơn đứng ở $(0, 0)$ (đánh số từ $0$ cho tiện), hướng d = 0 (sang phải). Bốn hướng theo thứ tự rẽ phải là: phải $(0, +1)$, xuống $(+1, 0)$, trái $(0, -1)$, lên $(-1, 0)$ – rẽ phải chính là d = (d + 1) % 4.
Mỗi bước: ghi số thứ tự k vào trụ đang đứng; nhìn trụ phía trước, nếu ra ngoài vườn hoặc đã có số thì rẽ phải; rồi bước tới. Điền xong $N \cdot M$ trụ thì mỗi câu hỏi chỉ việc tra mảng.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, m, q;
cin >> n >> m >> q;
vector<int> a(n * m, 0); // a[(x-1)*m + (y-1)] = thu tu bon phan
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0}; // phai, xuong, trai, len
int x = 0, y = 0, d = 0;
for (int k = 1; k <= n * m; k++) {
a[x * m + y] = k;
int nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx * m + ny] != 0) {
d = (d + 1) % 4; // ra ngoai vuon hoac tru da bon: re phai
nx = x + dx[d]; ny = y + dy[d];
}
x = nx; y = ny;
}
while (q--) {
int u, v;
cin >> u >> v;
cout << a[(u - 1) * m + (v - 1)] << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1]); q = int(data[2])
a = [0] * (n * m) # a[(x-1)*m + (y-1)] = thu tu bon phan
dx = (0, 1, 0, -1); dy = (1, 0, -1, 0) # phai, xuong, trai, len
x = 0; y = 0; d = 0
for k in range(1, n * m + 1):
a[x * m + y] = k
nx = x + dx[d]; ny = y + dy[d]
if nx < 0 or nx >= n or ny < 0 or ny >= m or a[nx * m + ny] != 0:
d = (d + 1) % 4 # ra ngoai vuon hoac tru da bon: re phai
nx = x + dx[d]; ny = y + dy[d]
x = nx; y = ny
res = []
for j in range(q):
u = int(data[3 + 2 * j]); v = int(data[4 + 2 * j])
res.append(a[(u - 1) * m + (v - 1)])
sys.stdout.write('\n'.join(map(str, res)) + '\n')
main()Cách 2Trụ ở rìa vườn: công thức theo 4 cạnh – O(1) mỗi câu · 60%
Ở subtask 2, mọi trụ được hỏi đều thuộc vòng ngoài cùng, tức là thầy Sơn bón nó trong "vòng đầu tiên" đi quanh rìa vườn. Vòng này gồm 4 cạnh, đi theo thứ tự:
| Cạnh | Các trụ (theo thứ tự đi) | Trụ $(x, y)$ là thứ |
|---|---|---|
| Trên (đi sang phải) | $(1, 1) \to (1, M)$ | $y$ |
| Phải (đi xuống) | $(2, M) \to (N, M)$ | $M + (x - 1)$ |
| Dưới (đi sang trái) | $(N, M - 1) \to (N, 1)$ | $M + (N - 1) + (M - y)$ |
| Trái (đi lên) | $(N - 1, 1) \to (2, 1)$ | $2M + (N - 2) + (N - x)$ |
Ví dụ với vườn $5 \times 6$: trụ $(3, 1)$ ở cạnh trái, là thứ $2 \cdot 6 + 3 + 2 = 17$ ✔; trụ $(5, 6)$ là góc dưới phải, thuộc cạnh phải, là thứ $6 + 4 = 10$ ✔.
if theo đúng thứ tự thầy đi (trên, phải, dưới, trái) thì trụ luôn được gán cho cạnh mà thầy đi qua nó đầu tiên – luôn đúng, kể cả các trường hợp suy biến. Đảo thứ tự (ví dụ xét cạnh trái trước cạnh phải) sẽ sai khi vườn chỉ có một cột.Kết quả có thể tới khoảng $4 \cdot 10^9$, vượt int: dùng long long. Code dưới đây gộp luôn Cách 1 cho vườn nhỏ:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
long long n, m;
int q;
cin >> n >> m >> q;
vector<long long> a;
bool small = (n * m <= 1000000);
if (small) { // Cach 1: mo phong ca vuon
a.assign(n * m, 0);
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
long long x = 0, y = 0; int d = 0;
for (long long k = 1; k <= n * m; k++) {
a[x * m + y] = k;
long long nx = x + dx[d], ny = y + dy[d];
if (nx < 0 || nx >= n || ny < 0 || ny >= m || a[nx * m + ny] != 0) {
d = (d + 1) % 4;
nx = x + dx[d]; ny = y + dy[d];
}
x = nx; y = ny;
}
}
while (q--) {
long long x, y;
cin >> x >> y;
long long k;
if (small) k = a[(x - 1) * m + (y - 1)];
else if (x == 1) k = y; // canh tren
else if (y == m) k = m + (x - 1); // canh phai
else if (x == n) k = m + (n - 1) + (m - y); // canh duoi
else k = 2 * m + (n - 2) + (n - x); // canh trai
cout << k << "\n";
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1]); q = int(data[2])
small = n * m <= 1000000
if small: # Cach 1: mo phong ca vuon
a = [0] * (n * m)
dx = (0, 1, 0, -1); dy = (1, 0, -1, 0)
x = 0; y = 0; d = 0
for k in range(1, n * m + 1):
a[x * m + y] = k
nx = x + dx[d]; ny = y + dy[d]
if nx < 0 or nx >= n or ny < 0 or ny >= m or a[nx * m + ny] != 0:
d = (d + 1) % 4
nx = x + dx[d]; ny = y + dy[d]
x = nx; y = ny
res = []
for j in range(q):
x = int(data[3 + 2 * j]); y = int(data[4 + 2 * j])
if small:
k = a[(x - 1) * m + (y - 1)]
elif x == 1:
k = y # canh tren
elif y == m:
k = m + x - 1 # canh phai
elif x == n:
k = m + n - 1 + m - y # canh duoi
else:
k = 2 * m + n - 2 + n - x # canh trai
res.append(k)
sys.stdout.write('\n'.join(map(str, res)) + '\n')
main()Cách 3Bóc vòng bằng công thức – O(1) mỗi câu · 100%
Giờ trụ $(x, y)$ có thể nằm sâu bên trong. Ta làm ba việc:
1) Trụ nằm ở vòng nào? Khoảng cách từ trụ tới bốn mép vườn là $x - 1$ (mép trên), $y - 1$ (mép trái), $N - x$ (mép dưới), $M - y$ (mép phải). Bóc một vòng thì cả bốn khoảng cách cùng giảm $1$, và trụ nằm ở rìa khi một khoảng cách bằng $0$. Vậy trụ nằm ở vòng $$L = \min(x - 1,\; y - 1,\; N - x,\; M - y)$$ (vòng ngoài cùng là vòng $0$).
2) Trước vòng $L$ có bao nhiêu trụ? Bóc $L$ vòng ngoài, phần còn lại là hình chữ nhật $r \times c$ với $r = N - 2L$, $c = M - 2L$. Các trụ đã bón trước chính là phần bị bóc đi: $$\text{before} = N \cdot M - r \cdot c.$$ Không cần vòng lặp cộng chu vi từng vòng – một phép trừ là xong!
3) Trong vòng $L$, trụ đứng thứ mấy? Đổi toạ độ sang hình chữ nhật $r \times c$: $x' = x - L$, $y' = y - L$. Trụ nằm ở rìa hình này, dùng nguyên công thức 4 cạnh của Cách 2 (với $r, c$ thay cho $N, M$) được $k$. Đáp án là $\text{before} + k$.
Kiểm tra với trụ $(4, 2)$ trong ví dụ: $L = \min(3, 1, 1, 4) = 1$; $r = 3$, $c = 4$; $\text{before} = 30 - 12 = 18$; toạ độ mới $(3, 1)$ nằm ở cạnh dưới: $k = 4 + 2 + 3 = 9$; đáp án $18 + 9 = 27$ ✔.
int nhưng $N \cdot M$ tới $10^{18}$. Nếu khai báo int n, m thì n * m bị tràn trước khi gán vào biến long long. Cách an toàn nhất: khai báo luôn n, m, x, y là long long.Các bạn nhập thử kích thước vườn và trụ cần hỏi rồi bấm "Tiếp" để xem từng bước:
Code hoàn chỉnh (đọc/ghi nhanh vì $Q$ tới $2 \cdot 10^5$):
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
long long n, m;
int q;
cin >> n >> m >> q;
string out;
while (q--) {
long long x, y;
cin >> x >> y;
long long L = min(min(x - 1, y - 1), min(n - x, m - y)); // tru nam o vong thu L (vong ngoai cung la 0)
long long before = n * m - (n - 2 * L) * (m - 2 * L); // so tru thuoc cac vong ben ngoai
long long r = n - 2 * L, c = m - 2 * L; // kich thuoc hinh chu nhat con lai
x -= L; y -= L; // toa do trong hinh chu nhat do
long long k;
if (x == 1) k = y; // canh tren: di sang phai
else if (y == c) k = c + (x - 1); // canh phai: di xuong
else if (x == r) k = c + (r - 1) + (c - y); // canh duoi: di sang trai
else k = 2 * c + (r - 2) + (r - x); // canh trai: di len
out += to_string(before + k);
out += '\n';
}
cout << out;
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); m = int(data[1]); q = int(data[2])
nm = n * m
res = []
p = 3
for _ in range(q):
x = int(data[p]); y = int(data[p + 1]); p += 2
L = min(x - 1, y - 1, n - x, m - y) # tru nam o vong thu L
r = n - 2 * L; c = m - 2 * L # hinh chu nhat con lai
before = nm - r * c # so tru thuoc cac vong ben ngoai
x -= L; y -= L
if x == 1:
k = y # canh tren
elif y == c:
k = c + x - 1 # canh phai
elif x == r:
k = c + r - 1 + c - y # canh duoi
else:
k = 2 * c + r - 2 + r - x # canh trai
res.append(before + k)
sys.stdout.write('\n'.join(map(str, res)) + '\n')
main()Bộ test chấm "bắt" những lỗi nào?
Bộ test có 30 test: 10 test subtask 1 ($N \cdot M \le 10^6$, có vườn $1 \times 10^6$, $10^6 \times 1$, $1001 \times 999$...), 9 test subtask 2 (vườn tới $10^9 \times 10^9$, chỉ hỏi trụ ở rìa, có cả vườn một hàng, một cột, hai hàng...), 11 test subtask 3 (vườn tới $10^9 \times 10^9$, nhiều câu hỏi sát tâm vườn, có vườn mà vòng trong cùng chỉ còn một hàng hoặc một cột rất dài). Mỗi test có $10^5$ – $2 \cdot 10^5$ câu hỏi.
| Cách làm | Sub 1 (30%) | Sub 2 (30%) | Sub 3 (40%) | Điểm |
|---|---|---|---|---|
| Cách 1 – mô phỏng cả vườn | Đúng | Sai/TLE | Sai/TLE | 30 |
| Cách 2 – công thức rìa vườn | Đúng | Đúng | WA | 60 |
| Cách 3 – bóc vòng bằng công thức | Đúng | Đúng | Đúng | 100 |
Sai 1 – dùng int cho $N, M$ và kết quả | Đúng | 6/9 test | 2/11 test | ≈ 57 |
| Sai 2 – bóc từng vòng bằng vòng lặp | Đúng | Đúng | 2/11 test (TLE) | ≈ 67 |
| Sai 3 – xét cạnh theo thứ tự trên → trái → dưới → phải | 8/10 test | 8/9 test | 9/11 test | ≈ 83 |
Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 10/10 test subtask 1 và trượt mọi test còn lại (vườn quá lớn, không thể lưu cả bảng); Cách 2 đúng hết hai subtask đầu và sai cả 11 test subtask 3; Cách 3 đúng 30/30 test, test lâu nhất khoảng 0,03 giây. Cách "bóc từng vòng" chỉ qua được 2 test vườn rất hẹp ($10^9 \times 3$, $10^9 \times 4$), còn lại đều chạy quá 3 giây. Lỗi đảo thứ tự xét cạnh chỉ lộ ra ở những vườn có vòng trong cùng là một cột – ví dụ của đề không có trường hợp này nên các bạn phải tự cẩn thận.
Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇
- 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