DWITE '11 R5 #3 - Unit rectangles

View as PDF
Submit solution
Points: 3
Time limit: 2.0s
Memory limit: 64M
Problem type
DWITE Online Computer Programming Contest, December 2010, Problem 2

Rectangles can be constructed out of smaller squares. Given a supply of unit squares (1 \times 1 in size), how many unique rectangles can be constructed?

The input will contain 5 lines, each an integer 1 \le N \le 1\,000, the number of unit squares available.

The output will contain 5 lines, each a number of unique rectangles that can be constructed from up to N unit squares (not all squares have to be used for some of the rectangles).

Note: a rectangle is unique if another rectangle that had previously been constructed can't be rotated to look the same way. That is, 2 \times 3 and 3 \times 2 are considered to be the same.

Sample Input

2
6

Sample Output

2
8

Problem Resource: DWITE

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments


  • 2
    notpeachay420  commented on Aug. 18, 2020, 6:41 p.m.

    can someone help me make my code faster?


    • 3
      Kirito  commented on Aug. 19, 2020, 4:09 a.m. ← edited

      Try looking for patterns instead of iterating through all the numbers.

      If you consider the input 2^{29}, for example, the next number with the same binary weight is 2^{30}, which is around a half billion iterations away.

      Edit: As pointed out by sushi, 10^9 is a billion, not a trillion.


      • 5
        sushi  commented on Aug. 19, 2020, 2:01 p.m.

        Isn't 2^{30} around 1 billion? I'm sorry if I made a mistake.