TLE '17 Contest 6 P3 - Spencer and Contest

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M
Author:
kobortor
Problem types
Spencer asking Andy for score booster tokens (2018, colorized).

Spencer really wants to go to the Canadian Computing Olympiad (CCO), the next stage of the Canadian Computing Competition (CCC). He wants to go so much that he cheated on the CCC. His master plan is the following:

  • Before the contest, Spencer goes to Andy, a CCC organizer, and buys "score booster tokens" worth an arbitrary positive integer amount of points to add to his score. Each token costs the same amount regardless of point value.
  • During the contest, Spencer activates the tokens to add to his score. His score increases by the point value of the token. The token cannot be used again.
  • ???
  • Profit!

Please note that Spencer isn't very good at programming, so he cannot score anything by himself without using tokens.

During the 2018 CCC, Spencer was disqualified as he got 77 / 75. Instead of giving up, Spencer registered an account under a different name to try again in the 2019 CCC.

To prevent future cheating, the CCC in the future will have a full score between 1 and N inclusive, and will be announced only when the contest starts. Spencer wants to make sure he is ready for the new CCC contest, so he can use the tokens to create any score between 1 and N, but also to make sure it's impossible to have a score over N. Given these requirements, help him find the minimum number of tokens he needs to buy!

Input Specification

The only input will be a single integer N (1 \le N \le 10^{18}).

For 40\% of the points, N \le 10.

Output Specification

First, print a single integer M, the minimum number of tokens he needs to buy.

In the next line, print M positive integers, the values of the tokens he should buy.

Sample Input 1

2

Sample Output 1

2
1 1

Sample Explanation 1

1 = 1
2 = 1 + 1

Sample Input 2

6

Sample Output 2

3
1 2 3

Sample Explanation 2

1 = 1
2 = 2
3 = 1 + 2
4 = 1 + 3
5 = 2 + 3
6 = 1 + 2 + 3

Comments


  • -2
    OneYearOld  commented on March 26, 2020, 9:46 p.m.

    1

    Spencer asking Andy for score booster tokens (2018, colorized).

    Picture: black and white.


  • 0
    felixzhang25  commented on April 8, 2018, 2:31 p.m.

    Sample Output 2

    3

    1 2 3

    Can it output it in a different order?


  • -6
    felixzhang25  commented on April 7, 2018, 4:30 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -1
    SuperCyther  commented on April 6, 2018, 2:09 a.m. ← edited

    Umm, can't you just use one number to token for the whole thing? ie: if N is equal to 5, just use a token worth 5


    • 1
      r3mark  commented on April 6, 2018, 2:14 a.m.

      He needs to be able to make any number from 1 to N, not just N.