2003 Canadian Computing Competition, Stage 1
Problem J2: Picture Perfect
Roy has a stack of student yearbook photos. He wants to lay the pictures on a flat surtace edge-to-edge to form a filled rectangle with minimum perimeter. All photos must be fully visible. Each picture is a square with dimensions 1x1.
For example, he would place 12 photos in the following configuration. where each photo is indicated with an x:
xxxx xxxx xxxx
Of course, he could orient them in the other direction, like so:
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
Point Value: 3
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 27, 2008
- Simple Math
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3