ICPC Regional Hanoi 2024 Editorial

Lời giải hai bài rất khó I và E trong đề.

I: Inversland

Đề bài

Cho $n$ mệnh giá tiền, mệnh giá tiền thứ $i$ là $\frac{1}{p_{i}}$ với $p_i$ là số nguyên tố. Đếm số lượng giá trị hữu tỉ có thể trả được bằng các mệnh giá tiền này mà người bán bắt buộc phải trả lại tiền thừa, modulo $998244353$ .

Lời giải

Ta phát biểu lại bài toán từ các mệnh giá hữu tỉ về các mệnh giá nguyên mà không mất tính tổng quát: Gọi $P$ là tích của tất cả các $p_i$ . Nhân mọi mệnh giá với $P$ thì mệnh giá thứ $i$ trở thành số nguyên $a_i=P/p_i$ . Trong bối cảnh bài toán này ta nói một số tiền $x$ nguyên là biểu diễn được nếu nó có thể biểu diễn bằng tổ hợp tuyến tính hệ số không âm của các giá trị $a_{i}$ , tức là $x=\sum_{i=1}^{n}c_{i}a_{i}$ với $c_{i}\ge0$ . Đáp án là số lượng giá trị không biểu diễn được.

Trước tiên ta phát biểu một số kết quả toán học cần thiết để chứng minh lời giải của bài toán này:

Định lý Bezout cho

n

số

Phát biểu:

Với mọi tập gồm $n$ số nguyên $a_1, a_2, \dots, a_n$ ( $n \ge 2$ ), luôn tồn tại bộ số nguyên $x_1, x_2, \dots, x_n$ sao cho:

\sum_{i=1}^n a_i x_i = \gcd(a_1, a_2, \dots, a_n)

Chứng minh:

Ta chứng minh bằng quy nạp. Trường hợp cơ sở với $n=2$ là bổ đề Bezout^[2] đã được chứng minh.

Giả sử định lý đúng với $k \ge 2$ . Nghĩa là với mọi bộ $k$ số nguyên $a_1, a_2, \dots, a_k$ , đặt $d_k = \gcd(a_1, a_2, \dots, a_k)$ , luôn tồn tại bộ số nguyên $x_1, x_2, \dots, x_k$ thỏa mãn: $a_1 x_1 + a_2 x_2 + \dots + a_k x_k = d_k$ . Ta chứng minh mệnh đề đúng với $k+1$ .

Theo tính chất kết hợp của hàm gcd ta có

\gcd(a_1, a_2, \dots, a_k, a_{k+1}) = \gcd\Big(\gcd(a_1, a_2, \dots, a_k), \; a_{k+1}\Big) = \gcd(d_k, a_{k+1})

Áp dụng Bổ đề Bézout cho 2 số $d_k$ và $a_{k+1}$ , tồn tại hai số nguyên $u, v$ sao cho:

u \cdot d_k + v \cdot a_{k+1} = \gcd(d_k, a_{k+1})

Thay $d_k = \sum_{i=1}^k a_i x_i$ từ giả thiết quy nạp vào phương trình trên:

u \left( \sum_{i=1}^k a_i x_i \right) + v \cdot a_{k+1} = \gcd(a_1, a_2, \dots, a_{k+1})

Khai triển và nhóm lại:

\sum_{i=1}^k a_i (u \cdot x_i) + a_{k+1} \cdot v = \gcd(a_1, a_2, \dots, a_{k+1})

Vì $u, v$ và các $x_i$ đều là số nguyên, nên $x'_i = u \cdot x_i$ (với $1 \le i \le k$ ) và $x'_{k+1} = v$ cũng là các số nguyên. Do đó, ta đã biểu diễn được $\gcd(a_1, \dots, a_{k+1})$ dưới dạng tổ hợp tuyến tính nguyên của $k+1$ số $a_1, \dots, a_{k+1}$ . Theo nguyên lý quy nạp ta có điều phải chứng minh.

Số Frobenius

Số Frobenius (ký hiệu $F(a_1, a_2, \dots, a_n)$ ) của một tập các số nguyên dương $a_1, a_2, \dots, a_n$ (với điều kiện $\gcd(a_1, a_2, \dots, a_n) = 1$ ) là số nguyên lớn nhất không thể biểu diễn dưới dạng tổ hợp tuyến tính không âm của các số đó. Mô tả bằng công thức: $F$ là số nguyên lớn nhất sao cho phương trình:

