Đây là bài toán tương tác. Hãy nhớ đẩy bộ đệm đầu ra (flush) sau mỗi lần in. Để đẩy đầu ra, bạn có thể sử dụng:

• fflush(stdout) hoặc cout.flush() trong C/C++;
• System.out.flush() trong Java và Kotlin;
• sys.stdout.flush() trong Python.

Ý tưởng của trò chơi, được minh họa bởi Nano Banana Pro.

Bạn đang tham gia vào một trò chơi chiến thuật theo lượt có tên là Cò Quay Súng Lục (Revolver Roulette).

Trò chơi bắt đầu với một khẩu súng lục ổ quay được nạp đúng $6$ viên đạn. Mỗi viên đạn độc lập có xác suất ngang nhau là đạn thật (live) hoặc đạn giả (blank). Cả hai người chơi luôn biết số lượng đạn thật và đạn giả hiện còn lại trong ổ quay, nhưng không biết thứ tự chính xác của chúng.

Mỗi người chơi bắt đầu với $5$ điểm máu (HP) và $2$ vật phẩm. Nếu HP của một người chơi giảm xuống $0$ hoặc thấp hơn, người đó sẽ bị loại và người chơi kia giành chiến thắng. Hai người chơi lần lượt thực hiện các hành động.

Quy trình Lượt chơi

Trong lượt của mình, người chơi đang có lượt có thể thực hiện số lần tùy ý các hành động sau:

• Sử dụng bất kỳ vật phẩm nào.
• Thực hiện bất kỳ hành động bắn nào.

Lượt chơi chỉ kết thúc khi một hành động bắn làm chuyển lượt sang người chơi kia, hoặc khi có một người chơi bị loại.

Hành động Bắn

Người chơi đang có lượt phải chọn một trong các hành động bắn sau:

• Fire at Opponent: Người chơi đang có lượt bắn viên đạn tiếp theo vào đối thủ. Nếu đó là đạn thật, đối thủ mất $1$ HP. Bất kể loại đạn là gì, lượt chơi sẽ chuyển sang đối thủ.
• Fire at Self: Người chơi đang có lượt tự bắn viên đạn tiếp theo vào chính mình. Nếu đó là đạn thật, người chơi đang có lượt mất $1$ HP và lượt chơi chuyển sang đối thủ. Ngược lại, nếu đó là đạn giả, người chơi đang có lượt giữ nguyên lượt của mình và tiếp tục thực hiện các hành động.

Vật phẩm

Khi một vật phẩm được sử dụng, nó sẽ bị tiêu hao và người chơi đang có lượt vẫn giữ nguyên lượt của mình, bất kể loại vật phẩm là gì. Các vật phẩm đều hiển thị công khai cho cả hai người chơi. Khi một người chơi nhận được một vật phẩm mới (bao gồm cả mỗi vật phẩm ban đầu), nó được chọn ngẫu nhiên đồng đều từ bốn loại sau:

• Dummy: Bắn viên đạn tiếp theo vào hình nộm huấn luyện. Hành động này làm tiêu hao viên đạn và không được coi là một hành động bắn.
• Magnifier: Nhìn lén viên đạn tiếp theo để biết viên đạn tiếp theo là đạn thật hay đạn giả. Cả hai người chơi đều biết kết quả.
• Converter: Đảo ngược loại của viên đạn tiếp theo (đạn thật $\leftrightarrow$ đạn giả). Cả hai người chơi đều quan sát được số lượng đạn thật và đạn giả sau khi cập nhật.

• Cage: Nhận hiệu ứng một lần giúp ngăn lượt chơi kết thúc ở hành động bắn tiếp theo mà thông thường sẽ làm kết thúc lượt. Cụ thể:

  • Nếu sau đó người chơi thực hiện Fire at Opponent (bất kể viên đạn là thật hay giả), hiệu ứng sẽ được áp dụng và lượt chơi không kết thúc.
  • Nếu sau đó người chơi thực hiện Fire at Self và viên đạn là đạn thật, hiệu ứng sẽ được áp dụng và lượt chơi không kết thúc (người chơi vẫn mất $1$ HP, nhưng giữ lại được lượt).

  Hiệu ứng bị tiêu hao ngay sau khi áp dụng một lần. Mỗi lượt chỉ được sử dụng nhiều nhất một vật phẩm Cage.

