NK05MNIM - Bốc sỏi

Bài toán

Hai bạn Nam và Mai cùng chơi một trò chơi với n đống sỏi. Luật chơi như sau:

• Hai bạn sẽ lần lượt đi. Bạn Mai là người đi trước
• Trong mỗi lượt đi, bạn đi sẽ được quyền bốc một số sỏi bất kỳ từ một đống nhất định và phải bốc tối thiểu là 1 viên sỏi.
• Bạn nào bốc phải viên sỏi cuối cùng là người thua cuộc

Bạn hãy giúp Mai xác định xem bạn ấy có thể thắng được trong trò chơi hay không

 

 Dữ liệu vào

Dòng đầu tiên chứa một nguyên t là số bộ test. Các dòng sau là t bộ test.
Mỗi bộ test bao gồm:

• Dòng đầu tiên chứa một số nguyên n (n<=100) là số đống sỏi
• Dòng thứ hai gồm n số nguyên a₁, a₂, a₃,... , a_n, ngăn cách nhau bởi một khoảng trắng. Số nguyên ai cho biết số lượng viên sỏi có trong đống thứ i (1<=a_i<=100)

Kết quả

Với mỗi bộ test, in ra 1 nếu bạn Mai thắng, -1 nếu bạn Mai thua

Ví dụ

Input
2
4
30 4 19 75
3
1 4 5


Output
1 

-1

Giới hạn

Thời gian chạy:	0.460s
Giới hạn mã nguồn:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)

Giải thuật (Thuật thắng trò chơi NIM)

- Tổng Nim của hai số a,b là a xnor b (trong C++ kí hiệu là a^b).

- Nếu số đống sỏi lẻ và mỗi đống chỉ có một viên thì người chơi trước luôn thua.

- Nếu ban đầu (a₁, a₂, a₃,... , a_n ) có tổng Nim duơng thì người chơi trước luôn thắng. (Theo định lý Bouton)

Code mẫu

- ideone.com
- github.com