Canadian Computing Competition: 2003 Stage 1, Junior #2
Roy has a stack of student yearbook photos. He wants to lay the pictures on a flat surface edge-to-edge to form a filled rectangle with minimum perimeter. All photos must be fully visible. Each picture is a square with dimensions 1 unit by 1 unit.
For example, he would place 12 photos in the following configuration,
where each photo is indicated with an
XXXX XXXX XXXX
Of course, he could orient them in the other direction, such as
XXX XXX XXX XXX
which would have the same perimeter, 14 units.
Your program should repeatedly read a positive integer ~C~, the number of pictures to be laid out. For each input, it should print the smallest possible perimeter for a filled rectangle that is formed by laying all the pictures edge-to-edge. Also print the dimensions of this rectangle.
You may assume that there are less than ~65\,000~ photos. An input value of ~C = 0~ indicates that the program should terminate.
100 15 195 0
Minimum perimeter is 40 with dimensions 10 x 10 Minimum perimeter is 16 with dimensions 3 x 5 Minimum perimeter is 56 with dimensions 13 x 15