CCC '03 J2 - Picture Perfect

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type
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 X


Of course, he could orient them in the other direction, such as


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.

Sample Input


Sample Output

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


  • -2
    sobko  commented on April 3, 2019, 7:36 p.m. edited

    I only seem to be getting 80/100 with only one test case even though it appears to meet all the requirements? Anybody got any ideas?

    Edit: Nvm my code did not work for when there was only 1 picture