c_1 a_1 + c_2 a_2 + \dots + c_n a_n = F

không có nghiệm nguyên không âm ( $c_i \in \mathbb{Z}_{\ge 0}$ ). Ngược lại, với mọi số nguyên $m > F$ , phương trình $c_1 a_1 + \dots + c_n a_n = m$ luôn có ít nhất một bộ nghiệm $c_i \ge 0$ .

Định lý Schur-Frobenius

Phát biểu: Cho $n$ số nguyên dương $a_1, a_2, \dots, a_n$ ( $n \ge 2$ ) nguyên tố cùng nhau. Khi đó, tồn tại một ngưỡng số nguyên $N$ sao cho với mọi số nguyên $m \ge N$ , phương trình Diophantine:

c_1 a_1 + c_2 a_2 + \dots + c_n a_n = m

luôn có ít nhất một bộ nghiệm nguyên không âm $(c_1, c_2, \dots, c_n \in \mathbb{Z}_{\ge 0})$ .

Chứng minh:

Vì $\gcd(a_1, a_2, \dots, a_n) = 1$ , theo Định lý Bézout, luôn tồn tại các số nguyên $u_1, u_2, \dots, u_n$ (có thể âm) sao cho $1 = u_1 a_1 + u_2 a_2 + \dots + u_n a_n$ .

Xét một số dư $r$ bất kỳ trong tập $\{0, 1, 2, \dots, a_1 - 1\}$ . Nhân cả 2 vế của phương trình trên với $r$ :

r = (r \cdot u_1) a_1 + (r \cdot u_2) a_2 + \dots + (r \cdot u_n) a_n

Lấy modulo hai vế cho $a_1$ , ta thu được:

r \equiv (r \cdot u_2) a_2 + \dots + (r \cdot u_n) a_n \pmod{a_1}

Các hệ số $(r \cdot u_i)$ ở trên có thể bị âm. Nếu hệ số nào bị âm, ta chỉ cần cộng thêm vào hệ số đó một lượng $k \cdot a_1$ (chọn $k$ đủ lớn để hệ số trở thành số dương) mà không làm thay đổi số dư khi chia tổng trên cho $a_1$ . Nhờ đó, với mỗi số dư $r$ , ta luôn tìm được một số $M_r \ge 0$ được tạo thành từ tổ hợp không âm của $(a_2, \dots, a_n)$ sao cho $M_r \equiv r \pmod{a_1}$ . Với $a_1$ số dư khả dĩ $\left(0,1,\dots,a_1-1\right)$ , ta thu được $a_1$ giá trị $\{M_0, M_1, \dots, M_{a_1-1}\}$ .

Đặt $N = \max(M_0, M_1, \dots, M_{a_1-1})$ . Lấy một số $m \ge N$ bất kỳ. Giả sử $m$ chia $a_1$ dư $r$ :

Do $m$ và $M_r$ có cùng số dư khi chia cho $a_1$ , hiệu $(m - M_r)$ chia hết cho $a_1$ .
Do $m \ge N \ge M_r$ , ta có $(m - M_r) \ge 0$ . Khi này ta có thể viết $m = q \cdot a_1 + M_r$ (với $q = \frac{m - M_r}{a_1} \ge 0$ ).
Vì $q \ge 0$ và $M_r$ vốn đã là tổ hợp không âm của $(a_2, \dots, a_n)$ , ta suy ra $m$ có thể biểu diễn được bằng tổ hợp không âm của $(a_1, a_2, \dots, a_n)$ . $\blacksquare$

Không chỉ vậy, định lý này còn có một kết quả mạnh hơn. Bạn đọc có thể đọc ở đây: Schur's theorem - Wikipedia

Quay trở lại bài toán. Từ định lý Schur-Frobenius ta suy ra một hệ quả trực tiếp là số các mệnh giá không biểu diễn được là hữu hạn, nên không có trường hợp in ra infinite.

Do các $p_i$ đôi một nguyên tố cùng nhau, theo Định lý Số dư Trung Hoa, tồn tại duy nhất bộ số $(c_1, c_2, \dots, c_n)$ với $0 \le c_i \le p_i - 1$ sao cho:

x \equiv \sum_{i=1}^n c_i a_i \pmod P

Đặt $v(\mathbf{c}) = \sum_{i=1}^n c_i a_i$ . Khi đó $x$ luôn viết được dưới dạng $x = v(\mathbf{c}) + k P$ với $k \in \mathbb{Z}$ . Ta có bổ đề sau:

Bổ đề: Số $x$ là biểu diễn được $\iff k\ge0$ (tức $x \ge v(\mathbf{c})$ ).

Chứng minh

Chiều thuận:

Ta có $x = v(\mathbf{c}) + k P = (c_1 + k p_1) a_1 + \sum_{i=2}^n c_i a_i$ . Do $k \ge 0$ , tất cả hệ số đều $\ge 0$

Chiều nghịch:

Giả sử $x = \sum c'_i a_i$ với $c'_i \ge 0$ . Xét modulo $p_i$ , ta có $c'_i a_i \equiv x \equiv c_i a_i \pmod{p_i} \implies c'_i \equiv c_i \pmod{p_i}$ .

Do $c'_i \ge 0$ và $0 \le c_i \le p_i - 1$ , ta bắt buộc có $c'_i = c_i + k_i p_i$ với $k_i \ge 0$ .

Suy ra $x = \sum (c_i + k_i p_i) a_i = v(\mathbf{c}) + \left(\sum k_i\right) P \implies k = \sum k_i \ge 0$ .

Từ bổ đề trên, một số $x$ là không biểu diễn được khi và chỉ khi:

x = v(\mathbf{c}) - k P \quad \text{với } k \ge 1

Để tìm số không thể biểu diễn lớn nhất (số Frobenius $F$ ):

Chọn $k = 1$ và chọn các $c_{i}$ sao cho $v(\mathbf{c}) = \sum_{i=1}^n c_i a_i$ đạt giá trị lớn nhất, tức là chọn $c_i = p_i - 1$ với mọi $i$ . Do đó: $F = \sum_{i=1}^n (p_i - 1) a_i - P$ .
Biến đổi đại số:

\sum_{i=1}^n (p_i - 1) a_i = \sum_{i=1}^n (p_i a_i - a_i) = \sum_{i=1}^n (P - a_i) = n P - \sum_{i=1}^n a_i = n P - S

Thế vào công thức $F$ :

F = (n P - S) - P = (n - 1)P - S

Từ công thức trên ta có thể chứng minh được $F$ luôn là một số lẻ (bạn đọc có thể tự chứng minh bằng cách xét trường hợp).

Xét một số nguyên $x \in [0, F]$ . Ta ghép cặp $x$ với $F - x$ . Tập hợp $[0, F]$ gồm đúng $F + 1$ số nguyên, được chia thành $\frac{F + 1}{2}$ cặp $\{x, F - x\}$ . Ta chứng minh rằng trong mỗi cặp $\{x, F - x\}$ luôn có đúng một số biểu diễn được và một số không biểu diễn được.

Chứng minh

Ý 1: Không thể cả 2 số cùng biểu diễn được

Nếu cả $x$ và $F - x$ đều biểu diễn được, thì tổng của chúng là $F = x + (F - x)$ cũng phải biểu diễn được (tổng 2 tổ hợp tuyến tính không âm là tổ hợp tuyến tính không âm). Điều này mâu thuẫn với định nghĩa $F$ là số không biểu diễn được.

Ý 2: Không thể cả 2 số cùng không biểu diễn được

Không mất tính tổng quát, giả sử $x$ không biểu diễn được. Theo bổ đề, $x = v(\mathbf{c}) - k P$ với $k \ge 1$ . Ta xét số $F-x$ :

F - x = \left( \sum_{i=1}^n (p_i - 1) a_i - P \right) - \left( \sum_{i=1}^n c_i a_i - k P \right)

F - x = \sum_{i=1}^n (p_i - 1 - c_i) a_i + (k - 1) P

