trang chủ / đề bài / icpcwf14_h

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á 109. 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 w và h 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 u, d, l, r có tổng bằng 100, 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 h dòng tiếp theo chứa w 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á 10−6.

Ràng buộc

  • 1≤w≤20, 2≤h≤10000.
  • u,d,l,r≥0 và u+d+l+r=100.
  • 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á 109.

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 20, sang phải với 40 (và lên trên với 20 rồi lại rơi xuống), nên đích trái nhận 13, đích phải nhận 23.
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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0