KOPC12A - K12 - Building Construction
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.
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.
The output must contain T lines each line corresponding to a testcase.
1 3 1 2 3 10 100 1000 Output:
two words: ternary search
Easy using binary search!!!
what is the order of this???
learnt a lot....nice question
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 :(
I actually enjoyed solving this, we need more original problems like this..
@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
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
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?