Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
BOUNCE - Trò chơi cờ bật |
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/bounce
Đề 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á. |