Sphere Online Judge

SPOJ Problem Set (classical)

10514. K12 - Building Construction

Problem code: KOPC12A


 

         Given N buildings of height h1,h2,h3...hn, the objective is to make every building has equal height. This can be done by removing bricks from a building or adding some bricks to a building.Removing a  brick or  adding  a brick is done at certain cost which will be given along with the heights of the buildings.Find the minimal cost at which you can make the buildings look beautiful by re-constructing the buildings such that the N buildings satisfy 

h1=h2=h3=..=hn=k ( k can be any number).

For convenience, all buildings are considered to be vertical piles of bricks, which are of same dimensions. 

 

         Given N buildings of height h1,h2,h3...hn, the objective is to make every building has equal height. This can be done by removing bricks from a building or adding some bricks to a building.Removing a  brick or  adding  a brick is done at certain cost which will be given along with the heights of the buildings.Find the minimal cost at which you can make the buildings look beautiful by re-constructing the buildings such that the N buildings satisfy 
h1=h2=h3=..=hn=k ( k can be any number).

Input

 

The first line of input contains an integer T which denotes number of test cases .This will be followed by 3*T lines , 3 lines per test case. The first line of each test case contains an integer n and the  second line contains n integers which denotes the heights of the buildings [h1,h2,h3....hn] and the third line contains n integers [c1,c2,c3...cn] which denotes the cost of adding or removing one unit of brick from the corresponding building.

T<=15;n<=10000;0<=Hi<=10000;0<=Ci<=10000;

Output

 

The output must contain T lines each line corresponding to a testcase.

 

Example

Input:
1
3
1 2 3
10 100 1000


Output:
120


Added by:Radhakrishnan Venkataramani
Date:2012-01-31
Time limit:1s-3s
Source limit:50000B
Memory limit:256MB
Cluster: Pyramid (Intel Pentium III 733 MHz)
Languages:All
Resource:Own

hide comments
2014-06-27 18:39:51 zicowa
i think it would be a good problem if constraints are well assigned these two statements are non meaningfull to my senses H==0 and cost==0 :(
2014-03-20 04:29:57 Alex Abbas
I actually enjoyed solving this, we need more original problems like this..
@Problem Setter: Can you tell if there is another approach to this problem other than my solution??
2012-04-13 08:46:22 Petar VeliŔkoviŠ
@Aleksandar: It doesn't matter. Although I find it more convenient to do it right after a single testcase is finished, and that's the approach I took. My solution got AC without problems.

Last edit: 2012-04-13 08:47:51
2012-04-04 22:32:11 Cleo
Yeah, I have the same question as Alexandar. Whenever I upload code I get 'Wrong answer', although it gave me correct answer for every single test I came up with... Am I missing something?

Last edit: 2012-04-04 22:33:28
2012-04-04 22:11:01 Aleksandar
If we have more than one test, should we print result after each test is finished, or should we print them all after all tests are finished?
2012-04-04 15:36:42 Dejan Tomic
It is okay people, I understood that. Now the problem is not so trivial. But I think I found a solution for this too...
2012-04-04 00:10:13 Nebojsa Bobic


Last edit: 2012-04-04 00:10:56
2012-04-03 17:15:58 Eros Lorand
You can not "move" bricks, you have to build new ones, or destroy the old ones.
2012-04-03 08:18:05 manish kapoor
i thnk we have to add a brick from outside.i mean ,brick need not be from other building.Ex-add a brick to 2 and two bricks to 1.Total cost = 120
Height of all the buildings = 3

Last edit: 2012-04-03 08:18:54
2012-04-03 04:13:13 LeppyR64
K=3 All n buildings must be the same height. Height of zero doesn't decrease n. removing from one building is an action on that building. Adding it to another is another action on the other building. 10 to add a brick to the frst building twice is 20. 100 to add a brick to second building is 120.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.