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

ETI07E4 - Spadająca kulka

W pewnej grze komputerowej akcja toczy się na prostokątnej planszy złożonej z kwadratowych pól o rozmiarze jednostkowym. Wyróżnia się tylko pola całkowicie puste i całkowicie pełne.

Na potrzeby symulacji w świecie tym zdefiniowano dosyć specyficzne prawa fizyki. Przypuśćmy, że w pewnym pustym polu zostanie umieszczona i puszczona swobodnie mała kuleczka. Wówczas na początku każdej jednostki czasu znajduje się ona zawsze w całości w pewnym pustym polu. W ciągu jednostki czasu kulka wykonuje ruch zgodnie z następującymi zasadami:

  • Kulka znajdująca się na pustym polu, pod którym nie ma pola pełnego, wykonuje zawsze ruch o jedno pole w dół.
  • Kulka znajdująca się na pustym polu, pod którym jest pole pełne, wykonuje z równym prawdopodobieństwem ruch albo o jedno pole w lewo, albo o jedno pole w prawo. Wybrany ruch nie zostaje jednak wykonany, jeżeli pole docelowe jest pełne.

Kulka, przemieszczając się, może wypaść poza planszę (wszystkie pola wokół planszy należy traktować jako puste).

Znając używaną w grze planszę oraz położenie początkowe kulki, należy wyznaczyć prawdopodobieństwo, że tor kulki przejdzie przez wskazane puste pola.

Wejście

Wejście rozpoczyna się od dwóch liczb całkowitych y x oddzielonych spacją, określających wymiary planszy (1 <= x, y <=100). W każdym z kolejnych y wierszy znajduje się opis rzędów planszy (poczynając od góry), złożony z dokładnie x znaków, określających zapełnienie poszczególnych pól rzędu. Pole zajęte zapisane jest zawsze w postaci znaku 'x', a pole puste jako jeden ze znaków {'*', '1', '2', '3', '.'}. Każdy ze znaków {'*', '1', '2', '3'} pojawia się dokładnie raz w całej planszy, a znak '*' opisuje położenie początkowe kulki.

Można przyjąć, że w jednym rzędzie planszy pola pełne nigdy do siebie bezpośrednio nie przylegają.

Wyjście

Wyjście składa się z dokładnie trzech wierszy, w których należy kolejno podać prawdopodobieństwa przejścia kulki przez puste pola oznaczone '1', '2', '3'. Wartość prawdopodobieństw powinna być określona dokładnie (bez zaokrąglenia czy obcięcia) w postaci ułamka dziesiętnego. Należy zawsze wybrać najkrótszy poprawny zapis ułamka.

Przykłady

 

Zestaw przykładowy 1

Wejście:

9 7
.......
...*...
.......
...x...
.......
..x.x..
.......
.1.2.3.
.......


Wyjście:
0.25
0.5
0.25


Ilustracja przykładu 1
Ilustracja przykładu 1

Zestaw przykładowy 2

Wejście:
5 5
..*.3
..x..
.x.x2
.....
x1...



Wyjście:
0.25
0.5
0


Dodane przez:adrian
Data dodania:2006-11-11
Limit czasu wykonania programu:0.444s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU

ukryj komentarze
2011-05-11 10:15:53 Piotr KÄ…kol
@Krzysztof Lewko - Nie:
"Można przyjąć, że w jednym rzędzie planszy pola pełne nigdy do siebie bezpośrednio nie przylegają."
Gdyby przylegały wynikiem dla 1 byłoby oczywiście:
1
0
0
Jako że pola 1, 2 i 3 są puste (więc po jedynce kulka spadłaby w dół).
2011-05-11 08:31:24 Krzysztof Lewko
Czy może wystąpić taki in :
.*........
x.........
xxxxxxx123


Jakie jest prawdopodobieństwo dla jedynki ? 1 ?

Ostatnio edytowany: 2011-05-11 10:10:14
2010-11-16 22:15:50 Ewa Piotrowska
Faktycznie, nie zauważyłam, że klocek stoi niżej. Dzięki za bardzo wyczerpujące wyjaśnienia, pozdrawiam:)
2010-11-11 14:03:45 Piotr KÄ…kol
Też na początku tego nie widziałem, ale przecież kulka nie może spaść do środka. Poza tym "Kulka, przemieszczając się, może wypaść poza planszę (wszystkie pola wokół planszy należy traktować jako puste)."

Nie takie ładne jak ilustracja do przykładu pierwszego, ale lepszy rydz niż nic. ;-)

Ostatnio edytowany: 2010-11-11 14:05:04
2010-11-09 21:47:44 Ewa Piotrowska
Ja bym powiedziała, że w drugim przykładzie to pole nr 1 ma prawdopodobieństwo 0.5, a 2 - 0.25. Wkońcu 2 ma sytuację analogiczną jak w pierwszym 1 i 3.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.