Trò chơi 0-1

Xem PDF

Điểm: 400 (p) Thời gian: 0.2s Bộ nhớ: 977M Input: bàn phím Output: màn hình

DeMen100ms là một người đam mê lập trình. Và hôm nay, DeMen100ms đã tạo ra một trò để chơi với Monarchuwu: DeMen100ms sẽ dùng máy tính để tạo ngẫu nhiên 1 dãy bit nhị phân trên đường tròn với độ dài \(k\) không quá \(1000\), và DeMen100ms luôn là người đi trước.

Sẽ có \(k\) lượt tương ứng với độ dài của dãy :

  • Lượt đầu tiên, DeMen100ms có thể chọn và xóa \(1\) số bất kì trong dãy bit
  • \(k - 1\) lượt tiếp theo, mỗi bên sẽ chọn xóa số liền kề trên đường tròn (trái hoặc phải) so với số mà đối phương lựa chọn ở lượt trước.

Các lưu ý :

  • Bên thắng là bên xóa được nhiều bit số \(1\) hơn
  • Sau khi xóa, dãy sẽ tự động lại gần với nhau. Ví dụ : Xóa ký tự thứ \(2\) của '010' -> '00'
  • 2 bên luôn chơi tối ưu.

Nhưng sau khi đọc luật chơi, Monarchuwu cho rằng trò chơi quá OP nên anh ta đã đề nghị ở lượt đầu, DeMen100ms phải chọn một vị trí ngẫu nhiên để trò chơi trở lại vị trí cân bằng. Và nhiệm vụ của bạn (với vai trò là cộng sự của DeMen100ms) là hãy tính giúp DeMen100ms tỉ lệ phần trăm mà DeMen100ms có thể thắng Monarchuwu (Biết sau lượt thứ nhất, cả hai người đều chơi tối ưu)

Input

  • Nhập 1 dòng duy nhất là dãy bit được tạo ngẫu nhiên bởi máy tính (Độ dài của dãy bit không vượt quá \(1000\))

Output

  • Đáp án của bài toán (Làm tròn đến \(2\) chữ số thập phân)

Example

Test 1

Input
1010
Output
50.00
Note

DeMen100ms có thể thắng nếu bắt đầu từ vị trí 1 hoặc 3 và không thể thắng nếu bắt đầu từ vị trí 2 hoặc 4

  • Nếu DeMen100ms bắt đầu từ vị trí 1, lượt tiếp theo Monarchuwu phải chọn xóa vị trí 4 hoặc 2 (đều là số 0). Bất kể thế nào, lượt tiếp theo DeMen100ms sẽ xóa vị trí 3 và thắng với 2 điểm.
  • Nếu DeMen100ms bắt đầu từ vị trí 2, lượt tiếp theo Monarchuwu phải chọn xóa vị trí 3 hoặc 1. Monarchuwu sẽ chọn xóa vị trí 1. Lượt tiếp theo, DeMen100ms sẽ xóa vị trí 3. Cuối cùng Monarchuwu xóa vị trí 4. Hai bạn hòa nhau vì cùng có 1 điểm.

Dưới đây là minh họa cho trường hợp DeMen100ms bắt đầu từ vị trí 1. Các hình tròn màu xanh là các ô DeMen100ms chọn xóa, các hình tròn màu đỏ là các ô Monarchuwu chọn.


Bình luận

Không có bình luận nào.