Nạp đạn (Reloading)

Khi ổ quay trống rỗng, $6$ viên đạn mới sẽ được nạp ngay lập tức (mỗi viên độc lập là đạn thật hoặc đạn giả với xác suất bằng nhau). Cả hai người chơi đều được thông báo về số lượng đạn thật và đạn giả mới. Ngoài ra, mỗi người chơi được bổ sung lại tối đa đến $2$ vật phẩm (một người chơi đang có $k$ vật phẩm sẽ nhận thêm $(2 - k)$ vật phẩm mới, mỗi vật phẩm được chọn ngẫu nhiên đồng đều và độc lập từ bốn loại trên).

Mục tiêu

Bạn là người chơi đi lượt đầu tiên, và mục tiêu của bạn là giành chiến thắng bằng cách loại bỏ đối thủ.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $w$, cho biết bạn cần thắng ít nhất $w$ trong số $n$ ván đấu để được chấp nhận. Chỉ có đúng ba test:

• Test ví dụ: $n = 1$ và $w = 0$. ($0\%$)
• Test ẩn 1: $n = 2\,000$ và $w = 1\,000$. ($50\%$)
• Test ẩn 2: $n = 20\,000$ và $w = 11\,000$. ($55\%$)

Có thể chứng minh rằng khi cả hai người chơi đều chơi tối ưu, người chơi đi trước sẽ thắng xấp xỉ $56.89\%$ số ván đấu.

Giao thức Tương tác

Bắt đầu Ván đấu

Chương trình của bạn đóng vai người chơi đi lượt đầu tiên đấu với trình tương tác. Khi bắt đầu mỗi ván đấu, trình tương tác in ra một số nguyên $g$:

• Nếu $g = 0$, tất cả các ván đấu trong lần chạy hiện tại đã hoàn tất. Chương trình của bạn phải kết thúc ngay lập tức.
• Ngược lại, $g$ là chỉ số của ván đấu hiện tại ($1 \le g \le n$).

Do vấn đề kỹ thuật, chương trình của bạn được thực thi hai lần trên mỗi test:

• Trình tương tác có thể quyết định khởi động lại chương trình của bạn bằng cách đưa ra $g = 0$ bất cứ lúc nào.

Bạn sẽ nhận được cùng giá trị $n$ và $w$ cho mỗi lần chạy trong một test. Do đó, $n$ không phải lúc nào cũng bằng số lượng ván đấu trong lần chạy hiện tại. Đảm bảo rằng mỗi ván đấu $1, \dots, n$ được chơi đúng một lần qua hai lần chạy. Ngoài điều này ra, chương trình của bạn có thể bỏ qua điều kiện chạy hai lần một cách an toàn.

Trạng thái Trò chơi

Tiếp theo, trình tương tác in ra dòng trạng thái trò chơi gồm $13$ số nguyên không âm:

$$t \quad l \quad b \quad h_1 \quad d_1 \quad m_1 \quad c_1 \quad k_1 \quad h_2 \quad d_2 \quad m_2 \quad c_2 \quad k_2$$

• $t \in \{0, 1, 2\}$: trạng thái lượt.
• $l, b$ ($1 \le l + b \le 6$): số lượng đạn thật và đạn giả hiện còn lại trong ổ quay.
• $h_1$ ($0 \le h_1 \le 5$): HP hiện tại của bạn.
• $d_1, m_1, c_1, k_1$ ($0 \le d_1 + m_1 + c_1 + k_1 \le 2$): số lượng vật phẩm Dummy, Magnifier, Converter và Cage bạn đang giữ.
• $h_2$ ($0 \le h_2 \le 5$): HP hiện tại của đối thủ.
• $d_2, m_2, c_2, k_2$ ($0 \le d_2 + m_2 + c_2 + k_2 \le 2$): số lượng vật phẩm Dummy, Magnifier, Converter và Cage đối thủ đang giữ.

