Đổi chỗ (Đề tự luyện HSG Tin quốc gia – Bài 1)
Đề bài
Đổi chỗ
Sân có $N$ ô, lớp có $N$ bạn; lúc đầu bạn $i$ đứng ở ô $i$. Tờ hướng dẫn là một hoán vị $p_1, p_2, \ldots, p_N$: mỗi tiếng còi, bạn đang đứng ở ô $i$ chạy sang ô $p_i$. Gọi $T$ là số tiếng còi dương nhỏ nhất để mọi bạn cùng về chỗ cũ.
Có $Q$ ý tưởng chụp ảnh, ý tưởng thứ $j$ gồm $k_j$ yêu cầu "bạn $a$ đứng ở ô $b$". Với mỗi ý tưởng, in số tiếng còi ít nhất (có thể là $0$) để mọi yêu cầu cùng đúng, hoặc $-1$ nếu không bao giờ xảy ra. Các ý tưởng độc lập, đều tính từ lúc bắt đầu.
Dữ liệu vào: dòng đầu $N, Q$ $(1 \le N, Q \le 2\cdot 10^5)$; dòng hai là $p_1, \ldots, p_N$; $Q$ dòng sau, mỗi dòng $k_j$ rồi $2k_j$ số $a_1, b_1, a_2, b_2, \ldots$ Tổng các $k_j$ không quá $2\cdot 10^5$. Bảo đảm $T \le 10^{18}$.
Kết quả: $Q$ dòng, mỗi dòng một số.
- Subtask 1 (15%): $N \le 12$, $Q \le 10$.
- Subtask 2 (20%): $k_j = 1$ với mọi $j$.
- Subtask 3 (30%): $Q \le 10$.
- Subtask 4 (35%): 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.
12 5
5 7 12 2 9 10 11 3 1 8 4 6
1 3 6
2 1 9 11 7
4 5 5 2 4 8 10 12 3
1 1 2
2 6 6 9 92
11
39
-1
0Các bạn chạy theo $1 \to 5 \to 9 \to 1$, $2 \to 7 \to 11 \to 4 \to 2$, $3 \to 12 \to 6 \to 10 \to 8 \to 3$. Ý tưởng 2: bạn 1 ở ô 9 sau $2, 5, 8, 11, \ldots$ tiếng còi, bạn 11 ở ô 7 sau $3, 7, 11, \ldots$ tiếng còi, lần đầu trùng là $11$. Ý tưởng 4: bạn 1 không bao giờ tới ô 2. Ý tưởng 5: chụp ngay.
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 Đổi chỗLời mở đầu
Thử đi theo một bạn: bạn $3$ đứng ở ô $3$, sau một tiếng còi sang ô $p_3 = 12$, rồi ô $p_{12} = 6$, rồi $10$, $8$, rồi lại về ô $3$. Bạn ấy cứ đi vòng quanh đúng 5 ô $3 \to 12 \to 6 \to 10 \to 8 \to 3$ mãi mãi. Đây là tính chất quen thuộc của hoán vị: các ô tách thành những vòng (chu trình) rời nhau, và mỗi bạn chỉ chạy quanh vòng chứa ô ban đầu của mình.
Ví dụ đề: hoán vị gồm ba vòng độ dài 3, 4, 5. Mỗi yêu cầu biến thành một phương trình đồng dư.
Đánh số các ô trên mỗi vòng theo chiều chạy: idx[v] là vị trí của ô $v$ trên vòng của nó, len là độ dài vòng. Sau $t$ tiếng còi, bạn $a$ đứng ở ô cách ô $a$ đúng $t$ bước theo chiều chạy. Vậy:
Cái khó: các modulo là độ dài các vòng, chúng không nhất thiết nguyên tố cùng nhau (ví dụ hai vòng dài $4$ và $6$). Công thức thặng dư Trung Hoa "trong sách" chỉ dùng được khi các modulo đôi một nguyên tố cùng nhau, nên ta phải dùng bản mở rộng.
Lộ trình:
Cách 1Mô phỏng từng tiếng còi – O(T·N) mỗi ý tưởng · 15%
Làm đúng như đề: giữ mảng at[x] = ô bạn $x$ đang đứng. Ở mỗi thời điểm $t = 0, 1, 2, \ldots$ kiểm tra mọi yêu cầu; nếu chưa đúng thì "thổi còi": at[x] = p[at[x]] cho mọi $x$. Khi mọi bạn đã về chỗ cũ (tức là $t = T$) mà vẫn chưa gặp thời điểm tốt thì sẽ không bao giờ gặp nữa – trạng thái lặp lại y hệt – in $-1$.
Với $N \le 12$ thì $T \le 60$ (lớn nhất khi các vòng dài $3, 4, 5$), chạy tức thì. Nhưng ở các subtask sau $T$ có thể tới $10^{18}$.
#include <bits/stdc++.h>
using namespace std;
// Cach 1: mo phong tung tieng coi cho toi khi moi ban ve cho cu
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<int> p(n + 1);
for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
vector<int> at(n + 1); // at[x] = o ban x dang dung
while (q--) {
int k;
scanf("%d", &k);
vector<int> a(k), b(k);
for (int i = 0; i < k; i++) scanf("%d %d", &a[i], &b[i]);
for (int i = 1; i <= n; i++) at[i] = i;
long long t = 0, ans = -1;
while (true) {
bool good = true;
for (int i = 0; i < k; i++)
if (at[a[i]] != b[i]) { good = false; break; }
if (good) { ans = t; break; }
for (int i = 1; i <= n; i++) at[i] = p[at[i]]; // thoi mot tieng coi
t++;
bool home = true; // da quay ve trang thai ban dau?
for (int i = 1; i <= n; i++)
if (at[i] != i) { home = false; break; }
if (home) break;
}
printf("%lld\n", ans);
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
p = [0] + [int(x) for x in data[2:2 + n]]
pos = 2 + n
out = []
for _ in range(q):
k = int(data[pos]); pos += 1
a = []; b = []
for _ in range(k):
a.append(int(data[pos])); b.append(int(data[pos + 1])); pos += 2
at = list(range(n + 1)) # at[x] = o ban x dang dung
home = list(range(n + 1))
t = 0; ans = -1
while True:
good = True
for i in range(k):
if at[a[i]] != b[i]:
good = False
break
if good:
ans = t
break
for i in range(1, n + 1): # thoi mot tieng coi
at[i] = p[at[i]]
t += 1
if at == home: # moi ban da ve cho cu
break
out.append(str(ans))
sys.stdout.write("\n".join(out) + "\n")
main()Cách 2Tách vòng – trả lời ngay khi k = 1 · 35%
Duyệt $i = 1..N$; gặp ô chưa thuộc vòng nào thì đi theo $i \to p_i \to p_{p_i} \to \ldots$ cho tới khi quay lại, gán cho các ô trên đường đi cùng số hiệu vòng cyc và vị trí idx = 0, 1, 2, .... Mỗi ô được thăm đúng một lần nên mất $O(N)$.
Khi ý tưởng chỉ có một yêu cầu $(a, b)$: nếu cyc[a] != cyc[b] thì in $-1$, ngược lại đáp án chính là số bước từ $a$ tới $b$ trên vòng: $(\text{idx}[b] - \text{idx}[a]) \bmod L$ (nhớ cộng thêm $L$ trước khi lấy dư vì hiệu có thể âm). Với ví dụ: bạn $3$ có idx $= 0$, ô $6$ có idx $= 2$ trên vòng C nên đáp án ý tưởng 1 là $2$.
Các ý tưởng có $k > 1$ thì vẫn mô phỏng như Cách 1 (để giữ điểm subtask 1).
#include <bits/stdc++.h>
using namespace std;
// Cach 2: tach vong; k = 1 thi dap an la khoang cach tren vong, con lai mo phong nhu Cach 1
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<int> p(n + 1), cyc(n + 1, 0), idx(n + 1), len(n + 1);
for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
int c = 0;
for (int i = 1; i <= n; i++) {
if (cyc[i]) continue;
c++;
int v = i, k = 0;
while (!cyc[v]) { cyc[v] = c; idx[v] = k++; v = p[v]; }
len[c] = k;
}
vector<int> at(n + 1);
while (q--) {
int k;
scanf("%d", &k);
vector<int> a(k), b(k);
for (int i = 0; i < k; i++) scanf("%d %d", &a[i], &b[i]);
if (k == 1) {
if (cyc[a[0]] != cyc[b[0]]) printf("-1\n");
else {
int L = len[cyc[a[0]]];
printf("%d\n", ((idx[b[0]] - idx[a[0]]) % L + L) % L);
}
continue;
}
for (int i = 1; i <= n; i++) at[i] = i;
long long t = 0, ans = -1;
while (true) {
bool good = true;
for (int i = 0; i < k; i++)
if (at[a[i]] != b[i]) { good = false; break; }
if (good) { ans = t; break; }
for (int i = 1; i <= n; i++) at[i] = p[at[i]];
t++;
bool home = true;
for (int i = 1; i <= n; i++)
if (at[i] != i) { home = false; break; }
if (home) break;
}
printf("%lld\n", ans);
}
return 0;
}import sys
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
p = [0] + [int(x) for x in data[2:2 + n]]
cyc = [0] * (n + 1); idx = [0] * (n + 1); ln = [0]
c = 0
for i in range(1, n + 1): # tach hoan vi thanh cac vong
if cyc[i]:
continue
c += 1
v = i; k = 0
while not cyc[v]:
cyc[v] = c; idx[v] = k; k += 1; v = p[v]
ln.append(k)
pos = 2 + n
out = []
for _ in range(q):
k = int(data[pos]); pos += 1
a = []; b = []
for _ in range(k):
a.append(int(data[pos])); b.append(int(data[pos + 1])); pos += 2
if k == 1:
if cyc[a[0]] != cyc[b[0]]:
out.append("-1")
else:
out.append(str((idx[b[0]] - idx[a[0]]) % ln[cyc[a[0]]]))
continue
at = list(range(n + 1)) # k > 1: mo phong nhu Cach 1
home = list(range(n + 1))
t = 0; ans = -1
while True:
good = True
for i in range(k):
if at[a[i]] != b[i]:
good = False
break
if good:
ans = t
break
for i in range(1, n + 1):
at[i] = p[at[i]]
t += 1
if at == home:
break
out.append(str(ans))
sys.stdout.write("\n".join(out) + "\n")
main()Cách 3Ghép từng phương trình bằng cách thử – O(N) mỗi ý tưởng · 65%
Giả sử sau khi xử lý vài yêu cầu, ta đã biết tập các $t$ hợp lệ là một lớp đồng dư $t \equiv r \pmod m$ (lúc đầu $r = 0$, $m = 1$: mọi $t$). Thêm yêu cầu mới $t \equiv r_2 \pmod L$. Các $t$ hợp lệ cũ là $r, r + m, r + 2m, \ldots$ – ta thử lần lượt xem số nào chia $L$ dư $r_2$.
- Phải thử bao nhiêu số? Gọi $g = \gcd(m, L)$. Số dư của $r + xm$ khi chia $L$ lặp lại với chu kỳ đúng $L/g$ theo $x$, nên chỉ cần thử $x = 0, 1, \ldots, L/g - 1$. Không gặp thì hệ vô nghiệm ⇒ $-1$.
- Gặp $x$ đầu tiên thì nghiệm mới là $t \equiv r + xm \pmod{\text{lcm}(m, L)}$, với $\text{lcm}(m, L) = m / g \cdot L$ (chia trước nhân sau để khỏi tràn).
Ví dụ ý tưởng 2: $t \equiv 2 \pmod 3$ và $t \equiv 3 \pmod 4$. Thử $2, 5, 8, 11$: số $11$ chia $4$ dư $3$ ⇒ $t \equiv 11 \pmod{12}$, đáp án $11$. Một ví dụ vô nghiệm: $t \equiv 1 \pmod 4$ và $t \equiv 2 \pmod 6$: thử $1, 5, 9$ (vì $6/\gcd(4,6) = 3$), chia $6$ dư $1, 5, 3$ – không có $2$. Thật vậy, vế đầu bắt $t$ lẻ, vế sau bắt $t$ chẵn.
Với yêu cầu đầu tiên ($m = 1$) ta gán luôn $r = r_2, m = L$ khỏi phải thử. Mỗi yêu cầu sau tốn tối đa $L/g \le L \le N$ bước, nên một ý tưởng tốn $O(N)$ (với các vòng khác nhau, tổng các $L/g$ không vượt quá $N$; yêu cầu thuộc vòng đã gặp thì $g = L$, chỉ 1 bước). Với $Q \le 10$ là đủ nhanh. Nhưng khi có hàng chục nghìn ý tưởng, mỗi ý tưởng hỏi hai bạn ở hai vòng dài $\approx 10^5$, ta phải thử tới hàng tỉ bước.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Cach 3: moi yeu cau cho t = r2 (mod L); ghep dan bang cach thu t = r, r + m, r + 2m, ...
int main() {
int n, q;
scanf("%d %d", &n, &q);
vector<int> p(n + 1), cyc(n + 1, 0), idx(n + 1), len(n + 1);
for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
int c = 0;
for (int i = 1; i <= n; i++) {
if (cyc[i]) continue;
c++;
int v = i, k = 0;
while (!cyc[v]) { cyc[v] = c; idx[v] = k++; v = p[v]; }
len[c] = k;
}
while (q--) {
int k;
scanf("%d", &k);
ll r = 0, m = 1; // dang biet: t = r (mod m)
bool ok = true;
for (int i = 0; i < k; i++) {
int a, b;
scanf("%d %d", &a, &b);
if (!ok) continue;
if (cyc[a] != cyc[b]) { ok = false; continue; }
ll L = len[cyc[a]];
ll r2 = ((idx[b] - idx[a]) % L + L) % L;
if (m == 1) { r = r2; m = L; continue; } // yeu cau dau tien
ll g = __gcd(m, L), steps = L / g; // sau L/g buoc, t mod L lap lai
bool found = false;
for (ll x = 0; x < steps; x++) {
if ((r + m * x) % L == r2) { r += m * x; found = true; break; }
}
if (!found) { ok = false; continue; }
m = m / g * L; // m moi = lcm(m, L)
}
printf("%lld\n", ok ? r : -1LL);
}
return 0;
}import sys
from math import gcd
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
p = [0] + [int(x) for x in data[2:2 + n]]
cyc = [0] * (n + 1); idx = [0] * (n + 1); ln = [0]
c = 0
for i in range(1, n + 1):
if cyc[i]:
continue
c += 1
v = i; k = 0
while not cyc[v]:
cyc[v] = c; idx[v] = k; k += 1; v = p[v]
ln.append(k)
pos = 2 + n
out = []
for _ in range(q):
k = int(data[pos]); pos += 1
r = 0; m = 1 # dang biet: t = r (mod m)
ok = True
for _ in range(k):
a = int(data[pos]); b = int(data[pos + 1]); pos += 2
if not ok:
continue
if cyc[a] != cyc[b]:
ok = False
continue
L = ln[cyc[a]]
r2 = (idx[b] - idx[a]) % L
if m == 1: # yeu cau dau tien
r = r2; m = L
continue
g = gcd(m, L)
t = r; found = False
for _ in range(L // g): # thu t = r, r + m, r + 2m, ...
if t % L == r2:
found = True
break
t += m
if not found:
ok = False
continue
r = t
m = m // g * L # m moi = lcm(m, L)
out.append(str(r) if ok else "-1")
sys.stdout.write("\n".join(out) + "\n")
main()long long. Nhưng nếu tính lcm theo kiểu m * L / g thì tích m * L có thể vượt $9{,}2\cdot 10^{18}$ – phải viết m / g * L.Cách 4Thặng dư Trung Hoa mở rộng – O(log N) mỗi yêu cầu · 100%
Thay vì thử từng $x$, ta giải luôn phương trình: cần $x$ sao cho $$r + m x \equiv r_2 \pmod L \iff m x \equiv r_2 - r \pmod L.$$ Đặt $g = \gcd(m, L)$ và $\Delta = r_2 - r$.
- Nếu $g \nmid \Delta$ thì vô nghiệm (vế trái luôn chia hết cho $g$, vế phải thì không) ⇒ in $-1$.
- Ngược lại chia cả ba (hai vế và modulo) cho $g$: $\frac{m}{g} x \equiv \frac{\Delta}{g} \pmod{\frac{L}{g}}$. Bây giờ $\frac{m}{g}$ và $\frac{L}{g}$ nguyên tố cùng nhau nên $\frac{m}{g}$ có nghịch đảo theo modulo $\frac{L}{g}$ (tìm bằng thuật toán Euclid mở rộng), và $$x \equiv \frac{\Delta}{g} \cdot \left(\frac{m}{g}\right)^{-1} \pmod{\frac{L}{g}}.$$
- Lấy $x$ nhỏ nhất trong $[0, L/g)$, cập nhật $r \leftarrow r + m x$, $m \leftarrow m \cdot \frac{L}{g} = \text{lcm}(m, L)$. Vì $x < L/g$ nên $r$ mới vẫn $< \text{lcm}(m, L)$: đây đúng là nghiệm nhỏ nhất của hai phương trình, giống hệt số mà Cách 3 tìm thấy.
Ví dụ ý tưởng 3: $t \equiv 0 \pmod 3$; thêm $t \equiv 3 \pmod 4$: $g = 1$, $3x \equiv 3 \pmod 4$ ⇒ $x = 1$, được $t \equiv 3 \pmod{12}$. Thêm $t \equiv 4 \pmod 5$: $12 x \equiv 1 \pmod 5$, nghịch đảo của $12 \equiv 2$ theo modulo $5$ là $3$ ⇒ $x = 3$, được $t \equiv 39 \pmod{60}$. Yêu cầu cuối (bạn 12) cũng là $t \equiv 4 \pmod 5$: $g = 5$, $\Delta = 4 - 39 \bmod 5 = 0$ chia hết, $L/g = 1$ nên $x = 0$, không đổi. Đáp án $39$.
- Dùng CRT "chuẩn" (coi các modulo nguyên tố cùng nhau, nhân thẳng $m \cdot L$): sai ngay khi hai vòng có ước chung, ví dụ dài $4$ và $6$.
- Quên kiểm tra $g \mid \Delta$: có ý tưởng vô nghiệm (hai yêu cầu cùng vòng mâu thuẫn, hoặc mâu thuẫn "chẵn – lẻ" giữa hai vòng) mà vẫn in ra một số.
- Tràn số: chỉ nhân sau khi đã rút gọn. Ở code dưới, $d < L/g$ và nghịch đảo $< L/g \le 2\cdot 10^5$ nên tích $< 4\cdot 10^{10}$; còn $r + m x < \text{lcm} \le T \le 10^{18}$.
Mỗi yêu cầu chỉ tốn một lần $\gcd$ và một lần Euclid mở rộng, tức $O(\log N)$. Tổng độ phức tạp $O(N + \sum k \log N)$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll inverse(ll a, ll m) { // nghich dao cua a theo modulo m (gcd(a, m) = 1)
ll r0 = a, r1 = m, x0 = 1, x1 = 0; // Euclid mo rong, viet lap
while (r1 != 0) {
ll q = r0 / r1, t;
t = r0 - q * r1; r0 = r1; r1 = t;
t = x0 - q * x1; x0 = x1; x1 = t;
}
return (x0 % m + m) % m;
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> p(n + 1), cyc(n + 1, 0), idx(n + 1), len(n + 1);
for (int i = 1; i <= n; i++) cin >> p[i];
int c = 0;
for (int i = 1; i <= n; i++) { // tach hoan vi thanh cac vong
if (cyc[i]) continue;
c++;
int v = i, k = 0;
while (!cyc[v]) { cyc[v] = c; idx[v] = k++; v = p[v]; }
len[c] = k;
}
while (q--) {
int k;
cin >> k;
ll r = 0, m = 1; // da biet: t = r (mod m)
bool ok = true;
for (int j = 0; j < k; j++) {
int a, b;
cin >> a >> b;
if (!ok) continue;
if (cyc[a] != cyc[b]) { ok = false; continue; }
ll L = len[cyc[a]];
ll r2 = ((idx[b] - idx[a]) % L + L) % L; // can them: t = r2 (mod L)
ll g = __gcd(m, L);
ll diff = r2 - r % L; // |diff| < L
if (diff % g != 0) { ok = false; continue; }
ll Lg = L / g;
ll d = ((diff / g) % Lg + Lg) % Lg;
ll x = d * inverse((m / g) % Lg, Lg) % Lg; // m*x = diff (mod L)
r += m * x; // r < lcm(m, L) <= T
m *= Lg; // m = lcm(m, L)
}
cout << (ok ? r : -1) << "\n";
}
return 0;
}import sys
from math import gcd
def main():
data = sys.stdin.buffer.read().split()
n = int(data[0]); q = int(data[1])
p = [0] * (n + 1)
for i in range(1, n + 1):
p[i] = int(data[1 + i])
cyc = [0] * (n + 1) # cyc[v]: so hieu vong chua v
idx = [0] * (n + 1) # idx[v]: vi tri cua v trong vong
ln = [0] # ln[c]: do dai vong c
c = 0
for i in range(1, n + 1):
if cyc[i]:
continue
c += 1
v = i; k = 0
while not cyc[v]:
cyc[v] = c; idx[v] = k; k += 1; v = p[v]
ln.append(k)
out = []
pos = n + 2
for _ in range(q):
k = int(data[pos]); pos += 1
r = 0; m = 1 # dang biet: t = r (mod m)
ok = True
for _ in range(k):
a = int(data[pos]); b = int(data[pos + 1]); pos += 2
if not ok:
continue
ca = cyc[a]
if ca != cyc[b]:
ok = False
continue
L = ln[ca]
r2 = (idx[b] - idx[a]) % L
g = gcd(m, L)
diff = r2 - r % L
if diff % g:
ok = False
continue
Lg = L // g
if Lg == 1:
continue
d = (diff // g) % Lg
# nghich dao cua (m/g) theo modulo Lg bang Euclid mo rong (viet lap)
r0 = (m // g) % Lg; r1 = Lg; x0 = 1; x1 = 0
while r1:
qq = r0 // r1
tmp = r0 - qq * r1; r0 = r1; r1 = tmp
tmp = x0 - qq * x1; x0 = x1; x1 = tmp
x = d * (x0 % Lg) % Lg
r += m * x
m *= Lg
out.append(str(r) if ok else "-1")
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 (30%) | Sub 4 (35%) | Điểm |
|---|---|---|---|---|---|
| Cách 1 – Mô phỏng từng tiếng còi | Đúng | TLE | TLE | TLE | 15 |
| Cách 2 – Tách vòng, trả lời ngay khi k = 1 | Đúng | Đúng | TLE | TLE | 35 |
| Cách 3 – Ghép đồng dư bằng cách thử từng bước | Đúng | Đúng | Đúng | TLE | 65 |
| Cách 4 – Thặng dư Trung Hoa mở rộng (sol.cpp) | Đúng | Đúng | Đúng | Đúng | 100 |
| Sai: CRT "chuẩn", coi các độ dài vòng nguyên tố cùng nhau | 3/11 | 8/8 | 0/8 | 0/9 | 24,1 |
Sai: đúng ý tưởng nhưng tính lcm bằng m * L / g (tràn số) | 11/11 | 8/8 | 0/8 | 4/9 | 50,6 |
Sai: quên kiểm tra diff % g == 0 | 3/11 | 8/8 | 1/8 | 0/9 | 27,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: bộ test có 36 test (11 + 8 + 8 + 9), mỗi cách ở trên đạt đúng số điểm công bố, còn ba lời giải sai bị bắt như bảng trên. Lời giải chuẩn sol.cpp chạy test lâu nhất hết khoảng 0,3 giây; bản Python sol.py cho cùng đáp án trên mọi test (trên CPython mất chưa tới 3 giây, các em nhớ chọn PyPy 3 khi nộp). Cách 3 ở subtask 4 chạy hơn một phút mỗi test vì phải thử hàng tỉ bước. "TLE" nghĩa là chạy quá 3 lần giới hạn thời gian. Lỗi tràn số chỉ lộ ra khi bội chung nhỏ nhất của các vòng lên tới cỡ $10^{17}$ – $10^{18}$, nên ở subtask 2 (mỗi ý tưởng một yêu cầu) nó vẫn "ăn" trọn điểm – đừng để mất điểm oan như vậy nhé!
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