trang chủ / đề bài / icpc23_reg_d

Trận chiến chia đá

Đề bài

Mô tả

Để chuẩn bị cho giải vô địch Pokenom quốc gia, Bash và Chikapu thường chơi các trò chơi chiến thuật để rèn luyện trí óc.

Hôm nay, hai bạn nhặt được một ít đá trong khu rừng gần đó và chơi trò chơi sau:

  • Ban đầu, họ xếp các viên đá thành n đống, đống thứ i có ai viên. Họ cũng chọn một số nguyên k.
  • Hai người lần lượt đi, Bash đi trước.
  • Ở mỗi lượt, người chơi chọn một đống đá khác rỗng. Giả sử người chơi chọn đống thứ i và đống này đang có ci viên. Người chơi bỏ đi một số viên đá khỏi đống này sao cho số viên còn lại là ci−1 hoặc ⌊cik⌋.
  • Người không thể đi ở lượt của mình thua cuộc.

Cả Bash và Chikapu đều chơi tối ưu. Hãy xác định người thắng cuộc.

Nhắc lại, ⌊x⌋ là số nguyên lớn nhất không vượt quá x.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t (1≤t≤105), số bộ dữ liệu. Tiếp theo là t bộ dữ liệu, mỗi bộ có dạng:

  • Dòng đầu chứa hai số nguyên n và k (1≤n≤105, 2≤k≤100): số đống đá và số nguyên được chọn.
  • Dòng thứ hai chứa n số nguyên a1,a2,…,an (1≤ai≤1018): số viên đá của từng đống.

Dữ liệu bảo đảm tổng n của tất cả các bộ dữ liệu không vượt quá 105.

Dữ liệu ra

Với mỗi bộ dữ liệu, in trên một dòng tên người thắng cuộc, Bash hoặc Chikapu.

Ràng buộc

  • 1≤t≤105
  • 1≤n≤105, 2≤k≤100
  • 1≤ai≤1018
  • Tổng n của tất cả các bộ dữ liệu không vượt quá 105.

Ví dụ

Input Output Giải thích
2
1 2
1
4 2
7 7 6 6
Bash
Chikapu
Bộ thứ nhất: Bash lấy viên đá duy nhất và Chikapu không còn nước đi. Bộ thứ hai: các đống đá đi thành từng cặp bằng nhau, Chikapu chỉ cần lặp lại nước đi của Bash trên đống cặp đôi.
2
1 3
5
2 2
3 4
Chikapu
Bash
Ví dụ bổ sung. Bộ thứ nhất: từ 5 chỉ đi được tới 4 hoặc 1, và từ cả hai trạng thái này người đi tiếp đều thắng.

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