Nim Nhiều Đống

Buổi 50 — Game Theory
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions

Đề bài

Hai người chơi thay phiên nhau chơi trò chơi Nim với n đống đá. Đống thứ i có a_i viên đá. Mỗi lượt, người chơi phải chọn một đống đá có ít nhất một viên và lấy đi ít nhất 1 viên đá từ đống đó (có thể lấy toàn bộ đống). Người chơi nào không thể thực hiện nước đi (tất cả các đống đều hết) sẽ thua.

Người chơi đầu tiên đi trước. Xác định ai sẽ thắng nếu cả hai chơi tối ưu.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên dương T (1 ≤ T ≤ 1000) — số lượng test case.
  • Mỗi test case gồm 2 dòng:
    • Dòng đầu chứa n (1 ≤ n ≤ 10^5) — số đống đá.
    • Dòng sau chứa n số nguyên a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^9) — số viên đá mỗi đống.
  • Tổng n qua tất cả test case không vượt quá 2 × 10^5.

Dữ liệu ra

  • Với mỗi test case, in ra "First" nếu người chơi đầu tiên thắng, "Second" nếu người chơi thứ hai thắng.

Ví dụ

Input
3
3
1 2 3
2
5 5
4
1 1 1 1
Output
Second
Second
Second

Giải thích

  • 1 XOR 2 XOR 3 = 0 → Second thắng.
  • 5 XOR 5 = 0 → Second thắng.
  • 1 XOR 1 XOR 1 XOR 1 = 0 → Second thắng.

Giới hạn

  • 1 ≤ T ≤ 1000
  • 1 ≤ n ≤ 10^5
  • 0 ≤ a_i ≤ 10^9
  • Tổng n ≤ 2 × 10^5
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved