CCC '03 J2 - Picture Perfect

View as PDF
Submit solution
Points: 3 (partial)
Time limit: 2.0s
Memory limit: 256M
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.

XXXX
XXXX
XXXX

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

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

Comments


  • 0
    BULLET999  commented on Sept. 2, 2024, 3:55 a.m.

    If you're getting 40/100 and it's accepted then your program is on the right track but might not be checking all possible pairs of the rectangles width and length.


  • 0
    leoliu93233  commented on Jan. 31, 2024, 3:44 a.m. ← edited

    who voted 30 points theres no way this is harder than ccc 21 s2 there is also only 1 test case


  • 0
    aldenstripes  commented on Nov. 23, 2023, 6:44 p.m. ← edited

    To rnpmat08, your output says "Minimum Perimeter" instead of "Minimum perimeter".


  • 0
    Random_User1111  commented on Oct. 10, 2022, 2:15 a.m.

    My code is working perfectly fine in PyCharm and I also used the sample inputs (which outputted correctly), however I get a IR when I submit my solution. Does anybody what could be causing this problem?


  • 0
    Berton  commented on Sept. 6, 2022, 5:56 p.m.

    What is the test case?? On the first line I got

    Minimum perimeter is 32 with dimensions 10 x 6

    Isn't it correct (for 60)?


    • 3
      Random_User1111  commented on Oct. 7, 2022, 8:12 p.m.

      Try switching the 10 and 6 i.e. Minimum perimeter is 32 with dimensions 6 x 10


  • 3
    rnpmat08  commented on July 29, 2022, 3:10 a.m. ← edit 3

    Edit 2 Now: I used lowercase X, tweaked my code to make sure an input of 1 would give the correct answer, yet I'm still getting WA (Wrong Answer) and it says my output is just a snippet of what's expected. It works perfectly fine in my IDE, but why doesn't it pass DMOJ's judge test?


  • -1
    Tintin  commented on Jan. 2, 2021, 2:32 a.m.

    Can someone check my code, when I try the input on PyCharm it works fine but it doesn't seem to work on DMOJ


    • 3
      cabbagecabbagecabbage  commented on Jan. 2, 2021, 5:13 a.m. ← edited

      notice that you are outputting "Minimum perimeter is 32.0 with dimensions 6 x 10" indicating that you did division with "/" which returns a float instead of integer division "//" (line 13 in your most recent submission).

      as a side note i think they prefer people asking for help on the dmoj discord instead of the comment section


  • -1
    sobko  commented on April 3, 2019, 11: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


    • -1
      Misaka  commented on Oct. 6, 2022, 4:22 a.m.

      Thanks!!