The team has been so focused on studying algorithms that they completely neglected the best kind of problems: those who require no classic algorithms at all! Fortunately, our friends at Yardi decided to help us give XORin, Lu-chan and Golgo a taste of what it's like to solve such a problem.
Given an integer N, find an array A of no more than 100 positive integers with the property that for each integer x (1 ≤ x ≤ N) there is at least one subarray of A whose sum is exactly x.
Input
The first line of input contains integer N.
Output
The first line of output should contain the number of elements in A.
The second line should contain all of A's elements, separated by a space.
Constraints
- 1 ≤ N ≤ 106
- 1 ≤ t ≤ 106 for every t in A
- It is guaranteed that at least one such array A exists.
- Subarray = subset. For example {1, 3} is a subarray of {1, 2, 3}
Sample
| Input | Output |
|---|---|
| 6 | 3 1 2 3 |
Since any number can be written as a sum of powers of 2, it is enough to print the powers of 2 from 20 to 220.
C solution (Marius Gavrilescu)
1 #include<stdio.h> 2 3 int main(void){ 4 int i; 5 puts("20"); 6 for(i = 0 ; i < 20 ; i++) 7 printf("%d ", 1 << i); 8 return 0; 9 }
Perl solution (Marius Gavrilescu)
1 #!/usr/bin/perl 2 use v5.14; 3 use warnings; 4 5 $, = ' '; 6 say 20; 7 say map { 1 << $_ } 0 .. 19;
Python solution (Sergiu Puscas)
1 print '20\n' + ' '.join([str(2**x) for x in range(0, 20)])
