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
[admin note: code removed]
Come up with some input numbers, work out the answers by hand, then run your program with them.
Try to find the connection between the factors and perimiter.
Also: the comment states that if you'd like to ask for help, you should do so on either the IRC server or the forums. Any further questions asked in comments will simply be deleted.
please check the problem again and check my answer.