Trò chơi cờ bật

View as PDF

Submit solution

Points: 1.86 (partial)
Time limit: 45.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Member SRM 465, Div 1 - Level 3Người dịch: Ngô Minh Ðức
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Có một trò chơi như sau. Có một bàn cờ ~1 \times N~ 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.

Input

  • 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.

Output

  • 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 \le n \le 5000~
  • ~1 \le d,x, y \le n-1~

Sample Input

[CASE]
10
6
1
1

[CASE]
10
2
1
1

[CASE]
100
20
1
10

[CASE]
10
5
9
1

[END]

Sample Output

0.541725121586
0.609049479167
0.491588871632
0.694301866667

Comments

Please read the guidelines before commenting.


There are no comments at the moment.