Băng rôn (Đề tự luyện HSG Tin 9 – Bài 4)
Đề bài
Băng rôn. Nội dung băng rôn được ghi bằng mã rút gọn $S$: chữ cái là chính nó; cụm k(X) ($2 \le k \le 10^9$) là nội dung của $X$ viết liên tiếp $k$ lần; các phần viết nối tiếp nhau. Ví dụ ab3(c2(de))f → abcdedecdedecdedef. Băng rôn có $T \le 10^{18}$ chữ. Trả lời $Q$ câu hỏi: chữ ở vị trí $p_j$ là chữ gì?
Dữ liệu vào: dòng 1 là $S$ $(|S| \le 2 \cdot 10^5)$; dòng 2 là $Q$ $(Q \le 3 \cdot 10^5)$; dòng 3 gồm $p_1, \dots, p_Q$ $(1 \le p_j \le T)$.
Kết quả: một dòng gồm $Q$ chữ cái viết liền.
- Subtask 1 (15%): $T \le 10^6$.
- Subtask 2 (20%): $Q \le 10$.
- Subtask 3 (30%): $Q \le 1000$.
- Subtask 4 (35%): không ràng buộc thêm.
di2(hoc3(vui))ne
7
1 22 16 5 3 4 17duochocBăng rôn có 28 chữ: dihocvuivuivuihocvuivuivuine. Các vị trí 1, 22, 16, 5, 3, 4, 17 lần lượt là d u o c h o c.
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 Băng rônLời mở đầu
Băng rôn có thể dài tới $10^{18}$ chữ nên không thể bung ra. Ta phải "đi tìm" chữ cần hỏi ngay trên mã rút gọn. Hãy nhìn mã như một cái cây: mỗi cụm k(...) là một nhóm, con của một nhóm là các đoạn chữ liền nhau hoặc các nhóm con; cả xâu $S$ là nhóm gốc với $k = 1$.
Hình 1. Cây nhóm của di2(hoc3(vui))ne. Muốn tìm chữ thứ $p$, đi từ gốc xuống: chọn con chứa vị trí $p$, vào nhóm thì lấy dư theo độ dài một lần lặp.
Đi xuống cây. Đứng ở một nhóm với vị trí $p$ (tính trong một lần nội dung của nhóm). Duyệt các con: con nào dài $d$ mà $p > d$ thì $p \mathrel{-}= d$ và sang con kế tiếp; đến con chứa $p$: nếu là đoạn chữ thì đáp án là chữ thứ $p$ của đoạn; nếu là nhóm con k(X) với một lần $X$ dài $m$ thì nội dung nhóm là $X$ lặp lại, vị trí $p$ ứng với vị trí $(p - 1) \bmod m + 1$ trong một lần $X$ — rồi đi tiếp xuống.
Cách 1Bung cả băng rôn ra – O(T + Q) · 15%
Khi $T \le 10^6$, cứ bung mã ra thành xâu thật rồi trả lời bangRon[p - 1]. Hàm đệ quy bung() đọc từ vị trí pos: gặp chữ cái thì thêm vào; gặp số $k$ thì đọc hết số, bỏ qua (, gọi đệ quy để bung phần bên trong, bỏ qua ) rồi nối phần đó $k$ lần. Gặp ) hoặc hết xâu thì trả về.
#include <bits/stdc++.h>
using namespace std;
string S;
int pos = 0;
// bung noi dung tu vi tri pos cho den het xau hoac den dau ')'
string bung() {
string r;
while (pos < (int)S.size() && S[pos] != ')') {
if (S[pos] >= 'a' && S[pos] <= 'z') r += S[pos++];
else {
long long k = 0;
while (S[pos] != '(') k = k * 10 + (S[pos++] - '0');
pos++; // bo qua '('
string x = bung();
pos++; // bo qua ')'
for (int t = 0; t < k; t++) r += x;
}
}
return r;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> S >> q;
string bangRon = bung(); // chi lam duoc khi bang ron ngan (T <= 10^6)
string out;
for (int j = 0; j < q; j++) {
long long p;
cin >> p;
out += bangRon[p - 1];
}
cout << out << "\n";
return 0;
}import sys
def bung(S, pos):
# bung noi dung tu vi tri pos cho den het xau hoac den dau ')'; tra ve (noi dung, vi tri dung)
parts = []
while pos < len(S) and S[pos] != ')':
c = S[pos]
if 'a' <= c <= 'z':
parts.append(c); pos += 1
else:
j = S.index('(', pos)
k = int(S[pos:j])
x, pos = bung(S, j + 1)
pos += 1 # bo qua ')'
parts.append(x * k)
return "".join(parts), pos
def main():
data = sys.stdin.read().split()
S = data[0]; q = int(data[1])
bang_ron, _ = bung(S, 0) # chi lam duoc khi bang ron ngan (T <= 10^6)
out = [bang_ron[int(data[2 + j]) - 1] for j in range(q)]
print("".join(out))
main()Cách 2Đi xuống cây, mỗi lần tính lại độ dài – O(Q · 60 · |S|) · 35%
Làm đúng cách "đi xuống cây" ở Lời mở đầu, nhưng độ dài mỗi nhóm được tính lại từ đầu bằng hàm đệ quy doDai(l, r) mỗi khi cần. Trước tiên dùng một ngăn xếp để biết dấu ( ở vị trí $i$ khớp với dấu ) ở vị trí khop[i]. Độ dài là số tới $10^{18}$: dùng long long.
#include <bits/stdc++.h>
using namespace std;
string S;
vector<int> khop; // khop[i] = vi tri ')' ung voi '(' o i
// do dai noi dung cua doan S[l, r) (tinh lai moi lan goi)
long long doDai(int l, int r) {
long long d = 0;
int i = l;
while (i < r) {
if (S[i] >= 'a' && S[i] <= 'z') { d++; i++; }
else {
long long k = 0;
while (S[i] != '(') k = k * 10 + (S[i++] - '0');
d += k * doDai(i + 1, khop[i]);
i = khop[i] + 1;
}
}
return d;
}
// chu cai o vi tri p (tinh tu 1) trong noi dung cua doan S[l, r)
char tim(int l, int r, long long p) {
int i = l;
while (true) {
if (S[i] >= 'a' && S[i] <= 'z') {
if (p == 1) return S[i];
p--; i++;
} else {
long long k = 0;
while (S[i] != '(') k = k * 10 + (S[i++] - '0');
long long mot = doDai(i + 1, khop[i]); // do dai mot lan lap
if (p <= k * mot) return tim(i + 1, khop[i], (p - 1) % mot + 1);
p -= k * mot;
i = khop[i] + 1;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> S >> q;
int n = S.size();
khop.assign(n, -1);
vector<int> st;
for (int i = 0; i < n; i++) {
if (S[i] == '(') st.push_back(i);
else if (S[i] == ')') { khop[st.back()] = i; st.pop_back(); }
}
string out;
for (int j = 0; j < q; j++) {
long long p;
cin >> p;
out += tim(0, n, p);
}
cout << out << "\n";
return 0;
}import sys
def do_dai(S, khop, l, r):
# do dai noi dung cua doan S[l, r) (tinh lai moi lan goi)
d = 0; i = l
while i < r:
if 'a' <= S[i] <= 'z':
d += 1; i += 1
else:
j = S.index('(', i)
d += int(S[i:j]) * do_dai(S, khop, j + 1, khop[j])
i = khop[j] + 1
return d
def tim(S, khop, l, r, p):
# chu cai o vi tri p (tinh tu 1) trong noi dung cua doan S[l, r)
i = l
while True:
if 'a' <= S[i] <= 'z':
if p == 1:
return S[i]
p -= 1; i += 1
else:
j = S.index('(', i)
k = int(S[i:j])
mot = do_dai(S, khop, j + 1, khop[j]) # do dai mot lan lap
if p <= k * mot:
return tim(S, khop, j + 1, khop[j], (p - 1) % mot + 1)
p -= k * mot
i = khop[j] + 1
def main():
data = sys.stdin.read().split()
S = data[0]; q = int(data[1]); n = len(S)
khop = [-1] * n; st = []
for i in range(n):
if S[i] == '(':
st.append(i)
elif S[i] == ')':
khop[st.pop()] = i
out = [tim(S, khop, 0, n, int(data[2 + j])) for j in range(q)]
print("".join(out))
main()doDai lại đi hết cả nhóm con. Nếu các nhóm lồng sâu ba mươi tầng, mỗi tầng chứa gần hết xâu, thì một câu hỏi đã tốn $30 \cdot 2 \cdot 10^5$ bước. Với $Q \le 10$ thì không sao, nhưng $Q = 1000$ thì quá chậm. Độ dài các nhóm không bao giờ thay đổi — tính một lần là đủ!Cách 3Tính trước độ dài mọi nhóm – O(|S| + Q · |S|) · 65%
Ta dựng cây một lần: nhóm số 0 là cả xâu; duyệt nội dung nhóm $u$, đoạn chữ liền nhau thành một con, gặp số thì tạo nhóm mới (đánh số tiếp theo) và nhảy qua dấu ) khớp. Vì nhóm cha luôn được tạo trước nhóm con, duyệt các nhóm theo thứ tự ngược thì khi tính nhóm $u$, mọi nhóm con của nó đã có độ dài. Với mỗi nhóm ta lưu tt[u][j] = tổng độ dài các con $0..j-1$ (tổng tiền tố), và dai[u] = k[u] * tt[u].back().
Khi trả lời câu hỏi, ở mỗi nhóm ta vẫn duyệt lần lượt các con để tìm con chứa $p$ (dòng while (tt[u][j + 1] < p) j++;). Code giống hệt Cách 4 dưới đây, chỉ khác đúng dòng tìm $j$. Mỗi câu hỏi tốn tới $O(|S|)$ khi một nhóm có rất nhiều con, nên $Q = 3 \cdot 10^5$ câu hỏi thì quá chậm.
#include <bits/stdc++.h>
using namespace std;
// Moi nhom k(X) la mot "nut". Con cua mot nut: doan chu cai lien tiep, hoac mot nhom con.
struct Con { bool laNhom; int vt; }; // laNhom = false: doan chu bat dau o S[vt]; true: nhom so vt
string S;
vector<int> khop; // khop[i] = vi tri ')' ung voi '(' o i
vector<vector<Con>> con; // danh sach con cua tung nut
vector<vector<long long>> tt; // tt[u][j] = tong do dai cac con 0..j-1 cua nut u
vector<long long> k, dai; // he so lap va do dai SAU KHI lap cua tung nut
vector<int> dauNut, cuoiNut; // noi dung nut nam trong S[dauNut, cuoiNut)
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> S >> q;
int n = S.size();
khop.assign(n, -1);
vector<int> st;
for (int i = 0; i < n; i++) {
if (S[i] == '(') st.push_back(i);
else if (S[i] == ')') { khop[st.back()] = i; st.pop_back(); }
}
// nut 0 = ca xau (he so 1). Tao cac nut theo thu tu: cha luon duoc tao truoc con.
k.push_back(1); dauNut.push_back(0); cuoiNut.push_back(n); con.push_back({});
for (int u = 0; u < (int)k.size(); u++) {
int i = dauNut[u];
while (i < cuoiNut[u]) {
if (S[i] >= 'a' && S[i] <= 'z') {
con[u].push_back({false, i});
while (i < cuoiNut[u] && S[i] >= 'a' && S[i] <= 'z') i++;
} else { // doc so k roi den '('
long long x = 0;
while (S[i] != '(') { x = x * 10 + (S[i] - '0'); i++; }
int v = k.size();
k.push_back(x); dauNut.push_back(i + 1); cuoiNut.push_back(khop[i]); con.push_back({});
con[u].push_back({true, v});
i = khop[i] + 1;
}
}
}
// tinh do dai tu nut con len nut cha (nut tao sau duoc tinh truoc)
int m = k.size();
tt.assign(m, {});
dai.assign(m, 0);
for (int u = m - 1; u >= 0; u--) {
tt[u].push_back(0);
for (auto &c : con[u]) {
long long d;
if (c.laNhom) d = dai[c.vt];
else { int j = c.vt; while (j < n && S[j] >= 'a' && S[j] <= 'z') j++; d = j - c.vt; }
tt[u].push_back(tt[u].back() + d);
}
dai[u] = k[u] * tt[u].back(); // de bai dam bao khong vuot 10^18
}
string out;
for (int t = 0; t < q; t++) {
long long p;
cin >> p; // vi tri tinh tu 1, nam trong noi dung nut u (chua lap)
int u = 0;
while (true) {
// tim con j: tt[u][j] < p <= tt[u][j + 1]
int j = 0;
while (tt[u][j + 1] < p) j++; // duyet lan luot tung con
p -= tt[u][j];
Con c = con[u][j];
if (!c.laNhom) { out += S[c.vt + p - 1]; break; }
u = c.vt;
long long mot = tt[u].back(); // do dai MOT lan noi dung cua nhom
p = (p - 1) % mot + 1; // vi tri trong lan lap chua no
}
}
cout << out << "\n";
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
S = data[0].decode()
q = int(data[1])
n = len(S)
khop = [-1] * n # khop[i] = vi tri ')' ung voi '(' o i
st = []
for i in range(n):
c = S[i]
if c == '(':
st.append(i)
elif c == ')':
khop[st.pop()] = i
# nut 0 = ca xau (he so 1); cha luon duoc tao truoc con
k = [1]; dau = [0]; cuoi = [n]
loai = [[]] # loai[u][j]: -1 neu con j la doan chu, nguoc lai la so hieu nhom con
vt = [[]] # vt[u][j]: vi tri bat dau doan chu (neu la doan chu)
dd = [[]] # dd[u][j]: do dai doan chu (neu la doan chu)
u = 0
while u < len(k):
i = dau[u]; e = cuoi[u]
L = loai[u]; V = vt[u]; D = dd[u]
while i < e:
c = S[i]
if 'a' <= c <= 'z':
j = i
while j < e and 'a' <= S[j] <= 'z':
j += 1
L.append(-1); V.append(i); D.append(j - i)
i = j
else: # doc so k roi den '('
j = S.index('(', i)
v = len(k)
k.append(int(S[i:j])); dau.append(j + 1); cuoi.append(khop[j])
loai.append([]); vt.append([]); dd.append([])
L.append(v); V.append(0); D.append(0)
i = khop[j] + 1
u += 1
m = len(k)
tt = [None] * m # tt[u][j] = tong do dai cac con 0..j-1 cua nut u
dai = [0] * m # do dai sau khi lap cua nut u
for u in range(m - 1, -1, -1):
t = [0]; s = 0
for j in range(len(loai[u])):
g = loai[u][j]
s += dd[u][j] if g < 0 else dai[g]
t.append(s)
tt[u] = t
dai[u] = k[u] * s
out = []
for idx in range(2, 2 + q):
p = int(data[idx])
u = 0
while True:
t = tt[u]
j = 0
while t[j + 1] < p: # duyet lan luot tung con
j += 1
p -= t[j]
g = loai[u][j]
if g < 0:
out.append(S[vt[u][j] + p - 1])
break
u = g
p = (p - 1) % tt[u][-1] + 1 # vi tri trong lan lap chua no
sys.stdout.write("".join(out) + "\n")
main()Cách 4Tổng tiền tố + tìm kiếm nhị phân – O(|S| + Q · 60 · log |S|) · 100%
Dãy tt[u] tăng dần (độ dài mỗi con đều dương), nên con chứa vị trí $p$ là con $j$ với tt[u][j] < p ≤ tt[u][j + 1] — tìm bằng chặt nhị phân (lower_bound trong C++, bisect_left trong Python). Mỗi tầng tốn $O(\log |S|)$ và có không quá 60 tầng.
#include <bits/stdc++.h>
using namespace std;
// Moi nhom k(X) la mot "nut". Con cua mot nut: doan chu cai lien tiep, hoac mot nhom con.
struct Con { bool laNhom; int vt; }; // laNhom = false: doan chu bat dau o S[vt]; true: nhom so vt
string S;
vector<int> khop; // khop[i] = vi tri ')' ung voi '(' o i
vector<vector<Con>> con; // danh sach con cua tung nut
vector<vector<long long>> tt; // tt[u][j] = tong do dai cac con 0..j-1 cua nut u
vector<long long> k, dai; // he so lap va do dai SAU KHI lap cua tung nut
vector<int> dauNut, cuoiNut; // noi dung nut nam trong S[dauNut, cuoiNut)
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> S >> q;
int n = S.size();
khop.assign(n, -1);
vector<int> st;
for (int i = 0; i < n; i++) {
if (S[i] == '(') st.push_back(i);
else if (S[i] == ')') { khop[st.back()] = i; st.pop_back(); }
}
// nut 0 = ca xau (he so 1). Tao cac nut theo thu tu: cha luon duoc tao truoc con.
k.push_back(1); dauNut.push_back(0); cuoiNut.push_back(n); con.push_back({});
for (int u = 0; u < (int)k.size(); u++) {
int i = dauNut[u];
while (i < cuoiNut[u]) {
if (S[i] >= 'a' && S[i] <= 'z') {
con[u].push_back({false, i});
while (i < cuoiNut[u] && S[i] >= 'a' && S[i] <= 'z') i++;
} else { // doc so k roi den '('
long long x = 0;
while (S[i] != '(') { x = x * 10 + (S[i] - '0'); i++; }
int v = k.size();
k.push_back(x); dauNut.push_back(i + 1); cuoiNut.push_back(khop[i]); con.push_back({});
con[u].push_back({true, v});
i = khop[i] + 1;
}
}
}
// tinh do dai tu nut con len nut cha (nut tao sau duoc tinh truoc)
int m = k.size();
tt.assign(m, {});
dai.assign(m, 0);
for (int u = m - 1; u >= 0; u--) {
tt[u].push_back(0);
for (auto &c : con[u]) {
long long d;
if (c.laNhom) d = dai[c.vt];
else { int j = c.vt; while (j < n && S[j] >= 'a' && S[j] <= 'z') j++; d = j - c.vt; }
tt[u].push_back(tt[u].back() + d);
}
dai[u] = k[u] * tt[u].back(); // de bai dam bao khong vuot 10^18
}
string out;
for (int t = 0; t < q; t++) {
long long p;
cin >> p; // vi tri tinh tu 1, nam trong noi dung nut u (chua lap)
int u = 0;
while (true) {
// tim con j: tt[u][j] < p <= tt[u][j + 1]
int j = lower_bound(tt[u].begin(), tt[u].end(), p) - tt[u].begin() - 1;
p -= tt[u][j];
Con c = con[u][j];
if (!c.laNhom) { out += S[c.vt + p - 1]; break; }
u = c.vt;
long long mot = tt[u].back(); // do dai MOT lan noi dung cua nhom
p = (p - 1) % mot + 1; // vi tri trong lan lap chua no
}
}
cout << out << "\n";
return 0;
}import sys
from bisect import bisect_left
def main():
data = sys.stdin.buffer.read().split()
S = data[0].decode()
q = int(data[1])
n = len(S)
khop = [-1] * n # khop[i] = vi tri ')' ung voi '(' o i
st = []
for i in range(n):
c = S[i]
if c == '(':
st.append(i)
elif c == ')':
khop[st.pop()] = i
# nut 0 = ca xau (he so 1); cha luon duoc tao truoc con
k = [1]; dau = [0]; cuoi = [n]
loai = [[]] # loai[u][j]: -1 neu con j la doan chu, nguoc lai la so hieu nhom con
vt = [[]] # vt[u][j]: vi tri bat dau doan chu (neu la doan chu)
dd = [[]] # dd[u][j]: do dai doan chu (neu la doan chu)
u = 0
while u < len(k):
i = dau[u]; e = cuoi[u]
L = loai[u]; V = vt[u]; D = dd[u]
while i < e:
c = S[i]
if 'a' <= c <= 'z':
j = i
while j < e and 'a' <= S[j] <= 'z':
j += 1
L.append(-1); V.append(i); D.append(j - i)
i = j
else: # doc so k roi den '('
j = S.index('(', i)
v = len(k)
k.append(int(S[i:j])); dau.append(j + 1); cuoi.append(khop[j])
loai.append([]); vt.append([]); dd.append([])
L.append(v); V.append(0); D.append(0)
i = khop[j] + 1
u += 1
m = len(k)
tt = [None] * m # tt[u][j] = tong do dai cac con 0..j-1 cua nut u
dai = [0] * m # do dai sau khi lap cua nut u
for u in range(m - 1, -1, -1):
t = [0]; s = 0
for j in range(len(loai[u])):
g = loai[u][j]
s += dd[u][j] if g < 0 else dai[g]
t.append(s)
tt[u] = t
dai[u] = k[u] * s
out = []
for idx in range(2, 2 + q):
p = int(data[idx])
u = 0
while True:
t = tt[u]
j = bisect_left(t, p) - 1 # con j: t[j] < p <= t[j + 1]
p -= t[j]
g = loai[u][j]
if g < 0:
out.append(S[vt[u][j] + p - 1])
break
u = g
p = (p - 1) % tt[u][-1] + 1 # vi tri trong lan lap chua no
sys.stdout.write("".join(out) + "\n")
main()long long. (2) Hệ số $k$ có thể có nhiều chữ số (tới $10^9$), đừng chỉ đọc một chữ số. (3) Lấy dư theo kiểu p = p % mot sẽ ra $0$ khi $p$ là chữ cuối của một lần lặp — phải dùng (p - 1) % mot + 1 (vị trí tính từ 1). Ví dụ của đề tình cờ không hỏi chữ cuối của lần lặp nào nên cả ba lỗi này đều vẫn ra đúng duochoc! (4) Python: đừng viết đệ quy sâu khi dựng cây/bung xâu với dữ liệu lớn — code mẫu dựng cây bằng vòng lặp.Bộ test chấm "bắt" những lỗi nào?
Bộ test có 36 test: Subtask 1 có 10 test ($T \le 10^6$: ví dụ, $|S| = 1$, 999999(a)b, nhóm cực rộng, cây ngẫu nhiên có cả $k$ lớn, $Q$ tới $10^5$), Subtask 2 có 8 test ($Q = 10$, $T$ tới đúng $10^{18}$, $k$ tới $10^9$, chuỗi nhóm lồng 30–50 tầng), Subtask 3 có 8 test ($Q = 1000$, nhóm lồng 25–34 tầng, trong cùng là một đoạn rất rộng: tính lại độ dài ở mỗi tầng là quá chậm), Subtask 4 có 10 test ($|S| \approx 1{,}4$–$1{,}9 \cdot 10^5$, $Q = 3 \cdot 10^5$; có nhóm có tới $7 \cdot 10^4$ con, có chuỗi 12 tầng mỗi tầng $6000$ con với nhóm lồng nằm ở cuối: duyệt lần lượt từng con là quá chậm). Câu hỏi gồm vị trí ngẫu nhiên, vị trí sát cuối băng rôn và đặc biệt là các vị trí "chữ cuối của một lần lặp". Điểm tính theo từng test (thang 100%).
| Cách làm | Sub 1 (10 test) | Sub 2 (8 test) | Sub 3 (8 test) | Sub 4 (10 test) | Điểm |
|---|---|---|---|---|---|
| Cách 1 – Bung cả băng rôn | Đúng 10/10 | Lỗi 0/8 | Lỗi 0/8 | Lỗi 0/10 | 15 |
| Cách 2 – Đi xuống, tính lại độ dài | Đúng 10/10 | Đúng 8/8 | TLE 0/8 | TLE 0/10 | 35 |
| Cách 3 – Tính trước độ dài, duyệt từng con | Đúng 10/10 | Đúng 8/8 | Đúng 8/8 | TLE 0/10 | 65 |
| Cách 4 – Thêm tìm kiếm nhị phân (chuẩn) | Đúng 10/10 | Đúng 8/8 | Đúng 8/8 | Đúng 10/10 | 100 |
Sai: độ dài kiểu int | Đúng 10/10 | Sai 0/8 | Sai 0/8 | Sai 0/10 | 15 |
| Sai: chỉ đọc một chữ số của $k$ | Sai 7/10 | Sai 0/8 | Sai 1/8 | Sai 0/10 | 14,2 |
Sai: p = p % mot (chia hết ra 0) | Sai 2/10 | Sai 2/8 | Sai 0/8 | Sai 0/10 | 8 |
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, các test còn lại băng rôn quá dài nên không bung được (tràn bộ nhớ); Cách 2 đúng 18/18 test của hai subtask đầu và quá thời gian (hơn 3 giây, có test hơn 8 giây) ở 18 test còn lại; Cách 3 đúng 26/26 test của ba subtask đầu và quá thời gian cả 10 test Subtask 4 (khoảng 4,5–5 giây mỗi test); Cách 4 đúng 36/36 test, test lâu nhất chạy khoảng 0,17 giây. Lời giải Python của Cách 4 cũng đúng 36/36 test, chạy tối đa khoảng 1,7 giây với CPython. Ví dụ của đề khá "hiền": mọi $k$ chỉ có một chữ số, băng rôn rất ngắn và không hỏi chữ cuối của lần lặp nào — nên cả ba lời giải sai ở bảng trên đều vẫn ra đúng duochoc, trong khi trên bộ test chúng chỉ được 8–15%. 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