Powerpuff girls Beebo
All submissions for this problem are available.
Professor Utonium created a pet called Beebo, but he told The Powerpuff Girls they must only feed him once, they fed him more than once which turning him into a giant monster and eating everything in Townsville then explode because he over ate, turning into a bunch of small cute little Beebo's for everyone. Professor Utonium discovered that all the Beebo’s can once again be made into one little Beebo by adding all of them. You have to add the Beebos such as:
There are n piles of Beebos of sizes b1, b2, ..., bn lying on the floor in front of you.
During one move you can take one pile of Beebo and add it to the other. As you add pile x to pile y, the size of pile y increases by the current size of pile x, and pile x stops existing. The cost of the adding operation equals the size of the added pile.
Your task is to determine the minimum cost at which you can gather all Beebos in one pile.
To add some challenge, the piles of Beebos built up conspiracy and decided that each pile will let you add to it not more than t times (after that it can only be added to another pile).
Moreover, the piles of Beebos decided to puzzle you completely and told you q variants (not necessarily distinct) of what t might equal.
Your task is to find the minimum cost for each of q variants.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows
The first line of each test case contains integer n — the number of piles of Beebos. The second line contains n space-separated integers: b1, b2, ..., bn — the initial sizes of the piles of Beebos.
The third line contains integer q -- the number of queries. The last line contains q space-separated integers t1, t2, ..., tq -- the values of number t for distinct queries. Note that numbers ti can repeat.
Print q whitespace-separated integers -- the answers to the queries in the order, in which the queries are given in the input.
- 1 ≤ T ≤ 100
- 1 ≤ n ≤ 105
- 1 ≤ bi ≤ 109
- 1 ≤ q ≤ 105
- 1 ≤ ti ≤ 105
Input: 1 5 2 3 4 1 1 2 2 3 Output: 9 8
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, PYTH 3.6, 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, CLOJ, FS|
Fetching successful submissions