Cuộc thi SF Round 4, kéo dài 4 giờ, đã khép lại. Giải đấu có sự tham gia của 5 thí sinh, trong đó không ai đạt điểm tuyệt đối (AK), nhưng cả 5 thí sinh đều có điểm số hợp lệ. Cuộc thi này, được tổ chức trước NOIP, có các bài toán tương đối dễ và tập trung vào các kiến thức đơn lẻ, chủ yếu kiểm tra khả năng tư duy và kỹ năng lập trình của thí sinh.
Bài toán A: SheKong ghét phương trình
Bài toán này tiếp nối truyền thống của các vòng SF: bài toán đầu tiên luôn là một bài mô phỏng lớn. Yêu cầu của đề bài là giải hai phương trình bậc nhất hai ẩn đã được "xử lý". Do đó, các bước chính để giải quyết bài toán này bao gồm: xử lý hệ số, xử lý biến số và thực hiện phép tính theo công thức.
Các điểm cần lưu ý:
- Khi hệ số là $\pm 1$, số 1 thường bị bỏ qua.
- Hệ số đầu tiên trong phương trình không có dấu cộng (+).
- Có thể có trường hợp một phương trình chỉ chứa một ẩn số.
- Thứ tự xuất hiện của các ẩn số trong hai phương trình có thể khác nhau.
- Đề bài nêu rõ: "Các số xuất hiện đều nằm trong phạm vi
int", tuy nhiên, trong quá trình tính toán có thể vượt quá giới hạn củaint. - Cần xử lý đặc biệt trường hợp $-0.000$ thành $0.000$.
- Chú ý đến các phương trình có cả hai hệ số đều là số âm.
Chi tiết hơn có thể tham khảo trong mã nguồn dưới đây:
// Author: SheKong
#include <cstdio>
#include <cstring>
#include <ctype.h>
long long getxs(char c, char s[]) {
int i, len = strlen(s), f = 1;
long long res = 0;
for (i = 0; i < len; i++) {
if (!isdigit(s[i])) {
if (s[i] == '-') f = -1;
else if (s[i] == '+') f = 1;
else if (s[i] == c) {
return res ? res * f : f;
} else res = 0;
} else res = res * 10 + s[i] - '0';
}
return 0;
}
long long getcs(char s[]) {
int i = 0, len = strlen(s), f = 1;
long long res = 0;
while (s[i] != '=') i++;
for (i++; i < len; i++) {
if (!isdigit(s[i]) && s[i] == '-') f = -1;
else res = res * 10 + s[i] - '0';
}
return res * f;
}
int main() {
char s1[50], s2[50], x1 = '0', x2 = '0';
scanf("%s%s", s1, s2);
long long xsx1, xsy1, xsx2, xsy2, cs1, cs2;
int i, len1 = strlen(s1), len2 = strlen(s2);
for (i = 0; i < len1; i++) {
if (s1[i] >= 'a' && s1[i] <= 'z') {
if (x1 == '0') x1 = s1[i];
else if (x2 == '0') x2 = s1[i];
}
}
for (i = 0; i < len2; i++) {
if (s2[i] >= 'a' && s2[i] <= 'z') {
if (x1 == '0') x1 = s2[i];
else if (s2[i] != x1 && x2 == '0') x2 = s2[i];
}
}
xsx1 = getxs(x1, s1), xsy1 = getxs(x2, s1), cs1 = getcs(s1);
xsx2 = getxs(x1, s2), xsy2 = getxs(x2, s2), cs2 = getcs(s2);
long double a1 = xsx1, a2 = xsx2, b1 = xsy1, b2 = xsy2, c1 = cs1, c2 = cs2, x, y;
if (a1 * b2 - a2 * b1 != 0) x = (c1 * b2 - c2 * b1) / (a1 * b2 - a2 * b1);
if ((c1 * b2 - c2 * b1) == 0 && (a1 * b2 - a2 * b1) == 0) x = 0;
if (b1 != 0) y = (c1 - a1 * x) / b1;
else y = (c2 - a2 * x) / b2;
printf("%c=%.3Lf\n%c=%.3Lf", x1, x == -0 ? 0 : x, x2, y == -0 ? 0 : y);
return 0;
}
Bài toán B: Học bổng (scholarship)
Lời nói đầu: Bối cảnh của bài toán này là có thật. Việc mua một mô hình figure đã "đốt sạch" toàn bộ học bổng thi lại ba lần của tôi.
40 điểm: Trong thời gian thi, tôi thực sự không nghĩ ra cách giải cho phần này nên đã đi thẳng vào hướng giải chính.
100 điểm: Bài toán yêu cầu chúng ta sử dụng phương pháp đệ quy. Lấy ví dụ với mẫu số 2 ($m=19$):
- Nếu có thể biểu diễn tất cả các số từ 1 đến 9, chỉ cần thêm số 10 là có thể biểu diễn tất cả các số từ 1 đến 19.
- Nếu có thể biểu diễn tất cả các số từ 1 đến 4, chỉ cần thêm số 5 là có thể biểu diễn tất cả các số từ 1 đến 9.
- Nếu có thể biểu diễn tất cả các số từ 1 đến 2, chỉ cần thêm số 2 là có thể biểu diễn tất cả các số từ 1 đến 4.
- Nếu có thể biểu diễn tất cả các số từ 1 đến 1, chỉ cần thêm số 1 là có thể biểu diễn tất cả các số từ 1 đến 2.
Từ ý tưởng trên, chúng ta có thể xây dựng phương án như trong ví dụ: $1, 1, 2, 5, 10$.
Áp dụng cho trường hợp $m$ là một số nguyên dương bất kỳ:
- Nếu có thể biểu diễn tất cả các số từ 1 đến $\lfloor \frac{n}{2} \rfloor$, chỉ cần thêm số $\lceil \frac{n}{2} \rceil$ là có thể biểu diễn tất cả các số từ 1 đến $n$.
- Tiếp tục đệ quy cho đến khi kết quả lấy phần nguyên lên sau khi chia đôi là 2 hoặc 3 (tương ứng với các cặp số nhỏ nhất là (1,1) và (1,2)).
Về mặt cài đặt, không cần sử dụng đệ quy. Chỉ cần lặp lại thao tác chia đôi và xuất kết quả theo thứ tự ngược lại.
Mã nguồn cốt lõi:
// Author: WalkerV
int m, cnt;
int a[50];
void Solve() {
while (m) {
a[++cnt] = abs((m + 1) / 2);
m /= 2;
}
printf("%d\n", cnt);
return;
}
Bài toán C: Di cư dân số
Xem thêm bài giải chất lượng cao hơn tại: [Hình dạng fractal ẩn trong Tháp Hà Nội] của 3Blue1Brown.
Bản chất của bài toán này là bài toán Tháp Hà Nội, nhưng chỉ được phép di chuyển giữa các cột liền kề. Ý tưởng chính của đề bài đã được trình bày trong video trên. (Đừng hỏi, tôi không muốn viết thêm).
Lưu ý rằng đáp án sẽ xuất hiện $3^n$, trong khi $n$ trong đề bài có thể lên tới $10^{18}$. Nếu chỉ sử dụng phương pháp tính thông thường $O(n)$ sẽ bị TLE (Time Limit Exceeded). Do đó, ở đây giới thiệu một thuật toán khác: lũy thừa nhanh (fast exponentiation), có thể tính toán với độ phức tạp $O(\log n)$.
Kết hợp ý tưởng trên và thuật toán, ta có mã nguồn AC (Accepted) cho bài toán này:
// Author: SheKong
#include <bits/stdc++.h>
long long MOD = 998244353;
inline long long abs(long long a) { return a < 0 ? -a : a; }
// Hàm tính lũy thừa nhanh (fast exponentiation)
long long qpow(long long b, long long k, long long p) {
long long ans = 1;
while (k > 0) {
if (k & 1) ans = ((ans % p) * (b % p)) % p;
k >>= 1;
b = ((b % p) * (b % p)) % p;
}
return ans;
}
int main() {
long long l, n, r, ans = 1, k = 3;
scanf("%lld %lld %lld", &l, &n, &r);
while (n) {
if (n & 1) ans = ans * k % MOD;
k = k * k % MOD;
n >>= 1;
}
// abs(r-l)==1 xử lý trường hợp đặc biệt của Tháp Hà Nội với 2 cột
printf("%lld", abs(r - l) == 1 ? (ans - 1 + MOD) * qpow(2, MOD - 2, MOD) % MOD : (ans - 1 + MOD) % MOD);
return 0;
}
Bài toán D: Biến động (flow)
Lời nói đầu: Bối cảnh của bài toán này được nảy ra trong trận mưa lớn ở Hà Nam, tôi xin dành bài toán này để vinh danh những người hùng chống lũ.
Số $19980928$ là ngày công bố chiến thắng toàn diện trong cuộc đấu tranh phòng chống và cứu trợ lũ lụt năm 1998.
10 điểm:
Theo đề bài, chúng ta có thể liệt kê tất cả các dãy số và kiểm tra xem chúng có thỏa mãn tính chất hay không. Độ phức tạp thời gian là $O(2^n \times n^3)$.
Mã nguồn cốt lõi:
// Author: WalkerV
#define MOD 19980928
int a[30];
long long n, ans;
void Check() {
int sum;
for (int k = 1; k <= n; k++) {
for (int m = k; m <= n; m++) {
sum = 0;
for (int i = k * 2 - 1; i <= m * 2; i++) {
sum += a[i];
}
if (sum < -2 || sum > 2) {
return;
}
}
}
ans++;
ans %= MOD;
return;
}
void Recur(int dep) {
if (dep == n * 2 + 1) {
Check();
return;
}
for (int i = 1; i <= 2; i++) {
if (i == 1) {
a[dep] = -1;
Recur(dep + 1);
} else {
a[dep] = 1;
Recur(dep + 1);
}
}
}
void Subtask1() {
Recur(1);
return;
}
30 điểm:
Theo đề bài, với mọi $i (1 \leq i \leq n)$, $x_{2i-1}$ và $x_{2i}$ hoặc giống nhau hoặc khác nhau. Chúng ta xem xét một dãy số ${ y_n }$ thỏa mãn $y_i = x_{2i-1} + x_{2i}$. Rõ ràng $y_i \in \{ -2, 0, 2 \}$. Điều kiện ban đầu $|\sum_{i=2k-1}^{2m} x_i| \leq 2$ tương đương với $|\sum_{i=k}^{m} y_i| \leq 2$.
Khi $y_i = \pm 2$, ta gọi $i$ là **điểm biến động**, ngược lại gọi là **điểm không biến động**. Theo điều kiện, nếu $i, j$ là hai điểm biến động liền kề, thì $y_i + y_j = 0$. Do đó, các giá trị tại điểm biến động phải xen kẽ giữa $-2$ và $2$ (tức là $y_i = -2, y_j = 2$ hoặc $y_i = 2, y_j = -2$). Vậy có hai trường hợp cho tất cả các điểm biến động (giá trị tại điểm biến động đầu tiên là $-2$ hoặc $2$, các điểm biến động tiếp theo sẽ được xác định).
Phân loại theo số lượng **điểm biến động** ($p$):
- $0$ **điểm biến động**: Với mỗi $y_i$ tương ứng với $(x_{2i-1}, x_{2i})$, có thể là $(-1,1)$ hoặc $(1,-1)$. Có $n$ vị trí, vậy có tổng cộng $2^n$ trường hợp.
- $p$ **điểm biến động** ($p \geq 1$): Chọn $p$ điểm trong tổng số $n$ điểm làm điểm biến động (có $C_n^p$ cách). Điểm biến động có 2 trường hợp. Với $(n-p)$ điểm còn lại không biến động, mỗi điểm tương ứng với $(x_{2i-1}, x_{2i})$ có thể là $(-1,1)$ hoặc $(1,-1)$, có $2^{n-p}$ cách. Tổng cộng có $C_n^p \times 2 \times 2^{n-p}$ trường hợp.
Kết hợp cả hai trường hợp, đáp án là $2^n + \sum_{p=1}^n (C_n^p \times 2 \times 2^{n-p})$.
Về mặt cài đặt, cần độ phức tạp thời gian $O(n^2)$ để tính toán tổ hợp.
60 điểm:
Với dãy số ${ x_{2n} }$ trong đề bài, định nghĩa **tổng tiền tố có độ dài $l$** là $S_l = \sum_{i=1}^l x_i$. Rõ ràng $S_{2i} \in \{ -2, 0, 2 \}$ ($1 \leq i \leq n$).
Chứng minh rằng, **với một dãy số thỏa mãn đề bài, không tồn tại hai số nguyên phân biệt $i,j$ ($1 \leq i,j \leq n$) sao cho $S_{2i}=2$ và $S_{2j}=-2$.**
Giả sử điều ngược lại là đúng, tức là với một dãy số thỏa mãn đề bài, tồn tại hai số nguyên phân biệt $i,j$ ($1 \leq i,j \leq n$) sao cho $S_{2i}=2$ và $S_{2j}=-2$.
- Khi $i
- Khi $i>j$, tương tự.
Do đó, bài toán có thể chia thành hai trường hợp:
- $S_{2i} \in \{ 0, 2 \}$ ($1 \leq i \leq n$)
- $S_{2i} \in \{ -2, 0 \}$ ($1 \leq i \leq n$)
Hai trường hợp này là tương đương, ta xem xét trường hợp đầu tiên.
Định nghĩa **trạng thái** $f(l, S_{2l})$ là số lượng các dãy ${ x_{2l} }$ thỏa mãn các điều kiện của đề bài, với $x_i \in \{-1, 1\}$ ($1 \leq i \leq 2l$) và $S_{2l} = S_{2l}$. Nói cách khác, đây là số cách xây dựng dãy từ đầu đến phần tử thứ $2l$ sao cho $S_{2l}$ là $S_{2l}$ và thỏa mãn yêu cầu đề bài.
Với định nghĩa trạng thái này, đáp án cho trường hợp đầu tiên là $f(n,0) + f(n,2)$, với $f(0,0)=1, f(0,2)=0$.
- Xem xét trạng thái $f(l,0)$. Một dãy có độ dài $2l$ và $S_{2l}=0$ có thể được tạo ra từ một dãy có độ dài $2(l-1)$ và $S_{2(l-1)}=0$ bằng cách thêm hai phần tử $1,-1$ hoặc $-1,1$; hoặc từ một dãy có độ dài $2(l-1)$ và $S_{2(l-1)}=2$ bằng cách thêm hai phần tử $-1,-1$.
- Xem xét trạng thái $f(l,2)$. Một dãy có độ dài $2l$ và $S_{2l}=2$ có thể được tạo ra từ một dãy có độ dài $2(l-1)$ và $S_{2(l-1)}=2$ bằng cách thêm hai phần tử $1,-1$ hoặc $-1,1$; hoặc từ một dãy có độ dài $2(l-1)$ và $S_{2(l-1)}=0$ bằng cách thêm hai phần tử $1,1$.
Do đó, **phương trình chuyển trạng thái** là:
- $f(l,0) = 2 \times f(l-1,0) + f(l-1,2)$
- $f(l,2) = f(l-1,0) + 2 \times f(l-1,2)$
Ta có thể tính toán từ $f(0,0), f(0,2)$.
Vì có hai trường hợp, nên nhân kết quả thu được với 2. Tuy nhiên, có một loại dãy số bị đếm hai lần: đó là các dãy có $S_{2i}=0$ ($1 \leq i \leq n$). Theo cách làm của phương pháp 30 điểm, có $2^n$ dãy như vậy. Do đó, đáp án cuối cùng là $2 \times [f(n,0)+f(n,2)] - 2^n$.
Về mặt cài đặt, ta sử dụng mảng hai chiều f để biểu diễn trạng thái, trong đó `f[l][0]` biểu thị $f(l,0)$ và `f[l][1]` biểu thị $f(l,2)$. Độ phức tạp thời gian là $O(n)$.
Lưu ý về độ phức tạp không gian là $O(n)$. Với 256MB có thể chứa khoảng $6 \times 10^7$ biến kiểu int, nên về mặt không gian sẽ không có vấn đề. Có thể tối ưu hóa mảng hai chiều f thành 4 biến kiểu int.
Mã nguồn cốt lõi:
// Author: WalkerV
#define MOD 19980928
#define N 10000010
long long n, ans;
long long f[N][2];
// Hàm tính lũy thừa nhanh
long long Quickpow(long long x, long long p, int mod) {
long long ret = 1;
if (p == 0) {
ret = 1 % mod;
return ret;
}
while (p) {
if (p % 2 == 1) {
ret *= x, ret %= mod;
}
x *= x, x %= mod;
p /= 2;
}
return ret;
}
void Subtask2() {
f[0][0] = 1, f[0][1] = 0;
for (int i = 1; i <= n; i++) {
f[i][0] = 2 * f[i - 1][0] + f[i - 1][1];
f[i][0] %= MOD;
f[i][1] = f[i - 1][0] + 2 * f[i - 1][1];
f[i][1] %= MOD;
}
ans = 2 * (f[n][0] + f[n][1]) - Quickpow(2, n, MOD);
ans %= MOD;
if (ans < 0) {
ans += MOD;
}
return;
}
100 điểm:
Cải tiến cho phương pháp 30 điểm:
Quan sát công thức thu được ở phương pháp 30 điểm: $2^n + \sum_{p=1}^n (C_n^p \times 2 \times 2^{n-p})$.
Thực hiện biến đổi sau:
$2^n + \sum_{p=1}^n (C_n^p \times 2 \times 2^{n-p}) = 2^n + 2 \times \sum_{p=1}^n (C_n^{n-p} \times 2^{n-p})$
Lưu ý rằng với phần $\sum_{p=1}^n (C_n^{n-p} \times 2^{n-p})$, sử dụng định lý nhị thức có thể biến đổi như sau:
$ \sum_{p=1}^n ( C_n^{n -p} \times 2^{n -p}) = \sum_{p=0}^n (C_n^{n -p} \times 1^p \times 2^{n -p}) -C_n^{n -0} \times 1^0 \times 2^{n -0} = (1+2)^n -2^n = 3^{n} -2^{n}$
Do đó, công thức tiếp tục biến đổi thành:
$2^n + 2 \times \sum_{p=1}^n (C_n^{n-p} \times 2^{n-p}) = 2^n + 2 \times (3^n -2^n) = 2 \times 3^{n} -2^{n}$
Vậy đáp án là $2 \times 3^{n} -2^{n}$.
Về mặt cài đặt, sử dụng **lũy thừa nhanh**, độ phức tạp thời gian là $O(\log n)$.
Mã nguồn cốt lõi:
// Author: WalkerV
#define MOD 19980928
long long n, ans;
// Hàm tính lũy thừa nhanh
long long Quickpow(long long x, long long p, int mod) {
long long ret = 1;
if (p == 0) {
ret = 1 % mod;
return ret;
}
while (p) {
if (p % 2 == 1) {
ret *= x, ret %= mod;
}
x *= x, x %= mod;
p /= 2;
}
return ret;
}
void Subtask3() {
ans = 2 * Quickpow(3, n, MOD) - Quickpow(2, n, MOD);
ans %= MOD;
if (ans < 0) {
ans += MOD;
}
return;
}
Cải tiến cho phương pháp 60 điểm:
Phương pháp 1: Phương pháp toán học
Liệt kê các giá trị đầu của $f(l, S_{2i})$:
| $i$ | $f(i,0)$ | $f(i,2)$ | $f(i,0)+f(i,2)$ |
|---|---|---|---|
| $0$ | $1$ | $0$ | $1$ |
| $1$ | $2$ | $1$ | $3$ |
| $2$ | $5$ | $4$ | $9$ |
| $3$ | $14$ | $13$ | $27$ |
| $4$ | $41$ | $40$ | $81$ |
Từ bảng trên, ta có thể đưa ra phỏng đoán:
- $f(i,0)+f(i,2)=3^i$
Chứng minh $f(i,0)+f(i,2)=3^i$:
- Khi $i=0$, $f(0,0)+f(0,2)=3^0$.
- Giả sử mệnh đề đúng khi $i=k$ ($k \geq 1$), tức là $f(k,0)+f(k,2)=3^k$.
- Khi $i=k+1$, $f(k+1,0)+f(k+1,2) = [2 \times f(k,0)+f(k,2)] + [2 \times f(k,2)+f(k,0)]$ $= 3 \times [f(k,0)+f(k,2)]$ $= 3 \times 3^k = 3^{k+1}$
Do đó, mệnh đề được chứng minh.
Vậy đáp án là $2 \times 3^{n} -2^{n}$.
Cài đặt tương tự như phần cải tiến cho phương pháp 30 điểm.
Phương pháp 2: Lũy thừa ma trận (Matrix Exponentiation)
Sử dụng **lũy thừa ma trận**, có thể tối ưu hóa độ phức tạp thời gian của phương pháp 60 điểm xuống $O(\log n)$.
Mã nguồn cài đặt:
// Author: yussgrw
#include <cstdio>
#include <cstring>
const int P = 19980928;
struct Matrix {
int m[3][3];
int r, c;
Matrix() { memset(m, 0, sizeof(m)); }
};
Matrix operator*(Matrix x, Matrix y) {
int i, j, k;
Matrix res;
for (i = 1; i <= x.r; i++) {
for (j = 1; j <= y.c; j++) {
for (k = 1; k <= x.c; k++) {
res.m[i][j] = (res.m[i][j] + (long long)x.m[i][k] * y.m[k][j]) % P;
}
}
}
res.r = x.r;
res.c = y.c;
return res;
}
Matrix quickpow(Matrix x, long long y) {
Matrix res;
res.r = res.c = 2;
res.m[1][1] = res.m[2][2] = 1;
while (y) {
if (y & 1) {
res = res * x;
}
x = x * x;
y >>= 1;
}
return res;
}
// Hàm tính lũy thừa nhanh cho số nguyên
int quickpow(int x, long long y) {
int res = 1;
while (y) {
if (y & 1) {
res = (long long)res * x % P;
}
x = (long long)x * x % P;
y >>= 1;
}
return res;
}
int main() {
Matrix res, x;
res.r = 2;
res.c = 1;
res.m[1][1] = 1; // Giá trị ban đầu f(0,0)
x.r = x.c = 2;
x.m[1][1] = x.m[2][2] = 2; // Hệ số của f(i-1,0) và f(i-1,2) trong phương trình chuyển trạng thái
x.m[1][2] = x.m[2][1] = 1;
long long N;
scanf("%lld", &N);
// Tính (quickpow(x, N) * res) để có f(N,0) và f(N,2)
res = quickpow(x, N) * res;
// Đáp án là 2 * (f(N,0) + f(N,2)) - 2^N
int ans = (((res.m[1][1] + res.m[2][1]) * 2 - quickpow(2, N)) % P + P) % P;
printf("%d\n", ans);
return 0;
}
Lời kết
Là bài toán cuối cùng của SF Round 4, tôi muốn thông qua bài toán này để mọi người lĩnh hội một số **kinh nghiệm giải bài toán trong OI (Olympic Tin học)**:
- Trong một bài toán OI, thường có nhiều mức **điểm phần thưởng**. Hãy xác định **độ phức tạp** của thuật toán tương ứng với **quy mô dữ liệu** của từng phần thưởng, từ đó đoán thuật toán cần sử dụng.
- Khi không thể tìm ra **lời giải chính** ngay lập tức, hãy bắt đầu từ **điểm phần thưởng**. Rất nhiều khi lời giải chính là sự tối ưu hóa hoặc cải tiến của thuật toán cho điểm phần thưởng.
- Trong OI, **không cần** chứng minh toán học quá chặt chẽ, nhưng điều đó không có nghĩa là không cần nền tảng toán học. Thực tế, **nền tảng toán học** là một trong những rào cản mà nhiều thí sinh gặp phải khi muốn nâng cao trình độ.
- **Liệt kê/Thử duyệt** luôn hữu ích. Trong OI, điều này không chỉ có nghĩa là liệt kê các dãy số như bài này, mà còn có thể mở rộng ra việc kiểm tra thủ công trên **dữ liệu quy mô nhỏ**. Điều này có lợi cho **hiểu đề bài** và **tìm ra hướng đột phá**.
- Hãy thử **tiếp cận bài toán từ nhiều góc độ**. Mặc dù các lời giải khác nhau cho một bài toán về bản chất là giống nhau, nhưng trong OI không thiếu những bài toán có thể giải quyết từ những cách tiếp cận hoàn toàn khác nhau. Tương tự như bài toán này, nó sử dụng hai ý tưởng cơ bản là **kiến thức toán học** và **quy hoạch động**.