Máy Pachinko
Đề bài
Mô tả
Bạn vừa được hãng Addictive Coin Machines thuê để giúp thiết kế sản phẩm ăn khách tiếp theo trong dòng máy Pachinko bắt mắt, nuốt xu không ngừng, "chơi thêm một lần nữa thôi" của họ, dành cho các sòng bạc trên khắp thế giới.
Chơi một máy Pachinko là thả các viên bi vào một lưới hình chữ nhật chứa đầy chốt, vật cản và đích. Viên bi nảy khắp lưới cho tới khi cuối cùng rơi vào một trong các đích. Người chơi được một số điểm tùy theo đích mà viên bi rơi vào.
Mẫu lưới của máy Pachinko tiếp theo đã được thiết kế xong, nhưng điểm của các đích thì chưa được gán. Điểm phải được đặt sao cho, giống như mọi máy trong sòng bạc, chiếc máy có lãi nhưng không lãi quá nhiều. Vì vậy cần biết xác suất để viên bi rơi vào từng đích cụ thể. Đó là nhiệm vụ của bạn!
Để đơn giản, lưới được mô hình hóa thành một hình chữ nhật cao gồm phần lớn là các ô trống (mỗi ô ký hiệu là .), các vật cản không thể đi qua (ký hiệu X) và các đích (ký hiệu T).
Viên bi được thả ngẫu nhiên với xác suất đều vào một trong các ô trống ở hàng trên cùng của lưới. Từ đó trở đi, va chạm với các chốt làm viên bi nảy ngẫu nhiên lên trên, xuống dưới, sang trái hoặc sang phải với các xác suất cho trước. Để đơn giản, coi các xác suất này là như nhau ở mọi ô của lưới. Nếu viên bi nảy vào một vật cản hoặc định đi ra ngoài lưới thì nó thực ra không di chuyển khỏi ô hiện tại. Khi viên bi đi vào một đích, nó bị loại khỏi cuộc chơi.
Bạn có thể yên tâm giả sử rằng số ô trung bình mà viên bi đi qua trước khi rơi vào một đích không vượt quá . Một trò chơi mà viên bi nảy mãi không dừng thì chẳng vui chút nào!
Với mỗi đích, hãy tính xác suất để đó là đích mà viên bi được thả rơi vào.
Dữ liệu vào
Dữ liệu vào gồm một bộ test duy nhất. Dòng đầu tiên chứa hai số nguyên và là chiều rộng và chiều cao của lưới Pachinko. Dòng tiếp theo chứa bốn số nguyên không âm , , , có tổng bằng , lần lượt là xác suất (tính theo phần trăm) để viên bi nảy lên trên, xuống dưới, sang trái hoặc sang phải từ một ô trống bất kỳ.
Mỗi dòng trong dòng tiếp theo chứa ký tự, mỗi ký tự là ., X hoặc T. Các dòng này mô tả lưới Pachinko. Dòng đầu tiên mô tả hàng trên cùng của lưới, chứa ít nhất một ký tự . và không chứa ký tự T nào.
Dữ liệu ra
In ra một dòng cho mỗi ký tự T trong lưới, theo thứ tự từ trên xuống dưới, cùng hàng thì từ trái sang phải. Với mỗi đích, in ra xác suất để viên bi được thả rơi vào đích đó. Đáp án được chấp nhận nếu sai số tuyệt đối không vượt quá .
Ràng buộc
- , .
- và .
- Hàng trên cùng chứa ít nhất một ô
.và không có ôT. - Số ô trung bình viên bi đi qua trước khi rơi vào một đích không vượt quá .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 20 20 20 40 X.X T.T |
0.333333333 0.666666667 |
Viên bi luôn được thả vào ô giữa hàng trên. Từ một ô trống, các hướng bị chặn khiến viên bi đứng yên, nên chỉ cần so sánh xác suất các hướng đi được. Từ ô giữa hàng dưới, viên bi sang trái với xác suất , sang phải với (và lên trên với rồi lại rơi xuống), nên đích trái nhận , đích phải nhận . |
| 4 5 12 33 28 27 .... .XX. .... T..T XTTX |
0.435853889 0.403753221 0.081202502 0.079190387 |
Bốn đích theo thứ tự: hai đích ở hàng thứ tư (trái, phải), rồi hai đích ở hàng thứ năm (trái, phải). |
Bình luận