Nim Cầu Thang
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề bài
Cho một cầu thang gồm n bậc, đánh số từ 0 đến n. Bậc thứ i (1 ≤ i ≤ n) có a_i viên đá. Bậc 0 là mặt đất.
Hai người chơi thay phiên nhau. Mỗi lượt, người chơi phải chọn một bậc i (1 ≤ i ≤ n) có ít nhất một viên đá, và di chuyển ít nhất 1 viên đá từ bậc i xuống bậc i-1 (bậc ngay dưới). Người chơi nào không thể thực hiện nước đi (tất cả đá đã ở bậc 0) 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ố bậc.
- Dòng sau chứa n số nguyên a_1, a_2, ..., a_n (0 ≤ a_i ≤ 10^9) — số viên đá trên mỗi bậc.
- 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
2
3
1 2 3
4
1 1 1 1
Output
First
Second
Giải thích
- Test 1: XOR các bậc lẻ: a_1 XOR a_3 = 1 XOR 3 = 2 ≠ 0 → First thắng.
- Test 2: XOR các bậc lẻ: a_1 XOR a_3 = 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
Community Discussion