trang chủ / bài tập / ticketgame

Trò chơi tấm vé

Đề bài

Mô tả

Ở Berland, mỗi tấm vé xe buýt gồm n chữ số (n chẵn). Một tấm vé được gọi là vé hạnh phúc nếu tổng n/2 chữ số đầu bằng tổng n/2 chữ số cuối.

Monocarp và Bicarp nhặt được một tấm vé mà một số chữ số đã bị xóa (số lượng chữ số bị xóa là chẵn). Hai người chơi một trò chơi: họ luân phiên đi, Monocarp đi trước. Trong mỗi lượt, người chơi hiện tại chọn một vị trí bị xóa bất kỳ và điền vào đó một chữ số từ 0 đến 9. Trò chơi kết thúc khi không còn vị trí bị xóa nào.

Nếu tấm vé cuối cùng là vé hạnh phúc thì Bicarp thắng, ngược lại Monocarp thắng. Hãy xác định ai thắng nếu cả hai chơi tối ưu.

Dữ liệu vào

  • Dòng đầu chứa số nguyên chẵn n (2n2·105) là số chữ số của tấm vé.
  • Dòng thứ hai chứa xâu gồm n ký tự, mỗi ký tự là chữ số hoặc dấu "?". Ký tự "?" thể hiện chữ số bị xóa. Vé có thể chứa số 0 ở đầu. Số lượng ký tự "?" luôn chẵn.

Dữ liệu ra

In ra "Monocarp" nếu Monocarp thắng, ngược lại in ra "Bicarp".

Ràng buộc

  • 2n2·105, n chẵn.
  • Số lượng ký tự "?" là số chẵn.

Ví dụ

Input Output Giải thích
4
0523
Bicarp Không có chữ số nào bị xóa, vé đã là vé hạnh phúc (0+5=2+3) nên Bicarp thắng ngay.
2
??
Bicarp Sau khi Monocarp điền một chữ số vào một vị trí, Bicarp điền đúng chữ số đó vào vị trí còn lại, hai nửa luôn bằng nhau.
8
?054??0?
Bicarp Với chiến lược tối ưu, Bicarp luôn cân bằng được hai nửa.
6
???00?
Monocarp Monocarp có cách điền khiến Bicarp không thể cân bằng hai nửa.

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.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0