Trò chơi kỳ lạ
Đề bài
Mô tả
Hai người chơi và tham gia một trò chơi. Mỗi người được cho một xâu nhị phân độ dài :
- có xâu .
- có xâu .
Hai người chơi luân phiên đi lượt, đi trước. Trong mỗi lượt, người chơi chọn một chỉ số trong chưa được chọn bởi bất kỳ ai trước đó.
- Nếu là lượt của và chọn thì viết ký tự ra giấy của mình.
- Nếu là lượt của và chọn thì viết ký tự ra giấy của mình.
Trò chơi kết thúc khi không còn chỉ số nào chưa được chọn. Sau đó, mỗi người sắp xếp các ký tự đã viết theo thứ tự tuỳ ý để tạo thành một số nguyên (cho phép có chữ số đứng đầu). Người nào tạo được số lớn hơn sẽ thắng. Nếu hai số bằng nhau, kết quả là hoà.
Cho hai xâu và , hãy xác định kết quả của trò chơi khi cả hai cùng chơi tối ưu.
Dữ liệu vào
- Dòng đầu chứa số nguyên .
- Dòng thứ hai chứa xâu độ dài gồm các ký tự
0và1. - Dòng thứ ba chứa xâu độ dài gồm các ký tự
0và1.
Dữ liệu ra
In ra một dòng duy nhất:
Firstnếu thắng,Secondnếu thắng,Drawnếu hoà.
Ràng buộc
- .
- .
- chỉ gồm các ký tự
0và1.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 0111 0001 |
First | có thể chọn các vị trí để viết được hai ký tự 1; chỉ có thể lấy được tối đa một ký tự 1. |
| 3 111000 000111 |
Draw | Mỗi người có đúng ba ký tự 1 ở các vị trí khác hẳn nhau, dẫn đến hoà. |
| 4 01100000 10010011 |
Second | tận dụng được nhiều vị trí có hơn so với số mà thu được. |
Bình luận