trang chủ / đề bài / weirdgame

Trò chơi kỳ lạ

Đề bài

Mô tả

Hai người chơi A và B 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=s1s2…s2n.
  • B có xâu t=t1t2…t2n.

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

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

  • 1≤n≤106.
  • |s|=|t|=2n.
  • s,t chỉ gồm các ký tự 0 và 1.

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=1 mà A 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.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