Nim Giới Hạn
Points
40
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề 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 đá và lấy đi ít nhất 1 viên, nhưng không được lấy quá L viên đá từ đố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 hai số n, L (1 ≤ n ≤ 10^5, 1 ≤ L ≤ 10^9) — số đống đá và giới hạn lấy.
- 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 2
5 7 3
2 3
4 8
1 5
10
Output
First
Second
First
Giải thích
- Test 1: Grundy(a_i) = a_i % 3. G(5)=2, G(7)=1, G(3)=0. XOR = 2^1^0 = 3 ≠ 0 → First.
- Test 2: Grundy(a_i) = a_i % 4. G(4)=0, G(8)=0. XOR = 0 → Second.
- Test 3: Grundy(10) = 10 % 6 = 4 ≠ 0 → First.
Giới hạn
- 1 ≤ T ≤ 1000
- 1 ≤ n ≤ 10^5, 1 ≤ L ≤ 10^9
- 0 ≤ a_i ≤ 10^9
- Tổng n ≤ 2 × 10^5
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion