Trò chơi palindrome

Đề bài

Mô tả

Hai người chơi cùng nhau chơi một trò chơi với xâu s gồm các chữ cái Latin in thường. Luật chơi như sau:

  • Hai người luân phiên đi nước. Người đi trước thực hiện nước đầu tiên.
  • Trong mỗi lượt, người chơi bắt buộc phải xoá đi đúng một ký tự bất kỳ trong xâu s.
  • Trước khi bắt đầu lượt của mình, nếu người chơi có thể sắp xếp lại các ký tự của s thành một xâu đối xứng (palindrome), thì người chơi đó thắng và trò chơi kết thúc ngay lập tức.

Nhắc lại: một xâu là đối xứng nếu nó đọc xuôi và đọc ngược đều cho cùng kết quả; chẳng hạn "abba" là đối xứng, còn "abc" thì không.

Cho xâu ban đầu s. Cả hai người chơi đều chơi tối ưu. Hãy xác định ai sẽ thắng cuộc.

Dữ liệu vào

Một dòng duy nhất chứa xâu s gồm các chữ cái Latin in thường.

Dữ liệu ra

In ra một dòng:

  • "First" nếu người đi trước thắng.
  • "Second" nếu người đi sau thắng.

(In ra không kèm dấu nháy.)

Ràng buộc

  • 1|s|103
  • s chỉ gồm các chữ cái Latin in thường.

Ví dụ

Input Output Giải thích
aba First Trước lượt đầu, "aba" đã là một palindrome — người đi trước thắng ngay.
abca Second "abca" không thể sắp xếp thành palindrome (có hai ký tự xuất hiện số lần lẻ: b và c). Dù người đi trước xoá ký tự nào, người đi sau cũng sẽ đối mặt với một xâu có đúng một ký tự xuất hiện số lần lẻ, sắp xếp được thành palindrome và thắng.
aabb First Có thể sắp xếp thành "abba", một palindrome — người đi trước thắng ngay.

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