Problem 1985 --Just Pour the Water

1985: Just Pour the Water

正确率: $66.67\%$ 下一题

Description

Shirly is a very clever girl. Now she has two containers (A and B), each with some water. Every minute,

she pours half of the water in A into B, and simultaneous pours half of the water in B into A. As the

pouring continues, she finds it is very easy to calculate the amount of water in A and B at any time. It is

really an easy job :).

But now Shirly wants to know how to calculate the amount of water in each container if there are more

than two containers. Then the problem becomes challenging.

Now Shirly has N (2 <= N <= 20) containers (numbered from 1 to N ). Every minute, each container is

supposed to pour water into another K containers ( K may vary for different containers). Then the water

will be evenly divided into K portions and accordingly poured into anther K containers. Now the question

is: how much water exists in each container at some specified time?

For example, container 1 is specified to pour its water into container 1, 2, 3. Then in every minute,

container 1 will pour its 1/3 of its water into container 1, 2, 3 separately (actually, 1/3 is poured back to

itself, this is allowed by the rule of the game).

Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <=

10) which is the number of test cases. And it will be followed by T consecutive test cases.

Each test case starts with a line containing an integer N , the number of containers. The second line

contains N floating numbers, denoting the initial water in each container. The following N lines describe

the relations that one container(from 1 to N ) will pour water into the others. Each line starts with an

integer K (0 <= K <= N ) followed by K integers. Each integer ([1, N ]) represents a container that should

pour water into by the current container. The last line is an integer M (1<= M <= 1,000,000,000) denoting

the pouring will continue for M minutes.

For each test case, output contains N floating numbers to two decimal places, the amount of water

remaining in each container after the pouring in one line separated by one space. There is no space at

the end of the line.

1
2
100.00 100.00
1 2
2 1 2
2

75.00 125.00

the capacity of the container is not limited and all the pouring at every minute is processed at the

same time.

本题记录	用户（点击查看用户）	运行号（点击购买题解）	时间
算法最快[$388 $ms]	范晋豪@信息与计算科学142	108894	2017-07-02 23:10:47
内存最少[$960 $KB]	范晋豪@信息与计算科学142	108894	2017-07-02 23:10:47
第一AC	范晋豪@信息与计算科学142	108894	2017-07-02 23:10:47
第一挑战	范晋豪@信息与计算科学142	108894	2017-07-02 23:10:47

竞赛编号	竞赛名称	竞赛时间	访问比赛