Time Limit: 2 Seconds Memory Limit: 65536 KB
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).
Input
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.
Output
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.
Sample Input
1 2 100.00 100.00 1 2 2 1 2 2
Sample Output
75.00 125.00
<!-- Problem text file for ZheJiang University Online Judge Created by LiuYaoting -->
Note: the capacity of the container is not limited and all the pouring at every minute is processed at the same time.
题意:
给出 T 组样例,再给出 N 个水杯,后给出 N 个水杯的容量,后给出 N 行,首先第一行是 K,代表要讲这个杯里面的水要分给一下 K 个水杯,后给出 K 个水杯的编号。输出 M 时间后各个水杯剩下的水容量。输出两位小数。
思路:
矩阵快速幂。构成一个 N X N 的矩阵,对这个矩阵就 M 次方最后乘以 N X 1 的矩阵,输出这个 N X 1 的矩阵即为答案。至于这个矩阵是啥就不说明了。比赛的时候漏到了 k == 0 的情况了, K == 0 说明自己倒回自己那里,即不变,所以 fn = fn-1。所以赋值的时候应该 A [ i ] [ i ] = 1。
AC:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef vector<double> vec; typedef vector<vec> mat; mat mul (mat a, mat b) { mat c(a.size(), vec(b[0].size())); for (int i = 0; i < a.size(); ++i) { for (int j = 0; j < b[0].size(); ++j) { for (int k = 0; k < b.size(); ++k) { c[i][j] += a[i][k] * b[k][j]; } } } return c; } mat pow (mat a, int n) { mat b(a.size(), vec(a[0].size())); for (int i = 0; i < a.size(); ++i) b[i][i] = 1.0; while (n > 0) { if (n & 1) b = mul(b, a); a = mul(a, a); n >>= 1; } return b; } int main() { int t; scanf("%d", &t); while (t--) { int n; scanf("%d", &n); mat a(n, vec(n)); mat b(n, vec(1)); for (int i = 0; i < n; ++i) { scanf("%lf", &b[i][0]); } for (int i = 0; i < n; ++i) { int ans; double num; scanf("%d", &ans); num = 1.0 / (double)ans; if (!ans) a[i][i] = 1; else { while(ans--) { int k; scanf("%d", &k); --k; a[k][i] = num; } } } int m; scanf("%d", &m); a = pow(a, m); b = mul(a, b); for (int i = 0; i < n; ++i) { printf("%.2lf", b[i][0]); i == n - 1 ? printf("\n") : printf(" "); } } return 0; }
相关推荐
VHDL.2008.Just.the.New.Stuff英文版
C Programming - Just the FAQS,C语言编程的FAQ,描述C语言编程的注意事项
The C Language This chapter focuses on some basic elements of the C programming language. When you begin programming in C, you probably will find yourself coming up with basic questions regarding the ...
gem "just-the-docs" 并将此行添加到您的Jekyll网站的_config.yml : theme : just-the-docs 然后执行: $ bundle 或自己安装为: $ gem install just-the-docs 或者,您可以在开发站点时在Docker中运行它 $ ...
Don't just roll the dice, Don't just roll the dice
Just Keep Passing the Messages
C语言介绍(英文)作者Paul S. R. Chisholm
just download the file...and learn about the game
We useful code to restart the computer in 98, but just not the same in the NT system
WORK BOTF OR APPLE IRESERVE AS WOLARD CAN YOU JUST AMENDED THE DII FILE TO SAVE THE WORKD A BOT IS GOOD FOR YOUR DEVOLEOPMENT
A panel below the tree and just above the status bar display
Just to unlock the feature to download
C-Programming-Just-the-FAQS 中文版 C语言编程常见问题解答
a NULL skb means we just want the SPI chip line to raise.
this code just for open the pass for the 820 4 75 0 4
outside the clip. So we can t just fill where the user bits are 0. We also need to check that the clip bit is set.
We stash a pointer to the block header, just before the allocated space, so that we can decrement the live count on delete in constant time.
Windows 7 is a very robust piece of ... As the title suggests, I give you just the steps you need to do many of the most common Windows 7 tasks. This book is all about getting productive right away.
The IndigoDJ has no ASIC. Just do nothing.
XXX: This is just for liblustre. Remove the if defined directive when the cfs_ prefix is dropped cfs_list_head.