ECOO '15 R2 P4 - Rectangle Roundup

View as PDF
Submit solution
Points: 12 (partial)
Time limit: 13.0s
Memory limit: 64M
Problem types

You have been given a set of rectangular and square tiles. Your job is to try and put this set of tiles together to form larger rectangles. The rectangles must be completely filled in. They can't be hollow and they can't contain any holes. You have to use all of the tiles you have been given for each larger rectangle you form.

The input will contain 10 test cases. The first line of each test case will consist of a single integer N on a line by itself (1 \le N \le 10). This will be followed by N lines, each containing two integers S_1 and S_2 representing the two side lengths of one of your tiles in centimetres (1 \le S_1, S_2 \le 5). The total area of all the tiles combined for each test case will be no more than 30 square centimetres.

For each test case you should output a single integer representing the largest perimeter it is possible to create with the tiles when you make rectangles following the rules set out above. If it is not possible to create any rectangles with the tiles you have been given, you should output the words Not Possible with both words capitalized.

Note that the sample input below only contains 3 test cases, but the real data files will contain 10.

Sample Input

3
3 2
2 2
1 2
4
1 1
1 1
1 1
1 1
3
3 2
1 1
1 3

Sample Output

16
10
Not Possible

Question Development Team

Sam Scott (Sheridan College)
Kevin Forest (Sheridan College)
Greg Reid (St. Francis Xavier Secondary School, Mississauga)
Dino Baron (University of Waterloo)
John Ketelaars (ECOO-CS Communications)
David Stermole (ECOO-CS President)
Thanks also to Lukasz Wawrzyniak (Sheridan College)

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org

Comments


  • 0
    Ken_Shi  commented on April 15, 2017, 11:30 p.m.

    Can someone change the memory limit to 128M? I got OutOfMemory Error, but I think in the actual contest it doesn't really matter ay?


    • 0
      kobortor  commented on April 16, 2017, 1:24 a.m.

      The current submissions pass with ~6 MB of memory. Even with java the memory hog you should pass with < 64MB.


      • 0
        Ken_Shi  commented on April 16, 2017, 11:56 p.m.

        I just wanna try out my thing... Is that possible to give me a chance?


        • 2
          Xyene  commented on April 17, 2017, 7:29 a.m.

          I ran your submission with a 256mb limit and it continued to MLE on the last 2 cases. Higher limits cannot reliably be judged, so you should look into optimizing your approach instead.


          • 0
            Ken_Shi  commented on April 17, 2017, 3:14 p.m.

            Alright, Thx a lot.