Stones (AtCoder Educational DP Contest K)

Nguồn: AtCoder Educational DP Contest (VNOJ) Độ khó: Trung bình Quy hoạch động Lý thuyết trò chơi Đệ quy có nhớ

Đề bài

Atcoder Educational DP Contest K – Stones

Cho tập hợp gồm $N$ số nguyên dương $A = \{a_1, a_2, \ldots, a_N\}$. Taro và Jiro chơi với nhau một trò chơi như sau:

Ban đầu, chúng ta có một đống đá chứa $K$ viên đá. Hai người chơi sẽ lần lượt thực hiện 1 nước đi như sau, với Taro là người bắt đầu:

• Chọn một phần tử $x$ của tập $A$, và loại bỏ đi chính xác $x$ viên đá từ đống đá.

Người nào không thể thực hiện được nước đi, thì đó là người thua cuộc. Giả sử cả hai người đều chơi tối ưu, xác định người chiến thắng.

Input:

• Dòng thứ nhất chứa hai số nguyên dương $N$, $K$ $(1 \le N \le 100,\ 1 \le K \le 10^5)$.
• Dòng thứ hai chứa $N$ số nguyên dương thỏa mãn $1 \le a_1 \lt a_2 \lt a_3 \lt \ldots \lt a_N \le K$.

Output: Nếu Taro là người thắng cuộc, in ra First, ngược lại nếu Jiro thắng in ra Second.

Sample 1 – input

2 4
2 3

Sample 1 – output

First

Nếu Taro loại 3 viên đá, Jiro không thể thực hiện nước đi. Thế nên, Taro thắng.

Sample 2 – input

2 5
2 3

Sample 2 – output

Second

Bất kể Taro làm điều gì thì Jiro vẫn thắng vì: nếu Taro loại 2 viên đá, Jiro có thể loại 3 viên đá khiến Taro không thể thực hiện nước đi. Nếu Taro loại 3 viên đá, Jiro có thể loại 2 viên đá khiến Taro không thể thực hiện nước đi.

Sample 3 – input

2 7
2 3

Sample 3 – output

First

Taro nên loại 2 viên đá. Sau đó, bất kể Jiro làm điều gì thì Taro vẫn thắng vì: nếu Jiro loại 2 viên đá, Taro có thể loại 3 viên đá khiến Jiro không thể thực hiện nước đi. Nếu Jiro loại 3 viên đá, Taro có thể loại 2 viên đá khiến Jiro không thể thực hiện nước đi.

Sample 4 – input

3 20
1 2 3

Sample 4 – output

Second

Sample 5 – input

3 21
1 2 3

Sample 5 – output

First

Sample 6 – input

1 100000
1

Sample 6 – output

Second

Lời mở đầu

Đây là bài K trong bộ Educational DP Contest nổi tiếng của AtCoder – một bài "trò chơi hai người" rất hay để làm quen với quy hoạch động trạng thái thắng/thua. Mình viết lời giải đi từ vét cạn lên dần quy hoạch động để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.

Trước tiên mình tóm tắt lại đề bài một cách đơn giản nhất để bạn nào chưa hiểu: Taro và Jiro chơi với nhau. Lúc đầu có đống đá chứa $k$ viên. Hai người lần lượt đi, Taro đi trước: mỗi lượt chọn một phần tử $a[i]$ và bỏ đi chính xác $a[i]$ viên đá khỏi đống ($1 \le i \le n$). Ai không thể đi được nữa thì thua. Cả hai đều chơi tối ưu: nếu có một cách thắng bất kể người kia chơi thế nào thì họ sẽ chơi theo cách thắng; họ chỉ thua khi dù chơi thế nào cũng thua. Hãy xác định người chiến thắng.

