Lesson 2:
Problem: 591
Title: Box of Bricks
Difficulty Level: 1
Date: Dec 04, 2008
Site: UVA
Some stacks of bricks with different height are given. you have to calculate how many bricks need to move to make all stacks equal height.
Let there are 4 stacks, each stack height is: 4 5 6 9 respectively, i.e each stack contains 4 5 6 9 bricks respectively. If we make all stack height even, then it will look like: 6 6 6 6 , i.e each stack will contain 6 bricks. how can we get this ? Very easy..
(4 + 5 + 6 + 9 ) / 4 = 6.
Now time to count moves. Consider 1st stack, it has 4 bricks, but we need 6 bricks, so we dont need to move any bricks from this stack. similar case for 2nd and 3rd stack. But for the 4th stack, we need 6 bricks, but it has more than 3 bricks. So we need to move 3 bricks. So our answer is: ( 0 + 0 + 0 + 3) = 3.
Input Specification: if you read the input specification, you can see 4 important issues:
1. maximum stack: 50
2. maximum height for each stack: 100
3.The total number of bricks will be divisible by the number of stacks. Thus, it is always possible to rearrange the bricks such that all stacks have the same height. So THERE IS ALWAYS A SOLUTION.
4.The input is terminated by a set starting with n = 0. This set should not be processed. i.e you have to print nothing for this input and your program will stop reading input.
Output Specification: Very important for beginners to learn something new. Your output format will be exactly same as mentioned in the output specification. Otherwise you will get 'Presentation Error'. Your output should be:
Set #1
The minimum number of moves is xxxxx.
Set #2
The minimum number of moves is xxxxx.
where xxxxx = actual output for each input. And most important factor is: Output a blank line after each set. Print a blank line (2 new lines )after each set of output, even after the last test case. Otherwise you will get 'Presentation Error'
New Term: 'Presentation Error'- Presentation Error is a one type of judge response which means that your output
format does not match judge's expected format even your output is correct. This may happen even for a single
extra line or space or other character. Be careful about this.Never print anything extra.
Source code: Visit my ACM UVA Solution achieve section