Giai đoạn đi đường
Đề bài
Mô tả
Năm 2030. Kiaya, một trong những tuyển thủ Leaf of Lemons giàu thành tích nhất thế giới, vào hàng chờ một trận xếp hạng để chuẩn bị cho giải đấu sắp tới. Trên màn hình chờ, một cái tên quen thuộc xuất hiện. Kiaya không tin vào mắt mình. Đối đầu với anh ở đường trên là Zeros the GOAT, đồng đội cũ của anh, từng được coi là tài năng trẻ triển vọng nhất của trò chơi, nhưng đáng tiếc đã bị cấm thi đấu từ nhiều năm trước vì hàng loạt bê bối. (GOAT là viết tắt của "Globally banned frOm All compeTitions", không hẳn như bạn nghĩ...)
"Chúc một trận đấu hay, ông già" (Kiaya lẩm bẩm khi điều khiển tướng của mình lên đường trên). Zeros đã ở trong tầm mắt, vẫn nhảy những điệu nhảy khiêu khích như hồi hai người còn trẻ.
Trong Leaf of Lemons, giai đoạn đầu của trận đấu gọi là giai đoạn đi đường, khi các tuyển thủ đối đầu với đối thủ ở một trong ba đường: trên, giữa và dưới. Để đơn giản, đường trên nơi Kiaya và Zeros giao chiến được mô tả là một dải gồm ô đánh số từ đến . Hiện tại, tướng của Kiaya và Zeros lần lượt ở ô và ô (). Hai người lần lượt di chuyển, Kiaya đi trước.
Đến lượt mình, người chơi đang ở vị trí bắt buộc phải lướt tướng của mình bằng cách chọn một số nguyên khác là sao cho:
- với Kiaya, với Zeros;
- .
Sau khi lướt, vị trí mới của người đó là .
Hơn nữa, vì cả hai đều là những tuyển thủ cực kỳ xuất sắc, nếu một người lướt tướng vào hoặc vượt qua đối thủ, người đó sẽ bị hạ gục ngay lập tức. Do đó, người chơi nào buộc được đối thủ phải lướt vào hoặc vượt qua tướng của mình sẽ thắng giai đoạn đi đường. Chính xác hơn, một người chơi lướt vào hoặc vượt qua đối thủ khi và chỉ khi sau lượt của người đó, vị trí của Kiaya lớn hơn hoặc bằng vị trí của Zeros.
Cho trạng thái hiện tại của đường trên, Kiaya muốn biết ai (nếu có) sẽ thắng giai đoạn đi đường, giả sử cả hai đều chơi tối ưu. Hãy giúp anh ấy!
Dữ liệu vào
Dòng đầu tiên chứa (): số bộ dữ liệu. Tiếp theo là bộ dữ liệu, mỗi bộ trên một dòng gồm năm số nguyên (, , ): số ô trên đường, vị trí xuất phát của Kiaya và Zeros, và số bước tối đa trong một lượt của Kiaya và Zeros.
Dữ liệu ra
Với mỗi bộ dữ liệu:
- nếu Kiaya có chiến thuật thắng, in ra
Kiaya; - nếu Zeros có chiến thuật thắng, in ra
Zeros; - nếu không ai có chiến thuật thắng, in ra
Draw.
Ràng buộc
- .
- , , .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 2 3 2 1 4 3 4 2 1 999 1 999 1 1 |
Zeros Kiaya Kiaya |
Bộ thứ nhất: Kiaya buộc phải lùi một bước về ô ; Zeros thắng bằng cách đi tới ô , buộc Kiaya phải lướt vào hoặc vượt qua anh ở lượt sau. Bộ thứ hai: Kiaya đi về ô ; Zeros buộc phải đi tới ô ; Kiaya đi tới ô ; Zeros buộc phải đi tới ô ; Kiaya đi tới ô , buộc Zeros phải lướt vào anh ở lượt sau. Bộ thứ ba: có thể chứng minh Kiaya thắng bằng cách luôn tiến lên một bước, bất kể Zeros làm gì. |
| 4 10 4 7 2 2 10 9 10 3 1 10 6 8 2 5 10 6 8 1 5 |
Kiaya Kiaya Kiaya Zeros |
Ví dụ bổ sung (không có trong đề gốc). Bộ thứ ba: Kiaya đi tới ô ; Zeros buộc phải lùi về ô hoặc , Kiaya luôn theo sát được (mỗi lượt đi tới ô) cho đến khi Zeros bị dồn vào ô với Kiaya ở ô . Bộ thứ tư: Kiaya chỉ đi được bước nên không theo kịp khi Zeros lùi bước. |
Bình luận