Cờ ca-rô (Đề tự luyện HSG Tin 9 – Bài 1)
Đề bài
Cờ ca-rô. Bàn cờ $N \times N$, thầy Sơn cầm quân X đi trước (các nước lẻ), học trò cầm quân O (các nước chẵn). Một bên thắng khi có từ 5 quân trở lên của mình liền nhau trên một hàng, một cột hoặc một đường chéo (cả hai hướng chéo), không có luật chặn hai đầu. Cho $K$ nước đi theo thứ tự (các ô khác nhau), hãy tìm số thứ tự $t$ của nước đi mà ngay sau nước đó lần đầu tiên có một bên thắng; nếu không ai thắng in $0$.
Dữ liệu vào: dòng 1 gồm $N, K$ $(1 \le N \le 5000;\ 1 \le K \le \min(N^2, 3 \cdot 10^5))$; $K$ dòng sau, mỗi dòng là ô $(r_t, c_t)$ của nước thứ $t$.
Kết quả: một số nguyên $t$, hoặc $0$.
- Subtask 1 (30%): $N \le 15$.
- Subtask 2 (30%): $N \le 300$.
- Subtask 3 (40%): không ràng buộc thêm.
7 12
4 4
3 4
4 3
4 5
4 2
5 6
4 1
6 7
5 4
2 3
5 5
1 210Sau nước 7, thầy có 4 quân X liền nhau ở hàng 4 (chưa đủ 5). Sau nước 10, năm quân O ở $(2,3), (3,4), (4,5), (5,6), (6,7)$ nằm liền nhau trên một đường chéo: học trò thắng. Nước 11, 12 đánh sau khi đã có người thắng.
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 Cờ ca-rôLời mở đầu
Đây là bài mô phỏng: ta đặt lần lượt từng quân lên bàn cờ (một mảng hai chiều), sau mỗi nước thì kiểm tra xem đã có 5 quân liền nhau chưa. Cái khó duy nhất là kiểm tra sao cho nhanh, vì có tới $3 \cdot 10^5$ nước đi trên bàn cờ $5000 \times 5000$.
Nhận xét quan trọng: trước nước thứ $t$ chưa ai thắng (nếu không ta đã dừng sớm hơn). Vậy nếu sau nước $t$ có một dãy 5 quân liền nhau thì dãy đó bắt buộc phải chứa quân vừa đánh — mọi dãy khác đã có từ trước rồi. Do đó chỉ cần nhìn quanh ô vừa đánh theo 4 hướng: ngang, dọc, chéo chính, chéo phụ.
Hình 1. Dãy thắng mới (nếu có) phải đi qua ô vừa đánh, nằm trên một trong 4 đường thẳng.
Cách 1Sau mỗi nước, quét cả bàn cờ – O(K · N²) · 30%
Cách tự nhiên nhất: sau mỗi nước đi, duyệt mọi ô $(i, j)$ có quân, thử 4 hướng xem 5 ô liên tiếp bắt đầu từ $(i, j)$ có cùng loại quân không. Nếu có thì in $t$. Mỗi lần quét mất khoảng $4 \cdot 5 \cdot N^2$ phép so sánh; với $N \le 15$ thì có tối đa $225$ nước, tổng cộng chưa tới $10^6$ phép — rất nhanh.
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<vector<int>> b; // 0: trong, 1: X, 2: O
// kiem tra tren ban co co 5 quan cung loai lien tiep hay khong
bool coNguoiThang() {
int dr[4] = {0, 1, 1, 1}, dc[4] = {1, 0, 1, -1};
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (b[i][j] == 0) continue;
for (int d = 0; d < 4; d++) { // thu 5 o bat dau tu (i, j) theo huong d
int dem = 0;
for (int e = 0; e < 5; e++) {
int x = i + e * dr[d], y = j + e * dc[d];
if (x < 1 || x > n || y < 1 || y > n || b[x][y] != b[i][j]) break;
dem++;
}
if (dem == 5) return true;
}
}
return false;
}
int main() {
cin >> n >> k;
b.assign(n + 2, vector<int>(n + 2, 0));
for (int t = 1; t <= k; t++) {
int r, c;
cin >> r >> c;
b[r][c] = (t % 2 == 1) ? 1 : 2;
if (coNguoiThang()) { // quet lai ca ban co sau moi nuoc
cout << t << "\n";
return 0;
}
}
cout << 0 << "\n";
return 0;
}import sys
def co_nguoi_thang(b, n):
# kiem tra tren ban co co 5 quan cung loai lien tiep hay khong
for i in range(1, n + 1):
for j in range(1, n + 1):
if b[i][j] == 0:
continue
for dr, dc in ((0, 1), (1, 0), (1, 1), (1, -1)): # thu 5 o bat dau tu (i, j)
dem = 0
for e in range(5):
x = i + e * dr; y = j + e * dc
if x < 1 or x > n or y < 1 or y > n or b[x][y] != b[i][j]:
break
dem += 1
if dem == 5:
return True
return False
def main():
data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
b = [[0] * (n + 2) for _ in range(n + 2)]
for t in range(1, k + 1):
r = int(data[2 * t]); c = int(data[2 * t + 1])
b[r][c] = 1 if t % 2 == 1 else 2
if co_nguoi_thang(b, n): # quet lai ca ban co sau moi nuoc
print(t)
return
print(0)
main()Cách 2Chỉ quét 4 đường thẳng qua ô vừa đánh – O(K · N) · 60%
Theo nhận xét ở Lời mở đầu, dãy thắng mới phải chứa quân vừa đánh, nên chỉ cần xét 4 đường thẳng đi qua ô đó. Với mỗi đường, ta lùi về đầu đường (sát mép bàn cờ) rồi đi đến cuối đường, đếm độ dài dãy liên tiếp quân $q$ dài nhất (gặp ô khác loại thì đếm lại từ $0$). Mỗi đường dài không quá $N$ ô, nên mỗi nước mất $O(N)$.
#include <bits/stdc++.h>
using namespace std;
int n, k;
vector<vector<char>> b;
// dem day quan q dai nhat tren duong thang di qua (r, c) theo huong (dr, dc), duyet tu dau duong den cuoi duong
int dayDaiNhat(int r, int c, int dr, int dc, char q) {
while (r - dr >= 1 && r - dr <= n && c - dc >= 1 && c - dc <= n) { r -= dr; c -= dc; } // lui ve dau duong
int best = 0, dem = 0;
while (r >= 1 && r <= n && c >= 1 && c <= n) {
if (b[r][c] == q) dem++; else dem = 0;
best = max(best, dem);
r += dr; c += dc;
}
return best;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
b.assign(n + 2, vector<char>(n + 2, 0));
int dr[4] = {0, 1, 1, 1}, dc[4] = {1, 0, 1, -1};
for (int t = 1; t <= k; t++) {
int r, c;
cin >> r >> c;
char q = (t % 2 == 1) ? 1 : 2;
b[r][c] = q;
for (int d = 0; d < 4; d++) // chi xet 4 duong thang di qua o vua danh
if (dayDaiNhat(r, c, dr[d], dc[d], q) >= 5) {
cout << t << "\n";
return 0;
}
}
cout << 0 << "\n";
return 0;
}import sys
def day_dai_nhat(b, n, r, c, dr, dc, q):
# dem day quan q dai nhat tren duong thang di qua (r, c) theo huong (dr, dc)
while 1 <= r - dr <= n and 1 <= c - dc <= n: # lui ve dau duong
r -= dr; c -= dc
best = 0; dem = 0
while 1 <= r <= n and 1 <= c <= n:
if b[r][c] == q:
dem += 1
if dem > best: best = dem
else:
dem = 0
r += dr; c += dc
return best
def main():
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
b = [bytearray(n + 2) for _ in range(n + 2)]
for t in range(1, k + 1):
r = int(data[2 * t]); c = int(data[2 * t + 1])
q = 1 if t % 2 == 1 else 2
b[r][c] = q
for dr, dc in ((0, 1), (1, 0), (1, 1), (1, -1)): # chi xet 4 duong thang di qua o vua danh
if day_dai_nhat(b, n, r, c, dr, dc, q) >= 5:
print(t)
return
print(0)
main()Cách 3Đếm quân liền nhau về hai phía của ô vừa đánh – O(K) · 100%
Trên mỗi hướng $(dr, dc)$, xuất phát từ ô vừa đánh $(r, c)$:
- đi tới $(r + dr, c + dc), (r + 2dr, c + 2dc), \dots$ chừng nào còn gặp quân cùng loại thì đếm thêm;
- làm y hệt theo chiều ngược lại $(r - dr, c - dc), \dots$;
- cộng thêm $1$ cho chính quân vừa đánh. Nếu tổng $\ge 5$ thì bên vừa đi thắng, đáp án là $t$.
Vì trước đó chưa ai thắng nên mỗi phía chỉ đếm được tối đa $4$ quân (nếu đếm được $5$ quân ở một phía thì đã thắng từ trước). Vậy mỗi nước tốn không quá $4 \cdot 2 \cdot 5 = 40$ lần nhìn ô: tổng cộng $O(K)$.
Mẹo viền: khai báo bàn cờ rộng thêm 1 ô ở mỗi phía (chỉ số $0$ và $N + 1$), các ô viền luôn trống. Khi đi ra mép thì gặp ô viền và tự dừng, không cần kiểm tra $1 \le x \le N$. Code chuẩn lưu bàn cờ trong một mảng một chiều b[x * W + y] với $W = N + 2$ cho gọn bộ nhớ ($5002^2 \approx 2{,}5 \cdot 10^7$ byte).
Code chuẩn (C++ và Python) chỉ khác Cách 2 ở phần kiểm tra:
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
int W = n + 2; // them 1 o vien moi phia de khong di ra ngoai ban co
vector<char> b((long long)W * W, 0); // 0: trong, 1: X (thay Son), 2: O (hoc tro)
int dr[4] = {0, 1, 1, 1}, dc[4] = {1, 0, 1, -1}; // ngang, doc, cheo chinh, cheo phu
int ans = 0;
for (int t = 1; t <= k && ans == 0; t++) {
int r, c;
cin >> r >> c;
char q = (t % 2 == 1) ? 1 : 2; // nuoc le: X, nuoc chan: O
b[(long long)r * W + c] = q;
for (int d = 0; d < 4; d++) {
int dem = 1; // tinh ca quan vua di
int x = r + dr[d], y = c + dc[d];
while (b[(long long)x * W + y] == q) { dem++; x += dr[d]; y += dc[d]; }
x = r - dr[d]; y = c - dc[d];
while (b[(long long)x * W + y] == q) { dem++; x -= dr[d]; y -= dc[d]; }
if (dem >= 5) { ans = t; break; }
}
}
cout << ans << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); k = int(data[1])
W = n + 2 # them 1 o vien moi phia de khong bi tran ra ngoai ban co
b = bytearray(W * W) # 0: trong, 1: X (thay Son), 2: O (hoc tro)
huong = (1, W, W + 1, W - 1) # ngang, doc, cheo chinh, cheo phu (tren mang phang)
ans = 0
for t in range(1, k + 1):
p = int(data[2 * t]) * W + int(data[2 * t + 1])
q = 1 if t % 2 == 1 else 2
b[p] = q
for d in huong:
dem = 1 # tinh ca quan vua di
x = p + d
while b[x] == q:
dem += 1; x += d
x = p - d
while b[x] == q:
dem += 1; x -= d
if dem >= 5:
ans = t
break
if ans:
break
print(ans)
main()X X _ X X. (2) Đòi đúng 5 quân (dem == 5): bỏ sót khi nối thành dãy 6, 7 quân — đề nói "từ 5 quân trở lên". (3) Quên hướng chéo phụ (↙). Ví dụ của đề "hiền" nên cả ba lỗi đều vẫn ra đúng $10$!Bộ test chấm "bắt" những lỗi nào?
Bộ test có 30 test: Subtask 1 có 10 test ($N \le 15$: ví dụ, $N = 1$, bàn $4 \times 4$ đầy quân, bàn $15 \times 15$ đầy quân mà không ai thắng, thắng ở góc bàn cờ…), Subtask 2 có 9 test ($N \approx 300$, gần như kín bàn cờ, khoảng $7$–$9 \cdot 10^4$ nước, người thắng xuất hiện rất muộn hoặc không ai thắng), Subtask 3 có 11 test ($N$ từ $4800$ đến $5000$, gần $3 \cdot 10^5$ nước; có test quân dày đặc trong một khối $500 \times 600$, có test quân rải khắp bàn, có test thắng sát mép). Các dãy thắng được cài sẵn đủ kiểu: ngang, dọc, hai hướng chéo, quân cuối lấp vào giữa hoặc ở đầu mút, dãy đúng 5 hoặc 6, 7 quân. Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (10 test) | Sub 2 (9 test) | Sub 3 (11 test) | Điểm |
|---|---|---|---|---|
| Cách 1 – Quét cả bàn cờ | Đúng 10/10 | TLE 0/9 | TLE 0/11 | 30 |
| Cách 2 – Quét 4 đường thẳng | Đúng 10/10 | Đúng 9/9 | TLE 0/11 | 60 |
| Cách 3 – Đếm quanh ô vừa đánh (chuẩn) | Đúng 10/10 | Đúng 9/9 | Đúng 11/11 | 100 |
| Sai: chỉ xét dãy nhận quân vừa đánh làm đầu mút | WA 6/10 | WA 3/9 | WA 3/11 | 38,9 |
Sai: đòi đúng 5 quân (dem == 5) | WA 8/10 | WA 6/9 | WA 7/11 | 69,5 |
| Sai: quên hướng chéo phụ | WA 8/10 | WA 6/9 | WA 7/11 | 69,5 |
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à quá thời gian (hơn 3 giây) ở toàn bộ 20 test còn lại; Cách 2 đúng 19/19 test của hai subtask đầu và quá thời gian cả 11 test Subtask 3; Cách 3 đúng 30/30 test, test lâu nhất chạy khoảng 0,1 giây. Lời giải Python của Cách 3 cũng đúng 30/30 test, chạy tối đa khoảng 0,5 giây với CPython. Ví dụ của đề khá "hiền": dãy thắng dài đúng 5 quân, nằm trên đường chéo chính và quân cuối cùng ở đầu mút — nên cả ba lời giải sai ở bảng trên đều vẫn ra đúng $10$. Nhớ tự nghĩ thêm test nha!
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