Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

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

Đề 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

Được gửi lên bởi:VOJ Team
Ngày:2010-06-05
Thời gian chạy:15s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:Member SRM 465, Div 1 - Level 3
Người dịch: Ngô Minh Đức

hide comments
2015-06-11 15:54:57 Silver Rayleigh
P/S nâng time lên 1 chút được ko. Bài này time chặt quá.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.