CEOI '18 P5 - Toys - Olympiads Online Judge

CEOI '18 P5 - Toys

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 2.5s

Memory limit: 256M

Problem types

Johnny collects toys. His collection may contain many toys of many different types: cars, trucks, diggers and many more. He may own more than one piece of the same toy, e.g. four trucks, in which case all the pieces are indistinguishable for him.

Emma asked Johnny how many toys he has. Not wanting to reveal the secret, he answered with a riddle (it is typical for him): If I chose a different set of my toys for each day, I could play for $n$ ~n~ days. In other words, for every two days there is a type of toy with a different quantity. Here, Johnny considers an empty set of toys as a valid set.

Emma likes neither the answer and nor this riddle, but she is really curious to know how many toys Johnny has. She asked you for help. Can you determine all possibilities of the number of toys that Johnny may have in his collection?

Input

The first (and the only one) line of the standard input contains an integer $n$ ~n~ $(1 \le n \le 10^9)$ ~(1 \le n \le 10^9)~.

Output

The first line of the standard output should contain one integer $r$ ~r~, the number of solutions (that is, the number of possibilities of the number of toys in Johnny's collection).

The second line should contain a strictly increasing sequence of $r$ ~r~ integers that represents the numbers of toys that Johnny may have in his collection.

Grading

The test set is divided into the following subtasks with additional constraints. Tests in each of the subtasks consist of one or more separate test groups. Each test group may contain one or more test cases.

Subtask	Constraints	Points
$1$ ~1~	$n \le 50$ ~n \le 50~	$19$ ~19~
$2$ ~2~	$n \le 10\,000$ ~n \le 10\,000~	$20$ ~20~
$3$ ~3~	$n \le 100\,000$ ~n \le 100\,000~	$20$ ~20~
$4$ ~4~	$n \le 10^8$ ~n \le 10^8~	$20$ ~20~
$5$ ~5~	no additional constraints	$21$ ~21~

Sample Input 1

Sample Output 1

4
4 5 6 11

Explanation for Sample Output 1

Johnny could have:

two trucks, one car, and one digger (4 toys in total)
three trucks and two cars (5 toys in total),
five trucks and one car (6 toys in total),
eleven trucks (11 toys in total).

Each of these options guarantees exactly 12 days of fun. For example, if he has eleven trucks, he can choose a set of $i - 1$ ~i - 1~ trucks on the $i$ ~i~-th day (for $i = 1, \dots, 12$ ~i = 1, \dots, 12~)

Sample Input 2

Sample Output 2

8
6 7 8 10 11 13 18 35

Explanation for Sample Output 2

Note that there are two different sets of 10 toys that guarantee 36 days of fun:

one truck, one car, and eight diggers,
five trucks and five diggers.

Still, only one of them is output.

To get 6 toys in total, Johnny could have one truck, one car, two diggers and two buses.

Comments

-1

ross_cleary commented on May 13, 2020, 10:49 p.m. ← edited →

I am getting a TLE on the last batch, but when I run my code for the $10^9$ ~10^9~ case on my compiler, it seems to run under 2.5 seconds. Can someone take a look at my code, thanks.

1

Plasmatic commented on May 15, 2020, 4:05 p.m.

https://gist.github.com/dario2994/fb4713f252ca86c1254d might be helpful

Note that $10^9$ ~10^9~ isn't always the worst case

1

ross_cleary commented on May 15, 2020, 6:12 p.m.

Ya this makes sense, I tested with a high factorial and my code took like 10 seconds to run so my algorithm is definitely sub-optimal. Thanks.