Trò Chơi Hợp Nhất

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

Đề bài

Cho n trò chơi độc lập. Trò chơi thứ i có một đống đá gồm a_i viên. Mỗi trò chơi có quy tắc khác nhau: trong trò chơi thứ i, người chơi chỉ được lấy từ 1 đến k_i viên đá (subtraction game với tập {1, 2, ..., k_i}).

Hai người chơi thay phiên nhau. Mỗi lượt, người chơi chọn một trò chơi chưa kết thúc (đống đá còn viên) và thực hiện nước đi hợp lệ trong trò chơi đó. Người chơi nào không thể thực hiện nước đi nào (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ố trò chơi.
    • n dòng tiếp theo, mỗi dòng chứa hai số a_i, k_i (0 ≤ a_i ≤ 10^9, 1 ≤ k_i ≤ 10^9).
  • 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
2
5 2
7 3
3
10 3
6 2
8 5
Output
First
Second

Giải thích

  • Test 1: Grundy(5, k=2) = 5 % 3 = 2, Grundy(7, k=3) = 7 % 4 = 3. XOR = 2 ^ 3 = 1 ≠ 0 → First.
  • Test 2: Grundy(10, k=3) = 10 % 4 = 2, Grundy(6, k=2) = 6 % 3 = 0, Grundy(8, k=5) = 8 % 6 = 2. XOR = 2 ^ 0 ^ 2 = 0 → Second.

Giới hạn

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