DWITE '11 R5 #3 - Unit rectangles - DMOJ: Modern Online Judge

DWITE '11 R5 #3 - Unit rectangles

View as PDF

Submit solution

All submissions

Best submissions

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$ $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$ $1 \leq N \leq 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$ $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$ $2 \times 3$ and $3 \times 2$ $3 \times 2$ are considered to be the same.

Sample Input

Copy

2
6

Sample Output

Copy

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}$ $2^{29}$ , for example, the next number with the same binary weight is $2^{30}$ $2^{30}$ , which is around a half billion iterations away.

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

5

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

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