Tỉa cành (Đề tự luyện HSG Tin quốc gia – Bài 2)
Đề bài
Tỉa cành
Chậu mai giấy của thầy Sơn có $N$ đoạn cành và $N$ mắt cành (đánh số $1..N$), mặt đất là mắt cành $0$. Đoạn cành $i$ nối mắt cành $i$ với mắt cành $p_i$ ngay bên dưới. Hai người lần lượt chọn một đoạn cành còn trên chậu và cắt; mọi đoạn cành không còn nối xuống đất rơi theo. Ai đến lượt mà không còn đoạn nào để cắt thì thua. Thầy Sơn đi trước, cả hai chơi tối ưu.
Tìm mọi đoạn cành mà nếu thầy cắt ở nước đầu tiên thì thầy chắc chắn thắng.
Dữ liệu vào: dòng đầu $N$ $(1 \le N \le 2\cdot 10^5)$; dòng sau $p_1, \ldots, p_N$ $(0 \le p_i \le N,\ p_i \ne i)$, từ mọi mắt cành đi theo $p$ đều tới $0$.
Kết quả: dòng đầu $W$ = số đoạn cành như vậy; nếu $W > 0$, dòng hai in các chỉ số đó theo thứ tự tăng dần.
- Subtask 1 (15%): $N \le 15$.
- Subtask 2 (20%): mỗi cây mai là một thân thẳng (các $p_i \ne 0$ đôi một khác nhau).
- Subtask 3 (25%): $N \le 3000$.
- Subtask 4 (40%): không có ràng buộc gì thêm.
Giới hạn thời gian: C++ 1 giây, Python/PyPy 3 giây.
10
0 0 4 0 1 3 2 4 4 53
2 3 5Ba cây: thân $1 \to 5 \to 10$; thân $2 \to 7$; cây gốc $4$ có ba nhánh $3$ (trên đó là $6$), $8$, $9$. Cắt đoạn $2$, $3$ hoặc $5$ thì thầy Sơn chắc chắn thắng.
6
0 1 1 0 4 40Hai cây giống hệt nhau: thầy cắt gì ở cây này, học sinh cắt đúng đoạn tương ứng ở cây kia. Thầy Sơn không có nước đầu nào chắc 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 Tỉa cànhLời mở đầu
Đây là trò chơi hai người, thông tin đầy đủ, không có may rủi, và ván nào cũng kết thúc (mỗi nước bớt ít nhất một đoạn cành). Với loại trò chơi này, mỗi trạng thái hoặc là thắng (người sắp đi có cách thắng), hoặc là thua:
- trạng thái không còn nước đi là trạng thái thua;
- một trạng thái là thắng khi và chỉ khi có ít nhất một nước đi dẫn tới trạng thái thua.
Đề hỏi: những nước đi đầu tiên nào đưa chậu mai về trạng thái thua (cho học sinh). Ba ý tưởng sẽ lần lượt xuất hiện:
- Tách trò chơi: các cây mai trên chậu, và cả các nhánh mọc ra từ cùng một mắt cành, là những trò chơi độc lập chơi song song. Định lý Sprague–Grundy nói rằng mỗi trò chơi như vậy tương đương với một đống sỏi trong trò Nim, và cả tổng thể tương đương với Nim nhiều đống: người đi trước thua khi và chỉ khi XOR các "số Grundy" bằng $0$.
- Nguyên lý dấu hai chấm: số Grundy của một cây mai tính được bằng một công thức rất gọn từ dưới lên.
- Lan truyền "giá trị cần đạt" từ mặt đất lên ngọn, để kiểm tra mọi nước cắt trong $O(1)$ mỗi nước.
Mỗi nhánh "đoạn cành $c$ + mọi thứ phía trên" có số Grundy $g(c) + 1$.
Lộ trình:
Cách 1Vét cạn trạng thái – O(2^N · N) · 15%
Một trạng thái của ván chơi được mô tả bằng tập các mắt cành còn nối với đất – một số nhị phân $N$ bit s. Gọi sub[i] là tập các mắt cành nằm trên đoạn cành $i$ (gồm cả $i$): cắt đoạn $i$ thì cả tập này rơi, trạng thái mới là s & ~sub[i], luôn là một số nhỏ hơn s. Vì vậy ta tính win[s] theo thứ tự $s$ tăng dần:
Đáp án là mọi $i$ có win[full & ~sub[i]] = false, với full $= 2^N - 1$. Có $2^{15} = 32768$ trạng thái, mỗi trạng thái thử $15$ nước – rất nhanh.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> p(n + 1);
for (int i = 1; i <= n; i++) cin >> p[i];
vector<int> sub(n + 1, 0); // sub[i]: cac mat canh nam tren canh i (ke ca i)
for (int i = 1; i <= n; i++)
for (int v = i; v != 0; v = p[v]) sub[v] |= 1 << (i - 1);
int full = (1 << n) - 1;
vector<char> win(1 << n, 0); // win[s]: nguoi sap di thang khi con lai tap s
for (int s = 0; s <= full; s++)
for (int i = 1; i <= n && !win[s]; i++)
if ((s >> (i - 1) & 1) && !win[s & ~sub[i]]) win[s] = 1;
vector<int> ans;
for (int i = 1; i <= n; i++)
if (!win[full & ~sub[i]]) ans.push_back(i); // cat i xong doi thu thua
cout << ans.size() << "\n";
for (size_t i = 0; i < ans.size(); i++) cout << ans[i] << (i + 1 < ans.size() ? " " : "\n");
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
p = [0] + [int(x) for x in data[1:1 + n]]
sub = [0] * (n + 1) # sub[i]: cac mat canh nam tren canh i (ke ca i)
for i in range(1, n + 1):
v = i
while v != 0:
sub[v] |= 1 << (i - 1)
v = p[v]
full = (1 << n) - 1
win = bytearray(full + 1) # win[s]: nguoi sap di thang khi con lai tap s
for s in range(full + 1):
for i in range(1, n + 1):
if (s >> (i - 1)) & 1 and not win[s & ~sub[i]]:
win[s] = 1
break
ans = [i for i in range(1, n + 1) if not win[full & ~sub[i]]]
print(len(ans))
if ans:
print(" ".join(map(str, ans)))
main()Cách 2Mỗi thân thẳng là một đống Nim – O(N) · 35%
Khi mỗi cây là một thân thẳng dài $L$ đoạn, cắt đoạn thứ $h$ (tính từ đất, $1 \le h \le L$) thì thân còn đúng $h - 1$ đoạn. Tức là từ một đống $L$ viên sỏi ta được bốc để còn lại bất kỳ số nào từ $0$ đến $L-1$: đây chính là trò Nim với các đống $L_1, L_2, \ldots$
Ý chứng minh: từ $G = 0$, mọi nước đi đổi đúng một đống nên $G$ thành khác $0$; từ $G \ne 0$, lấy bit cao nhất của $G$, chọn một đống $L_j$ có bit đó bằng 1, thì $L_j \oplus G < L_j$ – giảm đống đó về $L_j \oplus G$ sẽ được $G = 0$. Trạng thái cuối (mọi đống bằng 0) có $G = 0$ và là trạng thái thua.
Vậy nước đầu thắng là nước đưa $G$ về $0$: với thân thứ $j$, cần còn lại đúng $L' = G \oplus L_j$ đoạn. Điều này làm được khi $L' < L_j$, bằng cách cắt đoạn thứ $h = L' + 1$ của thân đó. Mỗi thân cho tối đa một nước thắng. Code ghép thêm Cách 1 khi $N \le 15$:
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> p;
vector<int> brute() { // Cach 1: N <= 15
vector<int> sub(n + 1, 0);
for (int i = 1; i <= n; i++)
for (int v = i; v != 0; v = p[v]) sub[v] |= 1 << (i - 1);
int full = (1 << n) - 1;
vector<char> win(1 << n, 0);
for (int s = 0; s <= full; s++)
for (int i = 1; i <= n && !win[s]; i++)
if ((s >> (i - 1) & 1) && !win[s & ~sub[i]]) win[s] = 1;
vector<int> ans;
for (int i = 1; i <= n; i++)
if (!win[full & ~sub[i]]) ans.push_back(i);
return ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
p.assign(n + 1, 0);
vector<int> child(n + 1, -1), roots, win;
for (int i = 1; i <= n; i++) {
cin >> p[i];
if (p[i] == 0) roots.push_back(i); else child[p[i]] = i; // moi mat canh <= 1 con
}
if (n <= 15) win = brute();
else {
vector<int> len(roots.size());
int G = 0;
for (size_t j = 0; j < roots.size(); j++) { // moi than cay = mot dong Nim
int L = 0;
for (int v = roots[j]; v != -1; v = child[v]) L++;
len[j] = L; G ^= L;
}
for (size_t j = 0; j < roots.size(); j++) {
int h = (G ^ len[j]) + 1; // cat doan thu h: than con h - 1 doan
if (h > len[j]) continue;
int v = roots[j];
for (int s = 1; s < h; s++) v = child[v];
win.push_back(v);
}
sort(win.begin(), win.end());
}
cout << win.size() << "\n";
for (size_t i = 0; i < win.size(); i++) cout << win[i] << (i + 1 < win.size() ? " " : "\n");
return 0;
}import sys
def brute(n, p): # Cach 1: N <= 15
sub = [0] * (n + 1)
for i in range(1, n + 1):
v = i
while v != 0:
sub[v] |= 1 << (i - 1)
v = p[v]
full = (1 << n) - 1
win = bytearray(full + 1)
for s in range(full + 1):
for i in range(1, n + 1):
if (s >> (i - 1)) & 1 and not win[s & ~sub[i]]:
win[s] = 1
break
return [i for i in range(1, n + 1) if not win[full & ~sub[i]]]
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
p = [0] * (n + 1)
child = [-1] * (n + 1)
roots = []
for i in range(1, n + 1):
q = int(data[i]); p[i] = q
if q == 0:
roots.append(i)
else:
child[q] = i # moi mat canh <= 1 con
if n <= 15:
win = brute(n, p)
else:
lens = []
G = 0
for r in roots: # moi than cay = mot dong Nim
L = 0; v = r
while v != -1:
L += 1; v = child[v]
lens.append(L); G ^= L
win = []
for j in range(len(roots)):
h = (G ^ lens[j]) + 1 # cat doan thu h: than con h - 1 doan
if h > lens[j]:
continue
v = roots[j]
for _ in range(h - 1):
v = child[v]
win.append(v)
win.sort()
print(len(win))
if win:
print(" ".join(map(str, win)))
main()wrong_size.cpp trong bảng cuối bài đúng hết subtask 2 nhưng trượt gần hết phần còn lại.Cách 3Định lý Sprague–Grundy và nguyên lý dấu hai chấm – O(N²) · 60%
Số Grundy. Với mỗi trạng thái $X$, định nghĩa $\text{gr}(X) = \text{mex}\{\text{gr}(Y) : X \to Y\}$, trong đó $\text{mex}$ của một tập là số tự nhiên nhỏ nhất không thuộc tập đó. Trạng thái thua có $\text{gr} = 0$. Một thân thẳng dài $L$ có $\text{gr} = \text{mex}\{0, 1, \ldots, L-1\} = L$.
Định lý Sprague–Grundy. Nếu một trò chơi gồm nhiều trò chơi con độc lập (mỗi lượt chỉ đi ở một trò con) thì số Grundy của tổng là XOR số Grundy các trò con. Ở chậu mai: các cây độc lập, nên $G = \bigoplus$ (số Grundy từng cây), thầy Sơn cần đưa $G$ về $0$.
Nguyên lý dấu hai chấm. Gọi $g(v)$ là số Grundy của "phần cây phía trên mắt cành $v$" (coi $v$ như mặt đất). Khi đó
$$g(v) = \bigoplus_{c \text{ mọc từ } v} \big(g(c) + 1\big), \qquad g(\text{mắt cành không có nhánh}) = 0.$$Lý do: các nhánh mọc từ $v$ là các trò con độc lập (XOR), và ta chỉ cần chứng minh bổ đề: nếu trò chơi $H$ có số Grundy $x$ thì trò "một đoạn cành $c$, trên đó là $H$" có số Grundy $x + 1$. Chứng minh quy nạp: từ trò này, hoặc cắt đoạn $c$ (cả nhánh rơi, về trạng thái có Grundy $0$), hoặc đi một nước trong $H$, sang $H'$ có Grundy $y$, theo quy nạp thành $y + 1$. Tập các Grundy đi tới được là $\{0\} \cup \{y + 1\}$ với $y$ chạy trên tập Grundy đi tới được từ $H$, nên mex của nó bằng $1 + \text{mex}(\ldots) = x + 1$.
Với ví dụ 1: cây gốc $4$ có $g(6) = 0$, $g(3) = 0 + 1 = 1$, $g(8) = g(9) = 0$, nên $g(4) = (1+1) \oplus (0+1) \oplus (0+1) = 2$, và cả cây (tính đoạn $4$) có Grundy $3$. Hai thân thẳng có Grundy $3$ và $2$. Tổng $G = 3 \oplus 2 \oplus 3 = 2 \ne 0$: thầy Sơn đi trước thắng được. Trên toàn chậu, $g(0) = G$.
Thử từng nước. Với $N \le 3000$, ta thử cắt từng đoạn cành $c$, bỏ cả cây con phía trên $c$ (dùng thứ tự DFS: các mắt cành có tin trong $[\text{tin}[c], \text{tout}[c])$), tính lại $g$ của toàn chậu trong $O(N)$; nước cắt $c$ thắng khi $g(0)$ mới bằng $0$. Tổng $O(N^2)$. Code ghép thêm Cách 2 cho subtask 2 (ở đó $N$ lớn).
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> p, order, tin, tout;
vector<vector<int>> ch;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
p.assign(n + 1, 0); ch.assign(n + 1, {});
bool bamboo = true;
for (int i = 1; i <= n; i++) {
cin >> p[i]; ch[p[i]].push_back(i);
if (p[i] != 0 && ch[p[i]].size() > 1) bamboo = false;
}
vector<int> win;
if (bamboo) { // Cach 2: cac than thang = Nim
int G = 0;
vector<int> len(n + 1, 0);
for (int r : ch[0]) { int L = 0; for (int v = r; ; v = ch[v][0]) { L++; if (ch[v].empty()) break; } len[r] = L; G ^= L; }
for (int r : ch[0]) {
int h = (G ^ len[r]) + 1;
if (h > len[r]) continue;
int v = r;
for (int s = 1; s < h; s++) v = ch[v][0];
win.push_back(v);
}
} else { // Cach 3: thu cat tung canh, tinh lai O(N)
tin.assign(n + 1, 0); tout.assign(n + 1, 0);
int timer = 0;
vector<pair<int, int>> st = {{0, 0}}; // DFS khong de quy: Euler tour
while (!st.empty()) {
auto &[v, k] = st.back();
if (k == 0) { tin[v] = timer++; order.push_back(v); }
if (k < (int)ch[v].size()) { int c = ch[v][k++]; st.push_back({c, 0}); }
else { tout[v] = timer; st.pop_back(); }
}
vector<int> g(n + 1);
for (int c = 1; c <= n; c++) {
fill(g.begin(), g.end(), 0);
for (int h = n; h >= 1; h--) { // duyet nguoc thu tu DFS
int v = order[h];
if (tin[c] <= tin[v] && tin[v] < tout[c]) continue; // da roi theo canh c
g[p[v]] ^= g[v] + 1;
}
if (g[0] == 0) win.push_back(c);
}
}
sort(win.begin(), win.end());
cout << win.size() << "\n";
for (size_t i = 0; i < win.size(); i++) cout << win[i] << (i + 1 < win.size() ? " " : "\n");
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
p = [0] * (n + 1)
ch = [[] for _ in range(n + 1)]
bamboo = True
for i in range(1, n + 1):
q = int(data[i]); p[i] = q; ch[q].append(i)
if q != 0 and len(ch[q]) > 1:
bamboo = False
win = []
if bamboo: # Cach 2: cac than thang = Nim
G = 0; lens = {}
for r in ch[0]:
L = 0; v = r
while True:
L += 1
if not ch[v]:
break
v = ch[v][0]
lens[r] = L; G ^= L
for r in ch[0]:
h = (G ^ lens[r]) + 1
if h > lens[r]:
continue
v = r
for _ in range(h - 1):
v = ch[v][0]
win.append(v)
else: # Cach 3: thu cat tung canh, tinh lai O(N)
tin = [0] * (n + 1); tout = [0] * (n + 1); order = []
timer = 0
st = [(0, 0)] # DFS khong de quy: Euler tour
while st:
v, k = st.pop()
if k == 0:
tin[v] = timer; timer += 1; order.append(v)
if k < len(ch[v]):
st.append((v, k + 1)); st.append((ch[v][k], 0))
else:
tout[v] = timer
rev = order[:0:-1]
for c in range(1, n + 1):
lo = tin[c]; hi = tout[c]
g = [0] * (n + 1)
for v in rev: # duyet nguoc thu tu DFS
if lo <= tin[v] < hi:
continue # da roi theo canh c
g[p[v]] ^= g[v] + 1
if g[0] == 0:
win.append(c)
win.sort()
print(len(win))
if win:
print(" ".join(map(str, win)))
main()Cách 4Lan truyền "giá trị cần đạt" từ gốc lên ngọn – O(N) · 100%
Cắt đoạn $c$ (mọc từ mắt cành $v$) chỉ làm thay đổi các giá trị $g$ trên đường từ $v$ xuống đất. Thay vì tính lại cả đường đi, ta hỏi ngược: $g(v)$ phải trở thành bao nhiêu thì tổng ở mặt đất bằng $0$? Gọi giá trị đó là $t(v)$.
- Ở mặt đất: $t(0) = 0$ (muốn $G = 0$).
- Xét nhánh $c$ mọc từ $v$. Nếu chỉ phần phía trên $c$ thay đổi thì $g(v) = \big(g(v) \oplus (g(c)+1)\big) \oplus (\text{giá trị mới của } g(c) + 1)$. Muốn $g(v) = t(v)$ thì nhánh $c$ phải đóng góp đúng $$r = t(v) \oplus g(v) \oplus (g(c) + 1).$$
- Nếu $r = 0$: cắt chính đoạn $c$ làm nhánh này đóng góp $0$ – đó là một nước thắng!
- Nếu $r \ge 1$: muốn nước cắt nằm phía trên $c$ thì cần $g(c)$ mới $= r - 1$, tức $t(c) = r - 1$, rồi lặp lại lên trên.
- Nếu $t(v)$ không tồn tại (đánh dấu $-1$) thì mọi nhánh phía trên $v$ cũng không có nước thắng.
Với ví dụ 1 ($G = 2$): ở mặt đất, nhánh $1$ (Grundy $3$) cần đóng góp $0 \oplus 2 \oplus 3 = 1$, tức $t(1) = 0$; lên tiếp, nhánh $5$ (Grundy $2$) cần đóng góp $0 \oplus g(1) \oplus 2 = 0 \oplus 2 \oplus 2 = 0$ → cắt $5$ thắng. Nhánh $2$ cần đóng góp $0 \oplus 2 \oplus 2 = 0$ → cắt $2$ thắng. Nhánh $4$ (Grundy $3$) cần $1$, nên $t(4) = 0$; nhánh $3$ (đóng góp $2$) cần $0 \oplus 2 \oplus 2 = 0$ → cắt $3$ thắng. Mô phỏng:
Code hoàn chỉnh: dựng danh sách con bằng mảng head/nxt, BFS từ mặt đất để có thứ tự duyệt (không đệ quy, nên cây sâu $2\cdot 10^5$ tầng cũng không tràn ngăn xếp), tính $g$ theo thứ tự BFS ngược, rồi tính $t$ theo thứ tự BFS xuôi. Mảng t[v] = -1 nghĩa là "không có giá trị cần đạt". Cuối cùng nhớ sắp xếp các nước thắng trước khi in.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<int> p(n + 1), head(n + 1, -1), nxt(n + 1);
for (int i = 1; i <= n; i++) {
cin >> p[i];
nxt[i] = head[p[i]]; head[p[i]] = i; // them i vao danh sach con cua p[i]
}
vector<int> order; order.reserve(n + 1);
order.push_back(0); // BFS tu mat dat (dinh 0)
for (size_t h = 0; h < order.size(); h++)
for (int c = head[order[h]]; c != -1; c = nxt[c]) order.push_back(c);
vector<int> g(n + 1, 0);
for (int h = n; h >= 1; h--) { // nguyen ly "dau hai cham"
int v = order[h];
g[p[v]] ^= g[v] + 1;
}
vector<int> t(n + 1, -1); // t[v]: gia tri g[v] can co de tong = 0
t[0] = 0;
vector<int> win;
for (int h = 1; h <= n; h++) {
int c = order[h], v = p[c];
if (t[v] < 0) continue;
int r = t[v] ^ g[v] ^ (g[c] + 1); // nhanh c phai dong gop r
if (r == 0) win.push_back(c); // cat canh c: dung nuoc thang
else t[c] = r - 1;
}
sort(win.begin(), win.end());
cout << win.size() << "\n";
for (size_t i = 0; i < win.size(); i++) cout << win[i] << (i + 1 < win.size() ? " " : "\n");
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0])
p = [0] * (n + 1)
head = [-1] * (n + 1)
nxt = [0] * (n + 1)
for i in range(1, n + 1):
q = int(data[i]); p[i] = q
nxt[i] = head[q]; head[q] = i # them i vao danh sach con cua q
order = [0] # BFS tu mat dat (dinh 0)
for v in order:
c = head[v]
while c != -1:
order.append(c); c = nxt[c]
g = [0] * (n + 1)
for h in range(n, 0, -1): # nguyen ly "dau hai cham"
v = order[h]
g[p[v]] ^= g[v] + 1
t = [-1] * (n + 1) # t[v]: gia tri g[v] can co de tong = 0
t[0] = 0
win = []
for h in range(1, n + 1):
c = order[h]; v = p[c]
tv = t[v]
if tv < 0:
continue
r = tv ^ g[v] ^ (g[c] + 1) # nhanh c phai dong gop r
if r == 0:
win.append(c) # cat canh c: dung nuoc thang
else:
t[c] = r - 1
win.sort()
out = [str(len(win))]
if win:
out.append(" ".join(map(str, win)))
sys.stdout.write("\n".join(out) + "\n")
main()Bộ test chấm "bắt" những lỗi nào?
| Cách làm | Sub 1 (15%) | Sub 2 (20%) | Sub 3 (25%) | Sub 4 (40%) | Điểm |
|---|---|---|---|---|---|
| Cách 1 – Vét cạn trạng thái | Đúng | TLE/RE | TLE | TLE | 15 |
| Cách 2 – Thân thẳng = Nim | Đúng | Đúng | WA | WA | 35 |
| Cách 3 – Dấu hai chấm, thử từng nước O(N²) | Đúng | Đúng | Đúng | TLE | 60 |
| Cách 4 – Lan truyền giá trị cần đạt (sol.cpp) | Đúng | Đúng | Đúng | Đúng | 100 |
| Sai: quên sắp xếp, in theo thứ tự BFS | 7/10 | 3/8 | 4/9 | 3/11 | 40,0 |
| Sai: coi mỗi cây là đống Nim cỡ "số đoạn cành" | 4/10 | 8/8 | 1/9 | 0/11 | 28,8 |
| Sai: không lan truyền, coi cắt c làm G ⊕= g(c)+1 | 5/10 | 2/8 | 1/9 | 0/11 | 15,3 |
| Sai: chỉ xét cắt cả cây (đoạn cắm đất) | 4/10 | 2/8 | 1/9 | 0/11 | 13,8 |
| Sai: quên "+1" trong nguyên lý dấu hai chấm | 3/10 | 2/8 | 0/9 | 0/11 | 9,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: bộ test có 38 test (10 + 8 + 9 + 11), mỗi cách ở trên đạt đúng số điểm công bố, còn năm lời giải sai bị bắt như bảng trên. Mọi test của subtask 3 và 4 đều là "rừng" nhiều cây có nhánh, nên mẹo Nim cho thân thẳng không ăn được điểm nào ở đó. Lời giải chuẩn sol.cpp chạy test lâu nhất chưa tới 0,1 giây; bản Python sol.py cho cùng đáp án trên mọi test (CPython khoảng 0,5 giây CPU, các em vẫn nên chọn PyPy 3 khi nộp). Code không dùng đệ quy nên cây sâu hàng chục nghìn tầng cũng không lo tràn ngăn xếp. "TLE" nghĩa là chạy quá 3 lần giới hạn thời gian.
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