BOUNCE - Trò chơi cờ bật

Giới hạn
  • Thời gian: 5.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

Đề bài

Có một trò chơi như sau. Có một bàn cờ 1xN gồm N ô đánh số 1..N từ trái sang phải và 1 quân xúc xắc có d mặt với xác suất rơi trúng mỗi mặt là như nhau. Hai người chơi thay phiên nhau đi, mỗi người chơi có một quân cờ. Mỗi lượt người chơi sẽ tung xúc xắc và di chuyển quần cờ của mình với số ô bằng số hiện ra trên xúc xắc. Ai đến được ô N trước là thắng.

Lưu ý là nếu vượt quá ô N quân cờ sẽ bật ngược về bên trái. Cụ thể, nếu a là ô hiện tại và b là kết quả tung xúc xắc thì:

  • Nếu a + b < n, quân cờ di chuyển đến (a+b)
  • Nếu a + b = n, quân cờ di chuyển đến n và người cầm quân thắng cuộc
  • Nếu a + b > n, quân cờ di chuyển đến ô (n-(a+b-n))

Cho n, d và vị trí ban đầu của mỗi quân cờ, tính xác suất để người đi trước thắng.

Dữ liệu

  • Mỗi test bắt đầu bằng thẻ "[CASE]", các test cách nhau bởi một dòng trắng. Thẻ "[END]" báo hiệu kết thúc file input.
  • Mỗi test gồm 4 dòng n, d, x, y, trong đó x, y là vị trí ban đầu của quân cờ của người đi trước và người đi sau.

Kết quả

  • Với mỗi test, in ra xác suất để người đi trước thắng với độ chính xác ít nhất 6 chữ số thập phân.

Giới hạn

  • 10 <= n <= 5000
  • 1 <= d, x, y <= n-1

Ví dụ 

Dữ liệu
[CASE]
10
6
1
1

[CASE]
10
2
1
1

[CASE]
100
20
1
10

[CASE]
10
5
9
1

[END]
Kết quả
0.5417251215862328
0.6090494791666666
0.49158887163174947
0.6943018666666667

  • Người up: voj
  • Nguồn bài: Member SRM 465, Div 1 - Level 3Người dịch: Ngô Minh Ðức