Trường hợp $t = 0$ (Kết thúc Ván đấu)

Ván đấu hiện tại đã kết thúc. Trình tương tác chuyển sang ván đấu tiếp theo (in ra $g$ mới).

Trường hợp $t = 1$ (Lượt của Bạn)

Bạn phải in ra một số nguyên để chọn hành động:

1. Fire at Opponent.
2. Fire at Self.
3. Sử dụng vật phẩm Dummy.
4. Sử dụng vật phẩm Magnifier.
5. Sử dụng vật phẩm Converter.
6. Sử dụng vật phẩm Cage.

Nếu hành động không hợp lệ (ví dụ: sử dụng vật phẩm bạn không có, hoặc sử dụng vật phẩm Cage nhiều hơn một lần trong cùng một lượt), trạng thái trò chơi không thay đổi, trình tương tác in ra $0$ và in lại dòng trạng thái ($13$ số nguyên) đó. Mặc dù vẫn là lượt của bạn, bạn phải thực hiện một hành động hợp lệ khác để tiếp tục trò chơi.

Ngược lại, hành động có hiệu lực và trình tương tác in ra một số nguyên kết quả:

• Đối với các hành động $1$–$5$: Trả về $1$ nếu viên đạn tiếp theo trước hành động là đạn thật, $2$ nếu là đạn giả.
• Đối với hành động $6$: Trả về $1$ (không tiết lộ thông tin đạn).

Trình tương tác sau đó in ra dòng trạng thái trò chơi đã cập nhật.

Trường hợp $t = 2$ (Lượt của Đối thủ)

Trình tương tác mô phỏng hành động của đối thủ và in ra hai dòng:

• Mã hành động $a \in \{1, \dots, 6\}$.
• Số nguyên kết quả ($1$ hoặc $2$ như mô tả ở trên).

Đối thủ không bao giờ thực hiện hành động bất hợp lệ. Ngay sau đó, trình tương tác in ra dòng trạng thái trò chơi tiếp theo ($13$ số nguyên).

Đối với mỗi ván của trò chơi, trình mô phỏng sử dụng bộ sinh số giả ngẫu nhiên với hạt giống (seed) cố định. Ngoài ra, đối thủ trong trình tương tác sử dụng chiến lược tất định. Quyết định khởi động lại chương trình của bạn độc lập với quá trình tương tác. Do đó, cùng một chuỗi hành động luôn dẫn đến cùng một trạng thái trò chơi.

Một công cụ kiểm thử được cung cấp để giúp bạn phát triển và kiểm tra chương trình của mình.

Ví dụ

Ví dụ 1, Lần chạy 1

Dữ liệu vào

1 0
1
1 3 3 5 0 0 0 2 5 1 0 1 0

1
1 3 3 5 0 0 0 1 5 1 0 1 0

1
1 2 3 5 0 0 0 1 4 1 0 1 0

0
1 2 3 5 0 0 0 1 4 1 0 1 0

2
1 2 2 5 0 0 0 1 4 1 0 1 0

1
2 1 2 5 0 0 0 1 3 1 0 1 0
5
2
2 2 1 5 0 0 0 1 3 1 0 0 0
1
1
1 1 1 4 0 0 0 1 3 1 0 0 0

1
2 0 1 4 0 0 0 1 2 1 0 0 0
3
2
2 2 4 4 0 1 0 1 2 0 1 0 1
2
1
1 1 4 4 0 1 0 1 1 0 1 0 1

1
1 1 4 4 0 0 0 1 1 0 1 0 1

1
0 0 4 4 0 0 0 1 0 0 1 0 1
0

Kết quả

6


1


6


2


1








1








4


1

Ví dụ 1, Lần chạy 2

Dữ liệu vào

1 0
0

Kết quả