시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 31 | 23 | 21 | 75.000% |
Model a stochastic gym exercise.
An entertaining game for elementary school children in gym class is set up as follows:
The game proceed as follows: the children gather at a specified start basket. They each take a turn picking a random card from the basket, memorizing the destination, and returning the card before the next child picks one. When the teacher blows the whistle, all the children move to the basket indicated on the notecard.
Given the configuration of index cards at each basket, you are to determine the probabiliites a kindergardener will appear at each basket for the first ten steps of the game.
For example, suppose there are four baskets, "tree," "house," "car" and "park." Each basket has the following index cards:
This arrangement is summarized by the following table:
destination | ||||
basket | tree | house | car | park |
tree | 2 | 1 | 2 | 0 |
house | 1 | 0 | 1 | 2 |
car | 1 | 0 | 0 | 0 |
park | 1 | 1 | 1 | 1 |
Everyone starts at the tree, so initially,
In the middle of the game, the probablity of being at some new location is equal to the sum of the probabilities of being at any location on the previous step, times the probablity of moving to the destination location from that past location. For the example,
For N baskets, 2<=N<=10, the input file will contain N lines of information. The N lines will give the index card count as in the table for the example above. There will be at most 10 cards of the same name in any given basket, and each basket will contain at least one card.
There should be 10 lines of output for any given input. Other than the standard header and footer, you should print out the probabilites for seeing a kindergardener at any given basked for the first 10 steps in the game.
Your results should give the correct probablities to at least four digits of precision. We recommend you do the internal computations using double precision arithmetic.
2 1 2 0 1 0 1 2 1 0 0 0 1 1 1 1
1.00000 0.00000 0.00000 0.00000 0.40000 0.20000 0.40000 0.00000 0.61000 0.08000 0.21000 0.10000 0.49900 0.14700 0.28900 0.06500 0.54160 0.11605 0.25260 0.08975 0.52069 0.13076 0.26809 0.08046 0.52917 0.12425 0.26108 0.08549 0.52519 0.12721 0.26411 0.08350 0.52686 0.12591 0.26275 0.08448 0.52609 0.12649 0.26334 0.08408