Trò chơi XOR của Koa

Đề bài

Mô tả

Cho một mảng a gồm n 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 0.

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à x và phần tử được chọn là y thì điểm mới là xy.

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 t 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 n là độ dài mảng a.
    • Dòng thứ hai chứa n số nguyên a1,a2,,an.

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

  • 1t104
  • 1n105
  • 0ai109
  • Tổng n trên tất cả các bộ dữ liệu không vượt quá 105.

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 1, đối thủ buộc phải chọn 2, người đi trước chọn 2 còn lại. Điểm lần lượt là 12=32, nên người đi trước thắng.
Bộ 3: XOR của cả mảng bằng 0 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ử 0, người đi trước lấy nó và cả hai đều được 0 điểm.
Bộ 4: người đi trước lấy 5, đối thủ chỉ còn 4, nên 5>4.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.400 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0