Trò chơi XOR của Koa
Đề bài
Mô tả
Cho một mảng gồm số nguyên không âm. Hai người chơi lần lượt thực hiện lượt đi, người thứ nhất đi trước. Ban đầu điểm của mỗi người đều bằng .
Trong một lượt, người chơi chọn một phần tử bất kỳ còn lại trong mảng, xoá nó khỏi mảng và XOR giá trị đó vào điểm của mình. Nói cách khác, nếu điểm hiện tại là và phần tử được chọn là thì điểm mới là .
Trò chơi kết thúc khi mảng rỗng. Người có điểm lớn hơn là người thắng; nếu điểm hai người bằng nhau thì hoà.
Cả hai người chơi đều chơi tối ưu: mỗi người ưu tiên thắng, nếu không thể thắng thì ưu tiên hoà, cuối cùng mới chấp nhận thua. Hãy xác định kết quả trò chơi đối với người đi trước.
Dữ liệu vào
- Dòng đầu chứa số nguyên là số bộ dữ liệu.
- Mỗi bộ dữ liệu gồm hai dòng:
- Dòng thứ nhất chứa số nguyên là độ dài mảng .
- Dòng thứ hai chứa số nguyên .
Dữ liệu ra
Với mỗi bộ dữ liệu, in ra trên một dòng:
- WIN nếu người đi trước thắng.
- LOSE nếu người đi trước thua.
- DRAW nếu trò chơi kết thúc hoà.
Ràng buộc
- Tổng trên tất cả các bộ dữ liệu không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 3 1 2 2 3 2 2 3 5 0 0 0 2 2 |
WIN LOSE DRAW |
Bộ 1: người đi trước chọn , đối thủ buộc phải chọn , người đi trước chọn còn lại. Điểm lần lượt là và , nên người đi trước thắng. Bộ 3: XOR của cả mảng bằng nên hai người luôn có điểm bằng nhau, kết quả hoà. |
| 4 5 4 1 5 1 3 4 1 0 1 6 1 0 2 5 4 |
WIN WIN DRAW WIN |
Bộ 3: mảng chỉ có một phần tử , người đi trước lấy nó và cả hai đều được điểm. Bộ 4: người đi trước lấy , đối thủ chỉ còn , nên . |
Bình luận