Ví dụ và giải thích ở đề đã rất rõ rồi. Mình chỉ nói thêm về sample 4 và 5 ($A = \{1, 2, 3\}$): người đứng trước $4$ viên đá luôn thua, vì bỏ $x$ viên thì đối thủ bỏ tiếp $4 - x$ viên là hết sạch. Tương tự, cứ đứng trước bội số của $4$ ($8, 12, 16, 20$…) là thua. Nên $K = 20$ thì Taro thua (Second), còn $K = 21$ thì Taro bỏ $1$ viên, đẩy Jiro vào thế $20$ viên, Taro thắng (First).

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Vét cạn 2 hàm Taro/Jiro · TLECách 2Gộp thành 1 hàm Try(k) · TLECách 3Đệ quy có nhớ · O(k·n) · ACCách 4QHĐ bottom-up · O(k·n) · AC

Cách 1Vét cạn với 2 hàm Taro() và Jiro()

Cách làm đơn giản nhất là vét cạn, tức thử mọi trường hợp có thể. Tới lượt Taro, ta thử bỏ đi $a[1]$ viên đá, rồi thử bỏ $a[2]$ viên, $a[3]$ viên, …, $a[n]$ viên; tương ứng còn lại $k - a[1]$, $k - a[2]$, …, $k - a[n]$ viên (viên đá chứ không phải đá gì đâu nha 😆). Sau đó tới lượt Jiro với số đá còn lại, ta cũng thử mọi trường hợp; rồi lại tới Taro, cứ luân phiên như vậy.

Để dễ hình dung nhất, ta tạo 2 hàm: hàm lượt của Taro và hàm lượt của Jiro. Đầu vào là số đá còn lại, trả về là người đang tới lượt có thắng được hay không. Trong hàm của Taro sẽ gọi hàm của Jiro, và trong hàm của Jiro lại gọi hàm của Taro. Để làm được điều đó, ta khai báo trước (prototype) hàm Jiro ở phía trên:

bool Jiro(int k);

bool Taro(int k) {
    // to do
}

bool Jiro(int k) {
    // to do
}

Nhờ dòng khai báo trước đó mà ở trong hàm Taro() ta gọi được tới hàm Jiro() dù nó được viết ở bên dưới. Giờ ta xây dựng hàm lượt của Taro (hàm của Jiro y hệt):

Hàm Taro(k)

Taro(k) cho biết: tới lượt Taro, còn $k$ viên đá thì Taro thắng (true) hay thua (false). Tương tự Jiro(k) cho biết tới lượt Jiro, còn $k$ viên thì Jiro thắng hay thua.

Điều kiện dừng: khi tới lượt một người mà hết đá rồi ($k = 0$) thì người đó thua (làm gì còn đá mà bỏ ra được nữa 😁): if(k == 0) return false;

Còn đá nhưng không đi được thì sao?

Trường hợp còn đá nhưng số đá nhỏ hơn cả $a_{min}$ (phần tử nhỏ nhất của $A$) thì cũng không đi được. Các bạn có thể tìm trước $a_{min}$ lúc đọc mảng (lưu biến toàn cục) rồi thêm if(k < aMin) return false;. Hoặc đơn giản hơn là không cần điều kiện này, vì phần xử lý bên dưới đã tự lo: không có $a[i] \le k$ nào thì res vẫn giữ nguyên false. Hoặc dùng điều kiện k < aMin và bỏ luôn k == 0 cũng ok hết nha.

Xử lý chạy: khởi tạo res = false (chưa biết thắng thua thì cứ coi là thua; làm vậy vì nếu không chọn được $a[i]$ nào thì kết quả cũng chính là thua). Rồi duyệt qua mảng $a$, mỗi lần lặp kiểm tra res còn false không (nếu đã true nghĩa là có cách thắng rồi, chỉ cần 1 cách thắng là đủ, khỏi thử tiếp). Nếu vẫn false thì kiểm tra $a[i] \le k$: còn 5 viên thì chỉ bỏ được 1, 2, 3, 4 hoặc 5 viên thôi, sao bỏ 6 viên được đúng không nào.

Mấu chốt là thế này: Taro bỏ ra $a[i]$ viên thì tới lượt Jiro với $k - a[i]$ viên. Nếu với $k - a[i]$ viên đó Jiro thắng thì Taro thua; ngược lại Jiro thua thì Taro thắng. Tức là kết quả của Taro khi bỏ ra $a[i]$ viên = ngược lại kết quả của Jiro khi còn $k - a[i]$ viên:

Công thức mấu chốt

res = !Jiro(k - a[i]); (trong hàm Taro)   và   res = !Taro(k - a[i]); (trong hàm Jiro, vì sau lượt Jiro là tới Taro).

Source code để các bạn tham khảo nếu làm theo hướng này:

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

int n, a[105];

bool Jiro(int k);

bool Taro(int k) {
    if(k == 0) {
        return false;
    }
    bool res = false;
    for(int i = 1; i <= n && !res; ++i) {
        if(a[i] <= k) {
            res = !Jiro(k - a[i]);
        }
    }
    return res;
}

bool Jiro(int k) {
    if(k == 0) {
        return false;
    }
    bool res = false;
    for(int i = 1; i <= n && !res; ++i) {
        if(a[i] <= k) {
            res = !Taro(k - a[i]);
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    if(Taro(k)) {
        cout << "First";
    }
    else {
        cout << "Second";
    }
    return 0;
}

import sys
sys.setrecursionlimit(1000000)

def Taro(k):
    if k == 0:
        return False
    res = False
    i = 1
    while i <= n and not res:
        if a[i] <= k:
            res = not Jiro(k - a[i])
        i += 1
    return res

def Jiro(k):
    if k == 0:
        return False
    res = False
    i = 1
    while i <= n and not res:
        if a[i] <= k:
            res = not Taro(k - a[i])
        i += 1
    return res

data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
if Taro(k):
    print("First")
else:
    print("Second")

Bấm Tiếp để xem từng lời gọi qua lại giữa Taro và Jiro (ngăn xếp lời gọi ở phần "Dữ liệu"):

C++▶ Chạy tay từng dòng codeCách 1: Taro(k) thử từng a[i] ≤ k, thắng nếu Jiro(k - a[i]) thua; Jiro(k) làm y hệt.

Dữ liệu vào (stdin) – sửa thoải mái2 4 2 3

Dữ liệu mẫu:

1#include<bits/stdc++.h>

2#define endl '\n'

3

4using namespace std;

5typedef long long ll;

6

7int n, a[105];

8

9bool Jiro(int k);

10

11bool Taro(int k) {

12 if(k == 0) {

13 return false;

14 }

15 bool res = false;

16 for(int i = 1; i <= n && !res; ++i) {

17 if(a[i] <= k) {

18 res = !Jiro(k - a[i]);

19 }

20 }

21 return res;

22}

23

24bool Jiro(int k) {

25 if(k == 0) {

26 return false;

27 }

28 bool res = false;

29 for(int i = 1; i <= n && !res; ++i) {

30 if(a[i] <= k) {

31 res = !Taro(k - a[i]);

32 }

33 }

34 return res;

35}

36

37int main() {

38 ios::sync_with_stdio(0);

39 cin.tie(0);

40 cout.tie(0);

41 int k;

42 cin >> n >> k;

43 for(int i = 1; i <= n; ++i) {

44 cin >> a[i];

45 }

46 if(Taro(k)) {

47 cout << "First";

48 }

49 else {

50 cout << "Second";

51 }

52 return 0;

53}

ChậmVừaNhanhRất nhanh

Giải thích 1 số chỗ trong code ở trên:

1. 3 dòng đầu hàm main (ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);) giúp đẩy nhanh tốc độ nhập xuất nếu các bạn code C++ (để hiểu vì sao thì cứ gõ mấy từ này lên Google là ra rất nhiều bài viết giải thích nhé). Bài này đầu vào chỉ tầm 100 số nên không thêm cũng được, nhưng mình vẫn code vì đó là thói quen rồi nha.
2. for(int i = 1; i <= n && !res; ++i): mỗi lần lặp kiểm tra $i \le n$ và res phải đang false. Nếu res = true thì vòng lặp dừng luôn.
3. Phần in kết quả: Taro(k) là true thì Taro thắng, in First; ngược lại Taro thua, tức Jiro thắng, in Second.

Đánh giá độ phức tạp của cách làm này: mỗi lời gọi có thể gọi tiếp tới $n$ lời gọi con, độ sâu tới $k / a_1$ tầng, nên số lời gọi tăng theo hàm mũ.

Không gian$O(n + k)$

Thời gianhàm mũ

TLE chắc chắn

Với cách này chắc chắn bị TLE, cụ thể ăn được 17/27 test. Mình đo thử bản C++ với $A = \{1, 2, 3\}$: $K = 40$ mất khoảng 2 giây, $K = 60$ chạy quá 30 giây vẫn chưa xong, trong khi $K$ tới $10^5$. Tuy nhiên vẫn nên cài đặt nó để làm công cụ kiểm tra tính chính xác cho cách tối ưu, hoặc để cải tiến thành quy hoạch động top-down.

Cách 2Gộp lại thành 1 hàm Try(k)

Bây giờ ta thấy một điều rất hay nè: hai hàm Taro() và Jiro() nó giống hệt nhau. Điều gì sẽ xảy ra nếu trong hàm Taro() ta gọi chính hàm Taro() chứ không gọi Jiro()? Câu trả lời là code vẫn đúng!

Lý do: thắng hay thua chỉ phụ thuộc vào số đá còn lại và ai là người đi trước với số đá đó – không quan trọng người đó tên là Taro hay Jiro. Giả sử với $5$ viên đá còn lại người đi trước sẽ thua, thì tới lượt Taro mà còn $5$ viên thì Taro thua; tới lượt Jiro mà còn $5$ viên thì Jiro thua.

Hàm Try(k)

Try(k) cho biết với $k$ viên đá còn lại thì người đi trước (người đang tới lượt) sẽ thắng hay thua. Lúc đầu người đi trước là Taro; sau mỗi nước đi, với đống đá còn lại thì người đi trước là người kia – cứ luân phiên thôi. Công thức: res = !Try(k - a[i]).

Source code để các bạn tham khảo nếu làm theo hướng này:

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

int n, a[105];

bool Try(int k) {
    if(k == 0) {
        return false;
    }
    bool res = false;
    for(int i = 1; i <= n && !res; ++i) {
        if(a[i] <= k) {
            res = !Try(k - a[i]);
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    if(Try(k)) {
        cout << "First";
    }
    else {
        cout << "Second";
    }
    return 0;
}

import sys
sys.setrecursionlimit(1000000)

def Try(k):
    if k == 0:
        return False
    res = False
    i = 1
    while i <= n and not res:
        if a[i] <= k:
            res = not Try(k - a[i])
        i += 1
    return res

data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
if Try(k):
    print("First")
else:
    print("Second")

C++▶ Chạy tay từng dòng codeCách 2: Try(k) = người đi trước với k viên có thắng không; thắng nếu có a[i] ≤ k mà Try(k - a[i]) thua.

Dữ liệu vào (stdin) – sửa thoải mái2 5 2 3

Dữ liệu mẫu:

1#include<bits/stdc++.h>

2#define endl '\n'

3

4using namespace std;

5typedef long long ll;

6

7int n, a[105];

8

9bool Try(int k) {

10 if(k == 0) {

11 return false;

12 }

13 bool res = false;

14 for(int i = 1; i <= n && !res; ++i) {

15 if(a[i] <= k) {

16 res = !Try(k - a[i]);

17 }

18 }

19 return res;

20}

21

22int main() {

23 ios::sync_with_stdio(0);

24 cin.tie(0);

25 cout.tie(0);

26 int k;

27 cin >> n >> k;

28 for(int i = 1; i <= n; ++i) {

29 cin >> a[i];

30 }

31 if(Try(k)) {

32 cout << "First";

33 }

34 else {

35 cout << "Second";

36 }

37 return 0;

38}

ChậmVừaNhanhRất nhanh

Với cách này code đã gọn hơn rất nhiều rồi, nhưng độ phức tạp vẫn y như cách 1 nên vẫn bị TLE thôi. Các bạn bấm nút A = 1 2 3, K = 8 rồi bấm ⏭ sẽ thấy một Try(k) bị gọi đi gọi lại rất nhiều lần – đó chính là chỗ ta sẽ cải tiến.

Không gian$O(n + k)$

Thời gianhàm mũ

Cách 3Đệ quy có nhớ (QHĐ top-down) – O(k·n)

Lý do code ở trên chạy lâu là vì một vấn đề đã tính rồi mà lần sau gặp lại vẫn phải tính lại. Tư tưởng của đệ quy có nhớ là lưu lại kết quả đã tính; gặp lại thì trả về luôn. Cách này áp dụng được cho cả 2 code trên, nhưng ở đây mình áp dụng vào hàm Try(k) cho gọn nha. Ta làm 3 bước:

1Tham số nào thay đổi? Hàm Try() chỉ có 1 tham số $k$, thay đổi ở mỗi lần gọi đệ quy. Vậy tạo mảng 1 chiều $F$, với $F[k]$ lưu kết quả của Try(k).

2Giới hạn của tham số? $k$ tối đa $10^5$, nên khai báo f[(int)1e5 + 5] (cộng thêm 5 cho chắc, tránh truy cập ngoài phạm vi mảng).

3Giá trị không thể trả về? Hàm kiểu bool chỉ trả về $0$/$1$, không bao giờ là $-1$. Nên khai báo $F$ kiểu int và lấp đầy bằng $-1$ (chưa tính). Cách khác là tạo thêm mảng bool check[] đánh dấu đã tính hay chưa.

✓Dùng như thế nào? Sau điều kiện dừng, nếu f[k] != -1 thì đã tính rồi, trả về f[k] luôn. Ngược lại tính như bình thường, lưu vào f[k] rồi trả về.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

int n, a[105], f[(int)1e5 + 5];

bool Try(int k) {
    if(k == 0) {
        return false;
    }
    if(f[k] != -1) {
        return f[k];
    }
    bool res = false;
    for(int i = 1; i <= n && !res; ++i) {
        if(a[i] <= k) {
            res = !Try(k - a[i]);
        }
    }
    return f[k] = res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int k;
    cin >> n >> k;
    fill(f, f + k + 1, -1);
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    if(Try(k)) {
        cout << "First";
    }
    else {
        cout << "Second";
    }
    return 0;
}

import sys
import threading

def main():
    data = sys.stdin.read().split()
    n, k = int(data[0]), int(data[1])
    a = [0] + [int(x) for x in data[2:2 + n]]
    f = [-1] * (k + 1)

    def Try(k):
        if k == 0:
            return False
        if f[k] != -1:
            return f[k] == 1
        res = False
        i = 1
        while i <= n and not res:
            if a[i] <= k:
                res = not Try(k - a[i])
            i += 1
        f[k] = 1 if res else 0
        return res

    if Try(k):
        print("First")
    else:
        print("Second")

sys.setrecursionlimit(1000000)
threading.stack_size(512 * 1024 * 1024)
t = threading.Thread(target=main)
t.start()
t.join()

C++▶ Chạy tay từng dòng codeCách 3: như cách 2 nhưng lưu Try(k) vào f[k]; gặp lại thì trả về ngay.

Dữ liệu vào (stdin) – sửa thoải mái3 8 1 2 3

Dữ liệu mẫu:

1#include<bits/stdc++.h>

2#define endl '\n'

3

4using namespace std;

5typedef long long ll;

6

7int n, a[105], f[(int)1e5 + 5];

8

9bool Try(int k) {

10 if(k == 0) {

11 return false;

12 }

13 if(f[k] != -1) {

14 return f[k];

15 }

16 bool res = false;

17 for(int i = 1; i <= n && !res; ++i) {

18 if(a[i] <= k) {

19 res = !Try(k - a[i]);

20 }

21 }

22 return f[k] = res;

23}

24

25int main() {

26 ios::sync_with_stdio(0);

27 cin.tie(0);

28 cout.tie(0);

29 int k;

30 cin >> n >> k;

31 fill(f, f + k + 1, -1);

32 for(int i = 1; i <= n; ++i) {

33 cin >> a[i];

34 }

35 if(Try(k)) {

36 cout << "First";

37 }

38 else {

39 cout << "Second";

40 }

41 return 0;

42}

ChậmVừaNhanhRất nhanh

Giải thích 1 số chỗ trong code ở trên:

1. return f[k] = res; là gán f[k] = res rồi mới return f[k].
2. fill(f, f + k + 1, -1); là lấp đầy $f[0..k]$ bằng $-1$. Bạn nào không biết hàm fill thì dùng vòng lặp for cũng được nha.

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(k + n)$ vì dùng 2 mảng $f$ và $a$.
• Thời gian: $O(k \cdot n)$. Trường hợp tệ nhất ta phải lấp đầy mảng $F$, và với mỗi $F[k]$ phải duyệt qua $n$ cách chọn. Thay $k = 10^5$, $n = 100$ thì cần cỡ $10^7$ phép tính – hoàn toàn AC (accepted) được bài này.

Không gian$O(k + n)$

Thời gian$O(k \cdot n)$

Độ sâu đệ quy

Với sample 6 ($A = \{1\}$, $K = 10^5$) độ sâu đệ quy lên tới $10^5$ tầng. Với C++ thì vẫn chạy ổn, nhưng Python mặc định chỉ cho khoảng 1000 tầng nên bản Python ở trên phải tăng sys.setrecursionlimit và chạy trong một threading.Thread có stack lớn.

Cách 4Phần đọc thêm: QHĐ bottom-up – O(k·n)

Ta đã có cách quy hoạch động top-down rồi thì cũng sẽ có cách bottom-up, chính là tạo ra công thức truy hồi. Cho anh em nào đã biết cơ bản về quy hoạch động rồi thì ta có 4 bước như sau:

1Bài toán con: $F[i]$ cho biết người đi trước khi còn $i$ viên đá sẽ thắng ($\text{true}$) hay thua ($\text{false}$).

2Bài toán cơ sở: còn $0$ viên hoặc không đi được ($i \lt a_{min}$) thì thua. Khai báo $F$ toàn cục là mặc định toàn $\text{false}$.

3Đáp án: $F[k]$ = $\text{true}$ thì in First, ngược lại in Second.

4Truy hồi: $F[i] = \text{!}F[i - a[j]]$, xét khi $F[i] = \text{false}$ và $a[j] \le i$.

Bước 1: Xác định bài toán con

Gọi $F[i]$ cho biết người đi trước khi còn $i$ viên đá sẽ thắng hay thua. $F[i] = \text{true}$ là thắng, $F[i] = \text{false}$ là thua.

Bước 2: Xác định bài toán cơ sở

Dễ thấy người đi trước (tức là tới lượt người đó) mà còn $0$ viên đá hoặc không thể thực hiện được nước đi ($i \lt a_{min}$) thì thua. Vậy lúc đầu lấp đầy mảng $F$ bằng $\text{false}$ – chỉ cần khai báo $F$ là mảng toàn cục thì mặc định các phần tử đã bằng $0$ (tức $\text{false}$) rồi.

Bước 3: Xác định đáp án của bài toán

Dĩ nhiên là $F[k]$ rồi. Với $k$ viên đá mà người đi trước thắng ($F[k] = \text{true}$) thì in First (Taro thắng); ngược lại in Second (Jiro thắng).

Bước 4: Xác định công thức truy hồi

Tương tự phần vét cạn: ta thử mọi cách chọn, và kiểm tra $F[i]$ còn đang $\text{false}$ không (nếu đã $\text{true}$ tức đã có cách thắng thì không cần thử nữa). Nếu số đá bỏ đi $a[j] \le i$ thì kết quả của người đi trước khi còn $i$ viên bằng ngược lại kết quả của người đi trước khi còn $i - a[j]$ viên – vì sau khi bỏ $a[j]$ viên, người kia thành người đi trước với $i - a[j]$ viên: người đó thắng thì ta thua, người đó thua thì ta thắng.

Công thức truy hồi

$F[i] = \text{!}F[i - a[j]]$ (khi $F[i] = \text{false}$ và $a[j] \le i$)
Nói cách khác: $F[i] = \text{true}$ khi và chỉ khi tồn tại $a[j] \le i$ mà $F[i - a[j]] = \text{false}$ – tức là có một nước đi đẩy đối thủ vào thế thua.

Minh hoạ: tô thắng/thua cho từng số đá

Các bạn nhập tập $A$ và $K$ rồi bấm Tiếp. Với mỗi $i$, các ô ứng viên là các số đá còn lại sau khi bỏ $a[j]$ viên; chỉ cần một ô ứng viên là thua (đỏ) thì $i$ là thắng:

Tập A K

Ví dụ nhanh:

Với $A = \{2, 3\}$ các thế thua là $0, 1, 5, 6, 10, 11, \ldots$ (lặp lại theo chu kỳ 5) – đúng như sample: $K = 4$ và $K = 7$ Taro thắng, $K = 5$ Taro thua. Với $A = \{1, 2, 3\}$ thì thế thua chính là các bội của $4$ như mình phân tích ở đầu bài.

Source code để các bạn tham khảo nếu làm theo hướng này:

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

bool f[(int)1e5 + 5];
int a[105];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for(int i = 1; i <= k; ++i) {
        for(int j = 1; j <= n && !f[i]; ++j) {
            if(a[j] <= i) {
                f[i] = !f[i - a[j]];
            }
        }
    }
    if(f[k]) {
        cout << "First";
    }
    else {
        cout << "Second";
    }
    return 0;
}

import sys

data = sys.stdin.read().split()
n, k = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:2 + n]]
f = [False] * (k + 1)
for i in range(1, k + 1):
    j = 1
    while j <= n and not f[i]:
        if a[j] <= i:
            f[i] = not f[i - a[j]]
        j += 1
if f[k]:
    print("First")
else:
    print("Second")

C++▶ Chạy tay từng dòng codeCách 4: f[i] = true nếu có a[j] ≤ i mà f[i - a[j]] = false; tính i từ 1 đến k.

Dữ liệu vào (stdin) – sửa thoải mái2 7 2 3

Dữ liệu mẫu:

1#include<bits/stdc++.h>

2#define endl '\n'

3

4using namespace std;

5typedef long long ll;

6

7bool f[(int)1e5 + 5];

8int a[105];

9

10int main() {

11 ios::sync_with_stdio(0);

12 cin.tie(0);

13 cout.tie(0);

14 int n, k;

15 cin >> n >> k;

16 for(int i = 1; i <= n; ++i) {

17 cin >> a[i];

18 }

19 for(int i = 1; i <= k; ++i) {

20 for(int j = 1; j <= n && !f[i]; ++j) {

21 if(a[j] <= i) {

22 f[i] = !f[i - a[j]];

23 }

24 }

25 }

26 if(f[k]) {

27 cout << "First";

28 }

29 else {

30 cout << "Second";

31 }

32 return 0;

33}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: vẫn giống cách quy hoạch động top-down, $O(k + n)$.
• Thời gian: vẫn là $O(k \cdot n)$, nhưng code chạy nhanh hơn và ăn ít bộ nhớ hơn do không phải tốn cho việc gọi đệ quy nữa nha.

Không gian$O(k + n)$

Thời gian$O(k \cdot n)$

Bạn nào code Python để ý

$10^7$ phép tính là nhẹ nhàng với C++ (mình đo cả cách 3 và cách 4 đều dưới 0.1 giây), nhưng bản Python của cách 4 mình đo với $n = 100$, $K = 10^5$ mất khoảng 3 giây, cách 3 khoảng 1–2 giây. Bài này các bạn nên nộp C++ nha (hoặc chọn PyPy nếu hệ thống chấm có hỗ trợ).

Ghi chú của mình: code C++ và Python của cả 4 cách đều cho đúng output của 6 sample, và đã được so với một chương trình tính thế thắng/thua độc lập trên 400 bộ test ngẫu nhiên nhỏ ($K \le 26$, $n \le 5$) – khớp hết. Với $n = 100$, $K = 10^5$: bản C++ cách 3 và cách 4 chạy dưới 0.1 giây; còn cách 1 và cách 2 với $A = \{1, 2, 3\}$, $K = 60$ đã chạy quá 30 giây.

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 😇