Đặt $c'_i = p_i - 1 - c_i$ . Vì $0 \le c_i \le p_i - 1$ , ta có $0 \le c'_i \le p_i - 1$ . Do $k \ge 1 \implies k - 1 \ge 0$ , biểu thức trên chính là dạng $v(\mathbf{c}') + k' P$ với $k' = k - 1 \ge 0$ . Theo bổ đề, $F - x$ biểu diễn được.

Tổng kết 2 ý ta suy ra trong hai số $x$ và $F-x$ phải có đúng 1 số biểu diễn được và 1 số không biểu diễn được, tức điều phải chứng minh.

Do $0$ biểu diễn được ( $c_i = 0$ ), các số không biểu diễn được đều nằm trong khoảng $[1, F]$ . Mọi số $> F$ đều biểu diễn được. Vậy tổng số lượng các số nguyên dương không biểu diễn được là:

g=\frac{F + 1}{2}=\frac{(n-1)P-S+1}{2}

Cài đặt. Vì $p_i$ có thể trùng với modulo $998244353$ nên ta không được dùng phép chia bằng nghịch đảo modulo. Thay vào đó, ta có thể tính nhanh được cả $P$ và $S$ bằng tích tiền tố nhân tích hậu tố của các số $p$ . Độ phức tạp cho mỗi test là $\mathcal{O}(n)$ .

Code

C++

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
static constexpr int MOD = 998244353;
7
static constexpr long long INV2 = (MOD + 1) / 2; // Modular inverse of 2 mod MOD
8

9
void solve() {
10
    int n;
11
    cin >> n;
12

13
    vector<long long> p(n);
14
    for (int i = 0; i < n; ++i) {
15
        cin >> p[i];
16
        p[i] %= MOD;
17
    }
18

19
    // Compute suffix products in O(N): suff[i] = p[i] * p[i+1] * ... * p[n-1] % MOD
20
    vector<long long> suff(n + 1, 1);
21
    for (int i = n - 1; i >= 0; --i) {
22
        suff[i] = (suff[i + 1] * p[i]) % MOD;
23
    }
24

25
    long long P = suff[0]; // Total product P = p[0] * ... * p[n-1] % MOD
26
    long long S = 0;
27
    long long pref = 1;
28

29
    // Compute S = sum(P / p_i) = sum(pref[i] * suff[i+1]) in O(N)
30
    for (int i = 0; i < n; ++i) {
31
        long long term = (pref * suff[i + 1]) % MOD;
32
        S = (S + term) % MOD;
33
        pref = (pref * p[i]) % MOD;
34
    }
35

36
    // Frobenius number F = (n - 1) * P - S (mod MOD)
37
    long long F = ((1LL * (n - 1) % MOD * P) - S) % MOD;
38
    if (F < 0) F += MOD;
39

40
    // Genus g = (F + 1) / 2 (mod MOD)
41
    long long g = (F + 1) % MOD * INV2 % MOD;
42

43
    cout << g << "\n";
44
}
45

46
int main() {
47
    // Fast I/O
48
    ios::sync_with_stdio(false);
49
    cin.tie(nullptr);
50

51
    int T;
52
    if (cin >> T) {
53
        while (T--) {
54
            solve();
55
        }
56
    }
57
    return 0;
58
}

E: Easy Game

Đề bài

Bash và Chikapu chơi một trò chơi đối kháng trên một băng giấy gồm $n$ ô trống ban đầu. Hai người luân phiên đi. Tại mỗi lượt, chọn 1 ô trống và điền 1 ký tự thuộc xâu $A$ vào ô đó.

Người chơi giành chiến thắng ngay lập tức nếu nước đi của mình tạo ra xâu $S$ có độ dài $m$ liên tiếp trên bảng. Trò chơi kết thúc Hòa nếu điền hết $n$ ô mà xâu $S$ vẫn chưa xuất hiện. Biết rằng $s$ không chứa 3 chữ cái liên tiếp giống nhau.

Xác định kết quả của trò chơi (Bash thắng, Chikapu thắng, hay Hòa) khi cả hai đều chơi tối ưu.

Giới hạn: $1 \le t \le 100$ testcase; $1 \le n \le 100$ ; $m=\vert{}S\vert{}\le100$ ; $\vert{}A\vert{}\le26$ .

Lời giải

Đây là một bài chia trường hợp rất khó và không có đội nào AC trong kì thi. Lời giải dưới đây bổ sung dựa trên sketch ý tưởng của anh RR.

Ta bắt đầu với các nhận xét:

Sau một nước đi của người X bất kì, nếu nó tạo ra trạng thái mà đối thủ có thể thắng luôn thì đó được gọi là “trạng thái chết”.
Nếu một người luôn có nước đi không tạo ra trạng thái chết ("nước an toàn") thì người đó không bao giờ thua. Nên nếu cả hai đều có chiến thuật luôn đi được nước an toàn thì kết quả là hòa. Kết quả chỉ khác hoà khi có người bị ép phải tạo ra trạng thái chết.

Các trường hợp dễ

Có kí tự của $S$ không thuộc $A$ : không bao giờ tạo được $S$ $\implies$ hoà.
$m>n$ : không đủ chỗ để tạo ra xâu $S$ $\implies$ hòa.
$m=1$ : Bash điền ngay chữ đó ở nước đầu $\implies$ Bash.
Có chữ thuộc $A$ mà không thuộc $S$ $\left(m\ge2\right)$ : chữ cái đó không khớp ô nào của $S$ , nên điền nó sẽ luôn an toàn $\implies$ hòa.

Như vậy, ta chỉ còn các trường hợp mà tập các chữ cái của $S$ trùng với tập các chữ cái của $A$ và $2\le m\le n.$

$m=2$

Đây vẫn còn là trường hợp dễ khi ta chỉ cần xét:

$S \sim aa$ (khi đó $A=\left\lbrace a\right\rbrace$ ): Bash điền $a$ vào ô bất kỳ, vì $n\ge2$ nên còn ô trống kề bên, Chikapu điền a vào đó và thắng $\implies$ Chikapu.
$S \sim ab$ : nếu một người chơi đi $b$ vào bên phải của 1 ô trống hoặc $a$ vào bên trái của 1 ô trống sẽ thua luôn. Do đó cả hai sẽ chơi an toàn bằng việc điền $b$ vào bên trái ngoài cùng hoặc $a$ vào bên phải ngoài cùng $\implies$ hòa.

$m=3,S\sim\left\lbrace abc,aab,baa\right\rbrace$

Cả 3 trường hợp này đều ra kết quả hoà.

$S \sim abc$ : ta có thể điền $c$ ở vị trí đầu tiên để trở thành người đi sau điền $a$ trước $c$ hoặc $b$ sau $c$ , điền $c$ sau $a$ hoặc $b$ trước $a$ , điền $b$ trước hoặc sau $b$ . Kết quả hoà.
$S \sim aab$ hoặc $S \sim baa$ coi như là một trường hợp $aab$ . Có một chiến thuật để chắc chắn hòa trở lên không phụ thuộc lượt đi là điền $b$ vào vị trí trống đầu tiên. Thật vậy vì 3 trạng thái chết có thể có là $aa?,a?b,?ab$ nên từ một trạng thái chưa chết ta không thể tạo ra trạng thái chết nếu chơi với chiến thuật trên. Như vậy kết quả là hoà.

$m=3$ , $S \sim aba$

Đây là lớp trường hợp then chốt và khó nhất của bài toán. Khi này ta định nghĩa “bẫy” là chuỗi có dạng $a??a$ trong đó $?$ thể hiện 1 ô trống. Ta thấy rằng nếu trên bảng có bẫy, thì người chơi nào điền bất kỳ $a$ hoặc $b$ vào vị trí $?$ của bẫy sẽ thua vì tạo ra trạng thái chết. Do đó khi tạo được bẫy thì người chơi tiếp theo sẽ chỉ có thể điền bên ngoài bẫy này. 2 người chơi sẽ cố gắng tránh bẫy này cho đến khi hết vị trí ở bên ngoài.

Gọi $F$ là số ô trống nằm ngoài mọi bẫy ("ô tự do"). Ô tự do luôn có nước an toàn, còn ô trong bẫy thì không. Mỗi nước an toàn vào ô tự do làm $F$ giảm 1, và nếu nó tạo thêm bẫy mới (điền $a$ cách một chữ $a$ có sẵn đúng 3 ô, ở giữa là hai ô $?$ ) thì $F$ sẽ giảm thêm 2 cho mỗi bẫy mới. Theo đó mỗi nước đi luôn làm $F$ giảm một lượng lẻ, nên tính chẵn lẻ của $F$ thay đổi sau mỗi nước đi. Không có cách nào giảm số bẫy đi, nên khi $F = 0$ mà có bẫy thì người đến lượt sẽ luôn tạo ra trạng thái chết và thua ở lượt sau.

Giả sử người $X$ vừa tạo bẫy lúc có $e$ ô trống (trước nước đi đó). Sau nước đó $F$ có cùng tính chẵn lẻ với $e - 1$ , đối thủ $Y$ đến lượt, và cứ đến lượt $Y$ thì $F$ lại có cùng tính chẵn lẻ ấy. $Y$ gặp $F = 0$ khi và chỉ khi $e - 1$ chẵn, tức $e$ lẻ. Từ đó ta có kết luận là $X$ thắng nếu $e$ lẻ, $X$ thua nếu $e$ chẵn. Áp dụng vào đầu trò chơi: Bash đi mỗi lượt khi $e$ cùng tính chẵn lẻ với $n$ ; Chikapu đi khi $e$ cùng tính chẵn lẻ với $n - 1$ . Do đó:

$n$ lẻ: chỉ Bash được lợi khi tạo bẫy. Nếu bẫy xuất hiện thì Bash thắng; Chikapu sẽ không tự tạo bẫy. Nếu không có bẫy nào thì hòa.
$n$ chẵn: ngược lại, chỉ Chikapu được lợi khi tạo bẫy. Nếu bẫy xuất hiện thì Chikapu thắng, nếu không thì hòa.

Từ nhận xét trên, ta có thể chứng minh được thêm khá nhiều trường hợp:

Với $n\le6$ ta có thể duyệt để chứng minh là kết quả luôn hoà.
Với $n=7$ , Bash điền $a$ vào ô số 4 (chính giữa). Bất kể người chơi sau đi thế nào, Bash có thể tạo được bẫy bằng việc điền $a$ vào ô 1 hoặc 7. Với mọi $n\ge7$ lẻ thì có thể chứng minh Bash thắng tương tự vậy.
Với $n$ chẵn Bash không thể thắng bằng chiến thuật này do khi tạo được bẫy thì Bash luôn thua do tính chẵn lẻ của $n$ . Ngược lại Bash chỉ có thể cố gắng cầm hoà. Với $n\le14$ có thể duyệt để tìm ra chiến thuật hoà là ở nước chơi đầu tiên, Bash phải đặt $b$ vào ô chính giữa $\implies$ hoà.
Với $n\ge16$ và $n$ chẵn, chiến thuật này không còn hiệu quả nữa, do khi Bash đặt $b$ ở nước đầu thì bảng chia ra thành 2 phần, 1 phần chẵn và 1 phần lẻ độ dài $\ge7$ . Do đó Chikapu sẽ luôn đưa được game về $n\ge7$ lẻ đi trước và thắng. (Chú ý rằng Bash không thể đi $a$ ở nước đầu tiên vì Chikapu sẽ tạo được bẫy và thắng). Đây là trường hợp khó nhất của bài toán và người bình thường không thể tự nghĩ ra được trừ khi ngồi chứng minh chặt chẽ các chiến thuật chơi cho trường hợp này.

$m\ge4$

Với $m\ge4$ thì kết quả luôn là hoà.

Pseudocode

Python

1
def solve(n, s, a):
2
    m = len(s)
3
    if m > n: return "Oh no!"  # target string exceeds board size
4

5
    set_A, set_S = set(a), set(s)
6

7
    if m == 1:
8
        return "Bash" if s[0] in set_A else "Oh no!"  # single character check
9

10
    if set_A != set_S:
11
        return "Oh no!"  # character sets must match
12

13
    if m == 2 and s[0] == s[1]:
14
        return "Chikapu"  # pattern "aa"
15

16
    if m == 3 and s[0] == s[2] != s[1]:  # pattern "aba"
17
        if n % 2 == 1 and n >= 7: return "Bash"
18
        if n % 2 == 0 and n >= 16: return "Chikapu"
19

20
    return "Oh no!"

ICPC Regional Hanoi 2024 Editorial - Z

I: Inversland

Đề bài

Lời giải

Code

E: Easy Game

Đề bài

Lời giải

Các trường hợp dễ

$m=2$

$m=3,S\sim\left\lbrace abc,aab,baa\right\rbrace$

$m=3$ , $S \sim aba$

$m\ge4$

Pseudocode

Continue reading

I: Inversland

Đề bài

Lời giải

Code

E: Easy Game

Đề bài

Lời giải

Các trường hợp dễ

m=2m=2m=2

m=3,S∼{abc,aab,baa}m=3,S\sim\left\lbrace abc,aab,baa\right\rbracem=3,S∼{abc,aab,baa}

m=3m=3m=3, S∼abaS \sim abaS∼aba

m≥4m\ge4m≥4

Pseudocode

Continue reading

Related reading

$m=2$

$m=3,S\sim\left\lbrace abc,aab,baa\right\rbrace$

$m=3$ , $S \sim aba$

$m\ge4$