Computer Science Canada

CCC 2003 Stage1: J2: Picture Perfect

Author:  Tony [ Sat Mar 22, 2003 12:51 pm ]
Post subject:  CCC 2003 Stage1: J2: Picture Perfect

Roy has a stack of student yearbook photos. He wants to lay the pictures on a flat sufrace edge-to-edge to form a filled rectangle with minimum perimeter. All photos must by fully visible. Each picture is a square with dimentions 1 unit by 1 unit.
For example, he would place 12 photos in the following configuration, where each photo is indicated with an X


ofcourse, he could orient them in the other direction, such as


which would have teh same perimeter, 14 units.

Your problem should be interactive. It 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 alla the pictures edge-to-edge. Also print the dimensions of this rectangle.

You may assuem that there are less than 65,000 photos. An input value of C=0 indicated that the program should terminate.

Sample Session
Enter number of pictures:
Minumum perimeter is 40 with dimensions 10x10

Enter number of pictures:
Minumum perimeter is 16 with dimensions of 3x5

Enter number of pictures:
Minumun perimeter is 56 with dimensions 13x15

Enter number of pictures:

Solution by JSBN


var C : int
var z : int
var t2 : int
var d1 : int
var d2 : int


    put "Enter number of pictures"
    get C
    t2 := 65000
    exit when C = 0
    for i1 : 1 .. C
        for i2 : 1 .. C
            z := i1 * i2

            if z = C then
                if (i1 + i2) * 2 <= t2 then
                    t2 := (i1 + i2) * 2
                    d1 := i1
                    d2 := i2

                end if
            end if
        end for
    end for
    put "Minimum Perimeter is ", t2, " with the dimensions ", d1, " X ", d2
    put ""
end loop

I wish he would comment his solutions Confused basically two loops run through every possible rectangle size and just keeps track of the smallest perimeter it finds. Simple and easy.

Author:  Dan [ Sat Mar 22, 2003 12:59 pm ]
Post subject: 

i whode like to know how you whode do this if 64,999 is entred as a number. becuse that was one of the test values for the test. i lost a few points becuse my progame did not finsh in time.

Author:  Tony [ Sat Mar 22, 2003 1:21 pm ]
Post subject: 

rofl, If you would run my substring (S4) for those half a million char values... it would take a day for a single set... fortunatly (well for the teacher, not me) the program didnt execute over 65K solutions so it worked for 3/5 cases taking just few minutes each.

Edit: Doesnt answer your question, but something nice to know... the thing was inpossible in turing anyway as input for 4/5 cases was over 256 chars in length

Author:  octopi [ Sat Mar 22, 2003 3:49 pm ]
Post subject: 

Dan the number was acctually different, it wasn't 64999, it was a prime number 63907 I think it was. Anyways, as we know prime numbers only have 1, and themselves as factors. So it was kind of cheap of them to do that, I can't see many people passing that, unless there teachers let it run for days.

Any one else have any ideas on how to speed that one up?

Author:  Office of the Registar [ Fri Apr 25, 2003 9:10 am ]
Post subject: 

i think i have that was pretty short
let me look for it...