Want to try solving this problem? You can submit your code online if you log in or register.
It is the start of a new year at Petit's School for Proper and Well-Balanced Children, and as the Chief Record Keeper it is your job to take the school photograph. Your training in the art houses of Europe has taught you that form is more important than content--with this in mind, you decide that it does not matter who is in the photograph as long as it looks good.
You decide to form R rows of children, with C children in each row. For each row, the imbalance of the row is the difference between the height of the shortest student in that row and the height of the tallest student in that row. The imbalance of the entire photograph is the largest imbalance seen in any of the rows.
There are N students in the school, all of whom are eager to have their photo taken. To save your reputation as both an artist and a well-balanced teacher, your task is to choose R x C of these students for your photograph so that the imbalance of the photograph can be made as small as possible.
As an example, suppose there are N=8 students in the school, with the
following heights (all measured in centimetres):
Row 1: | Heights 225, 205, 225 | |
Row 2: | Heights 160, 190, 170 |
The imbalance of row 1 is 225-205 = 20, and the imbalance of row 2 is 190-160=30. Therefore the imbalance of the entire photograph is (20,30)=30, which in fact is the smallest imbalance possible.
For 100% of the available marks:
Your program must read from standard input. The first line of input will contain the integers N R C, as described above. Following this will be N additional lines of input, each giving the height of a student (measured in centimetres).
Your program must write a single line to standard output. This line must contain a single integer, giving the smallest possible imbalance for your photograph (again in centimetres).
8 2 3 170 205 225 190 260 130 225 160
30
The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.
Privacy
statement
© Australian Mathematics Trust 2001-2021
Page generated: 21 October 2021, 6:50pm AEDT