KOPC12A - K12 - Building Construction

no tags 

 

         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


hide comments
nurlansofiyev: 2016-07-17 23:17:42

There is 2 algorithm. one is O(nlogn) . other algorithm run O(10000) in worst case (without binary and ternary search)

Last edit: 2016-07-17 23:59:27
SUBHAJIT GORAI: 2016-03-16 08:12:57

elegant O(n) solution ...no need of binary or ternary search

Deepak : 2016-03-03 21:21:35

ternary search.. :)

sharif ullah: 2016-02-18 21:22:40

re constructing !!!!!!!!!!!!!
so,
3
0 0 0
1 1 1

mkmostafa: 2015-08-24 00:43:42

two words: ternary search

ANKIT TAPARIA: 2015-06-24 18:55:29

Easy using binary search!!!

jonty007: 2015-02-05 11:58:16

2
3
0 0 0
1 1 1
3
0 0 1
1 1 1
output???

Last edit: 2015-02-05 11:58:57
lucky: 2014-12-27 15:12:29

what is the order of this???

Ayush Vatsa: 2014-10-20 21:09:59

learnt a lot....nice question

though test cases are weak

Last edit: 2014-10-21 06:09:40
zicowa: 2014-06-27 18:39:51

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 :(


Added by:Radhakrishnan Venkataramani
Date:2012-01-31
Time limit:0.139s-0.665s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own