Trò chơi tấm vé
Đề bài
Mô tả
Ở Berland, mỗi tấm vé xe buýt gồm chữ số ( chẵn). Một tấm vé được gọi là vé hạnh phúc nếu tổng chữ số đầu bằng tổng 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ừ đến . 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 () là số chữ số của tấm vé.
- Dòng thứ hai chứa xâu gồm 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
- , 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 () 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