Nim Game II

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Hai người chơi chơi Nim với $n$ đống que có $x_{1}, x_{2}, \dots, x_{n}$ que. Mỗi lượt, người chơi chọn một đống không rỗng và lấy đi 1, 2, hoặc 3 que. Người lấy que cuối cùng thắng. Xác định người thắng khi cả hai chơi tối ưu.

Dữ liệu vào

Dòng 1: số nguyên $t$ — số lượng truy vấn.
Với mỗi truy vấn:
- Dòng 1: số nguyên $n$ .
- Dòng 2: $n$ số nguyên $x_{1}, x_{2}, \dots, x_{n}$ .

Dữ liệu ra

Với mỗi truy vấn, in "first" nếu người đi trước thắng, "second" nếu người đi sau thắng.

Ràng buộc

$1 \leq t \leq 2 \times 10^{5}$
$1 \leq n \leq 2 \times 10^{5}$
$1 \leq x_{i} \leq 10^{9}$
Tổng tất cả $n$ không vượt quá $2 \times 10^{5}$

Ví dụ

Input	Output	Giải thích
3 4 5 7 2 5 2 4 1 3 4 4 4	first first second	Giá trị Grundy: $G (x) = x mod 4$ ; XOR: $1 \oplus 3 \oplus 2 \oplus 1 \neq 0$ ; $0 \oplus 1 \neq 0$ ; $0 \oplus 0 \oplus 0 = 0$

Bình luận

Không có bình luận tại thời điểm này.