\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.7}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Phân tích bài toán chi tiết}}\)

• \(\color{#7f5f3f}{\text{Note: }}\) Ở dưới có cách đơn giản hơn

\(\color{#903030}{\text{Trường hợp đặc biệt}}\)

• Khi \((n = 0)\) HUY thắng vì KHÔI không chọn được
• Khi \((n \leq k)\) hiển nhiên KHÔI thắng vì chọn được hết
• Khi \((k = 1)\) thì xét chẵn lẻ với KHÔI đi trước thì thắng với \(n\) lẻ

\(\color{#903030}{\text{Định nghĩa}}\)

• Gọi việc chơi thắng là người ăn con cuối cùng, thua là bị buộc ăn con cuối cùng dù có đi ra sao và thắng thua là có thể cố thắng hoặc ép bên còn lại đi thắng dù họ đi thế nào
• Gọi nửa bên trái và bên phải của các viên đá là \(A\) và \(B\) (chia nhau bởi một dấu cách ở giữa)
• Gọi chỉ thua là \(0\), luôn thắng là \(1\), cả thắng và ép bên kia thắng là \(2\)
• Gọi \((...001|0110...)\) là thế trận ví dụ với \((x_p = 1)\) tức là tồn tại phàn tử \(p\)

\(\color{#903030}{\text{Trường hợp 1: }}\) Nước đi đầu Khôi chọn một đoạn ở giữa, chia 2 đoạn chỉ toàn số 1 kéo tới biên \((111..00|00..111)\)

• Trường hợp \(A0 - B0 (10100|0101)\)

Nếu HUY chơi bên nào thì mình sẽ cố ép thắng bên còn lại
+ Nếu HUY thắng một bên thì KHÔI sẽ thắng bên còn lại, và KHÔI chơi cuối
+ Nếu HUY đánh sang bên còn lại thì KHÔI sẽ ép thắng bên khác phía HUY

Vậy trường hợp này KHÔI thắng

• Trường hợp \(A0 - B1 (10100|00010)\)

HUY chơi thắng bên \(B\) và KHÔI thua \(A\)
+ Nếu KHÔI chơi cùng phía \(B\) sẽ thua
+ Nếu KHÔI chơi khác phía \(A\) thì kiểu gì cũng thắng một bên và sau đó HUY thắng bên còn lại và là người chọn cuối

Vậy trường hợp này HUY thắng

• Trường hợp \(A0 - B2 (0101|111)\)

HUY phải chủ động đánh thắng \(B\) để thắng
+ Nếu HUY đánh \(A\) thì KHÔI sẽ đánh \(B\) đưa về case A0 - B0
+ Nếu HUY đánh \(B\) thì đưa về \(A0 - B2\)

Vậy trường hợp này HUY thắng

• Trường hợp \(A1 - B0 (01000|00101)\)

Đảo ngược lại toàn bộ, ta sẽ thu được thế trận \(A0 - B1\)

Vậy trường hợp này HUY thắng

• Trường hợp \(A1 - B1 (10|01)\)

HUY đánh kiểu gì cũng thắng một bên nên HUY bị ép cờ
+ Nếu HUY đánh thắng một bên KHÔI sẽ thắng bên còn lại và KHÔI đánh cuối
+ Nhưng HUY không thể đánh thua vì kiểu gì KHÔI cũng ép thắng một bên

Vậy trường hợp này KHÔI thắng

• Trường hợp \(A1 - B2 (100|111)\)

HUY phải chủ động đánh thua \(B\) để thắng
+ Nếu HUY đánh \(B\) thì đưa về \(A1 - B0 = A0 - B1\)
+ Nếu HUY đánh \(A\) thì KHÔI đánh \(B\) đưa về \(A1 - B1\) và KHÔI thắng

Vậy trường hợp này HUY thắng

• Trường hợp \(A2 - B0 (111|0101)\)

Nếu đảo ngược cả thế trận ta thu được thế trận tương tự trường hợp \(A0 - B2\)

Vậy trường hợp này HUY thắng

• Trường hợp \(A2 - B1 (111|001)\)

Nếu đảo ngược cả thế trận ta thu được thế trận tương tự trường hợp \(A1 - B2\)

Vậy trường hợp này HUY thắng

• Trường hợp \(A2 - B2 (1110||01111)\)

KHÔI có thể điều khiển thế cờ theo ý mình muốn và ép cờ HUY để chiến thắng

• Nếu HUY đánh thắng một bên KHÔI cũng thắng bên còn lại và đưa về \(A1 - B1\)
• Nếu HUY đánh thua một bên KHÔI cũng thua bên còn lại và đưa về \(A0 - B0\)

Vậy trường hợp này KHÔI thắng

\(\color{#903030}{\text{Trường hợp 2: }}\) Nước đi đầu Khôi, chọn một đoạn kéo dài tới biên, đưa bài toán 1 bên về toàn 1 và bên còn lại toàn 0 \((111..11|00..000)\)

• Nếu chọn biên, tức là đã đánh thua một bên. Bên còn lại chủ động ăn hết còn lại hoặc đánh giữa và chiếm ưu thế chiến thắng

Vầy trừ trường hợp đặc biệt là KHÔI ăn hết hoặc HUY được đi ngu thì KHÔI luôn thua khi cắn biên

\(\color{#c01515}{\text{Approach <Cày trâu>}}\)

• \(\color{#f03030}{\text{Ý tưởng: }}\) Muốn kiểm tra xem là mình có thể phải trâu xuống các trạng thái xem có thể luôn thắng, ép thắng, và luôn thua hay không. Sau đó duyệt đến bài toán con và chia nhỏ bài toán

• \(\color{#f03030}{\text{Phân tích độ phức tạp:}}\)

Nếu sài trâu sẽ có độ phức tạp \(\Theta(k^n)\) hay \(\Theta(n!)\) tùy cách người cài đặt

Nếu sài quy hoạch động trạng thái sẽ có đô phức tạp \(\Theta(2^n)\)

\(\color{#300000}{\text{Phân tích bài toán đơn giản}}\)

• Khi \((n = 0)\) HUY thắng vì KHÔI không chọn được

• Khi \((n \leq k)\) hiển nhiên KHÔI thắng vì chọn được hết

• Khi \((k = 1)\) thì xét chẵn lẻ với KHÔI đi trước thì thắng với n lẻ

• Các trường hợp còn lại, khi thế cờ đối xứng và độ dài chẵn, dù đối thủ HUY có đi thế nào thì mình cũng có thể chọn một cách đi phù hợp để làm nó tiếp tục đối xứng, lúc này người cuối cùng, cũng chính KHÔI cố tình làm nó đối xứng thắng

• Vậy trong bước đi đầu tiên, với \((k \geq 2)\) thì KHÔI luôn có thể đưa cờ về thế đối xứng và cố tính ép đối xứng tới khi bốc những viên đá cuối cùng và dành chiến thắng

\(\color{#c01515}{\text{Approach <Lý thuyết trò chơi>}}\)

• \(\color{#f03030}{\text{Ý tưởng từ lời giải chi tiết: }}\) Nhận xét KHÔI chiếm ưu thế ngay từ đầu khi chọn giữa để chia hai đoạn còn lại bằng nhau thì cùng thua \(A0 - B0\) hoặc cùng thắng \(A1 - B1\) nên KHÔI sẽ luôn thắng trong TH không đặc biệt

• \(\color{#f03030}{\text{Ý tưởng từ lời giải đơn giản: }}\) Nếu \((n > 0)\) và \((k > 1)\) thì KHÔI luôn có cách thắng, còn lại ta xét trường hợp \((n = 0)\) và \((k = 1)\)

• \(\color{#f03030}{\text{Phân tích độ phức tạp: }}\) Sau khi có các nhận xét trên dựa trên các trường hợp, ta có thể kiểm tra điều kiện rồi \(ifelse\) trong \(O(1)\)

\(\color{#009933}{\text{Code tham khảo<Accepted> }}\): Lý thuyết trò chơi

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(1)\ \color{#7f5f3f}{\text{time}}\ ||\ O(1)\ \color{#7f5f3f}{\text{memory}}}}\)

int main()
{
    int n, k;
    cin >> n >> k;

    if (n == 0 || (k == 1 && n % 2 == 0))
        cout << "Huy";
    else 
        cout << "Khoi";
    return 0;
}