Chuồng Bò Tròn

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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

Farmer John và Farmer Nhoj chơi một trò chơi trong chuồng bò hình tròn có $N$ phòng. Phòng thứ $i$ ban đầu chứa $a_{i}$ con bò. Cả hai bắt đầu ở phòng 1 và lần lượt thực hiện (John đi trước):

Nếu phòng hiện tại có 0 con bò, người đi thua.
Ngược lại, người đi chọn số nguyên $P$ (với $P = 1$ hoặc $P$ là số nguyên tố không vượt quá số bò hiện tại), và loại bỏ $P$ con bò khỏi phòng.
Sau khi cả hai đi xong, họ chuyển sang phòng kế tiếp (theo vòng tròn).

Xác định ai thắng nếu cả hai chơi tối ưu.

Dữ liệu vào

Dòng 1: số nguyên $T$ ( $1 \leq T \leq 1000$ ), số bộ test.
Mỗi bộ test:
- Dòng 1: số nguyên $N$ ( $1 \leq N \leq 10^{5}$ ).
- Dòng 2: $N$ số nguyên $a_{1}, \dots, a_{N}$ ( $1 \leq a_{i} \leq 5 \times 10^{6}$ ).

Dữ liệu ra

Với mỗi bộ test, in "Farmer John" hoặc "Farmer Nhoj".

Ràng buộc

$1 \leq N \leq 10^{5}$ , $1 \leq a_{i} \leq 5 \times 10^{6}$
Tổng $N$ qua tất cả bộ test $\leq 2 \times 10^{5}$

Ví dụ

Input	Output	Giải thích
5 1 4 1 9 2 2 3 2 7 10 3 4 9 4	Farmer Nhoj Farmer John Farmer John Farmer John Farmer Nhoj	Với $a = [4]$ : cả hai luân phiên bỏ bò, 4 chia hết cho 4 nên Nhoj thắng.

Bình luận

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