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.

Sample Input

100
15
195
0

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

All Submissions
Best Solutions

Point Value: 3
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 27, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

I am unsure of how to post a question regarding my code on this site without directly pasting it, I also can't find it anywhere online, can someone tell me?

Read the replies to your previous comment. Further comments without demonstration that you've made some effort at solving this yourself may disappear without warning.

My code works perfectly, not sure whether something is wrong with my time, can someone help me out.
[admin note: code removed]

Please don't post your code in your comment. People who have solved the question can look at your answer and help you.

Your code does not at all work perfectly. Try testing it out on some more cases.

Come up with some input numbers, work out the answers by hand, then run your program with them.

https://www.google.ca/search?q=good+question+meme&rlz=1C1OCLT_enCA759CA759&source=lnms&tbm=isch&sa=X&ved=0ahUKEwjRwIiuv-vVAhXC3YMKHbevCvMQ_AUICigB&biw=1130&bih=647#imgrc=lGeK9t-s358foM:

Should the output be smaller side first for dimensions of the rectangle? It looks that way in the sample.

Sorry for the late response. Yes, please do this.

Uh.. with what?

Can admin check if I am doing something wrong or not. It seems to be working fine but it gave me a pretty vague error.

You're receiving a TLE (time limit exceeded) error because your code is too slow. You should try something different.

I'm using a simple method of finding the possible factors of C, and check which one would give the smallest perimeter. With this solution I get Time Limit Exceeded (TLE) all the time. Is my solution wrong mathematically, or should I try to optimize the program?

You can find the two factors with the smallest perimeter without actually calculating the perimeter for every factor.
Try to find the connection between the factors and perimiter.
Good luck!

Could someone help me out? My code works on the test cases.

Make more test cases? And try them out?

[code removed]

Please see [url=http://wcipeg.com/comments/view#3719]this comment[/url]. Note also that if you've submitted, you don't have to post your code; you can just ask us to check your latest submission, for instance.

So what is wrong about my code because it work good in my pc?

Your while(x>0) loop never runs. Note that your x variable is uninitialised.

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.

my program is optimal than your because in the input 3 with 195 pictures the minimum perimeter is 16 with 3 x 65 . you can check it by yourself.
please check the problem again and check my answer.

The perimeter of 3 x 65 is actually 136. 3*2+65*2=136.