The socialist state of Karuka
All submissions for this problem are available.
The socialist state of Karuka is a beautiful circular island, with a huge lake in the middle. The N cities of Karuka are along the island, consecutively along the circle, consecutively numbered 0 ... N-1.
Each of the cities initially have some amount of wealth, given by an array W, of length N. Karukians are happy within themselves, and there is no mechanism to gain wealth in Karuka.
The only transfer of wealth that happens in Karuka, is this. On every day, the president of Karuka selects a city W[i], takes away (N-1) of it's wealth and gives 1 amount of wealth to each of the other cities. That is,
- W[i] <- W[i] - (N - 1)
- For all (j != i), W[j] <- W[j] + 1
To ensure that the principles of the socialist state are honored, the probability of selection of city i is set to be proportional to W[i], at every point. (this probability changes after every day, if W[i] changes)
As the president of Karuka, you are interested in the probability that each of the i'th cities is selected at the Kth day from now.
Note: today's transfer of wealth is yet to happen. (That is, a total of K transfers will happen before the Kth day).
There will be a single test case. The first line will contain two space separated integers, N and K.
The next line will contain N space separated integers, specifying the array W.
Output a N space separated real values, where the i'th one gives the expected wealth after K transfers, correct to an error of 10^-6
- 5 ≤ N ≤ 6*10^3
- 20 ≤ K ≤ 3*10^3
- K*(N-1) ≤ W[i] ≤ 10^9
- It is ensured that at most N-2 cities can possibly become worthless
Input: 5 20 100 100 101 101 100 Output: 100.07257380 100.07257380 100.89113929 100.89113929 100.07257380
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.