trang chủ / đề bài / icpc24_nat_l

Tắt đèn

Đề bài

Mô tả

Một buổi tối, Bash và Chikapu đến một tòa chung cư bỏ hoang có n tầng. Thật bất ngờ, ở mỗi tầng vẫn còn một số bóng đèn hoạt động! Hai bạn chạy lên chạy xuống, bật tắt thử các bóng đèn và thấy rằng ở tầng thứ i có ai bóng đèn còn hoạt động. Ở mỗi tầng, các bóng đèn được đánh số từ 1 đến ai theo thứ tự từ trái sang phải.

Hiện tại hai bạn đang đứng trên sân thượng, sau khi đã tắt hết các bóng đèn ở mỗi tầng, trừ bóng đèn ngoài cùng bên phải (bóng số ai, bóng cần dùng để đi cầu thang).

Vốn hiếu thắng, hai bạn nghĩ ra trò chơi sau. Hai người chơi lần lượt thay phiên nhau, Bash đi trước. Ở mỗi lượt:

  1. Người chơi chọn một số i và đi đến tầng thứ i.
  2. Người chơi chọn một bóng đèn c đang bật ở tầng thứ i.
  3. Người chơi tắt bóng đèn c, đồng thời đảo trạng thái (bật thành tắt, tắt thành bật) của không, một hoặc hai bóng đèn tùy ý cùng tầng nằm bên trái bóng c.

Trò chơi kết thúc khi tất cả bóng đèn đều tắt; người thực hiện lượt cuối cùng là người thắng. Hãy xác định người thắng nếu cả hai đều chơi tối ưu. Nếu Bash (người đi trước) thắng, hãy đếm số nước đi đầu tiên khác nhau mà sau đó Bash chắc chắn thắng, lấy theo modulo 998244353.

Hai nước đi được coi là khác nhau nếu:

  • tầng i được chọn khác nhau, hoặc
  • bóng đèn c được chọn khác nhau, hoặc
  • tập các bóng đèn bị đảo trạng thái khác nhau.

Dữ liệu vào

Dữ liệu gồm nhiều bộ test. Dòng đầu tiên chứa số nguyên t (1≤t≤105): số bộ test. Mỗi bộ test gồm:

  • Dòng đầu tiên chứa số nguyên n (1≤n≤105): số tầng.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (1≤ai≤1018): số bóng đèn ở mỗi tầng.

Tổng n trên tất cả các bộ test không vượt quá 105.

Dữ liệu ra

Với mỗi bộ test, in kết quả trên một dòng:

  • Nếu Chikapu thắng, in Chikapu.
  • Nếu Bash thắng, in Bash rồi một dấu cách và số nguyên x: số nước đi đầu tiên sau đó Bash chắc chắn thắng, lấy theo modulo 998244353.

Ràng buộc

  • 1≤t≤105
  • 1≤n≤105, tổng n trên tất cả các bộ test không vượt quá 105
  • 1≤ai≤1018

Ví dụ

Input Output Giải thích
2
3
1 2 1
4
1 2 3 4
Bash 1
Chikapu
Ví dụ của đề gốc.
4
1
5
2
2 3
3
3 6 7
2
4 4
Bash 1
Bash 1
Bash 3
Chikapu
Ví dụ bổ sung, tính bằng lời giải mẫu. Bộ test thứ nhất: nước thắng duy nhất là tắt bóng 5 và không đảo bóng nào, khi đó mọi bóng đều tắt. Bộ test cuối: hai tầng giống hệt nhau, Chikapu chỉ cần lặp lại nước đi của Bash ở tầng còn lại.

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