trang chủ / đề bài / icpcwf25_b

Trò chơi trên bảng đen

Đề bài

Mô tả

Để giúp các học sinh tiểu học hiểu khái niệm phân tích ra thừa số nguyên tố, cô Aisha đã nghĩ ra một trò chơi trên bảng đen. Luật chơi như sau.

Trò chơi có hai người chơi, lần lượt thay phiên nhau đi. Ban đầu, các số nguyên từ 1 đến n được viết trên bảng. Ở nước đi đầu tiên, người chơi thứ nhất được chọn một số chẵn bất kỳ và khoanh tròn nó. Ở mỗi nước đi tiếp theo, người chơi hiện tại phải chọn một số (còn trên bảng) bằng số đang được khoanh tròn nhân với một số nguyên tố nào đó, hoặc bằng số đang được khoanh tròn chia cho một số nguyên tố nào đó. Sau đó người chơi xóa số đang được khoanh tròn và khoanh tròn số vừa chọn. Người chơi nào không thể đi được nữa thì thua.

Để giúp các học sinh của cô Aisha, hãy viết chương trình cho biết, với số nguyên n cho trước, nên đi trước hay đi sau thì tốt hơn, và nếu đi trước tốt hơn thì hãy tìm một nước đi đầu tiên giúp chiến thắng.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t (1≤t≤40), số bộ dữ liệu. Tiếp theo là mô tả của t bộ dữ liệu.

Mỗi bộ dữ liệu gồm một dòng chứa số nguyên n (2≤n≤107), số lớn nhất được viết trên bảng.

Dữ liệu ra

Với mỗi bộ dữ liệu, nếu người chơi thứ nhất có chiến lược thắng với n đã cho, in ra từ first, theo sau là một số nguyên chẵn: một nước đi đầu tiên bất kỳ mà từ đó người chơi thứ nhất vẫn có chiến lược thắng. Nếu người chơi thứ hai có chiến lược thắng, chỉ in ra từ second.

Ràng buộc

  • 1≤t≤40.
  • 2≤n≤107.
  • Tổng các giá trị n trong một test không vượt quá 107.

Ví dụ

Input Output Giải thích
1
5
second Với n=5, người chơi thứ nhất thua dù đi nước đầu tiên nào. Nếu người thứ nhất chọn 2, người thứ hai khoanh 4 và không còn nước đi hợp lệ nào. Nếu nước đầu tiên là 4, người thứ hai khoanh 2; người thứ nhất buộc phải khoanh 1, và người thứ hai chọn một trong hai số còn lại (3 hoặc 5) để thắng.
2
12
17
first 8
first 6
Với n=12 các nước đi đầu tiên giúp thắng là 2, 8, 12; với n=17 là 4, 6, 10, 16. In ra nước nào cũng được.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0