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

Trò chơi kỳ lạ

Đề bài

Mô tả

Hai người chơi AB tham gia một trò chơi. Mỗi người được cho một xâu nhị phân độ dài 2n:

  • A có xâu s=s1s2s2n.
  • B có xâu t=t1t2t2n.

Hai người chơi luân phiên đi lượt, A đi trước. Trong mỗi lượt, người chơi chọn một chỉ số k trong {1,2,,2n} chưa được chọn bởi bất kỳ ai trước đó.

  • Nếu là lượt của AA chọn k thì A viết ký tự sk ra giấy của mình.
  • Nếu là lượt của BB chọn k thì B viết ký tự tk 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ố 0 đứ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 st, 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 n.
  • Dòng thứ hai chứa xâu s độ dài 2n gồm các ký tự 01.
  • Dòng thứ ba chứa xâu t độ dài 2n gồm các ký tự 01.

Dữ liệu ra

In ra một dòng duy nhất:

  • First nếu A thắng,
  • Second nếu B thắng,
  • Draw nếu hoà.

Ràng buộc

  • 1n106.
  • |s|=|t|=2n.
  • s,t chỉ gồm các ký tự 01.

Ví dụ

Input Output Giải thích
2
0111
0001
First A có thể chọn các vị trí 2,3 để viết được hai ký tự 1; B 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 B tận dụng được nhiều vị trí có tk=1 hơn so với số sk=1A thu được.

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