Cheerio Contest 3 P3 - Everything Array

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem types

Consider an array where each integer from 1 to N (inclusive) can be made by either adding or subtracting 2 numbers in the array. More rigorously, for every integer 1 \le n \le N there exists two indices i, j (i \ne j) such that A_i+A_j = n or A_i-A_j = n. Furthermore, each array element must be an integer in the range [1, N], though they do not have to be distinct.

Your goal is to find and construct such an array with a length of at most M.


Points Awarded N M
6 points 18 \le N \le 10^4 M = \lfloor 0.4N \rfloor
9 points 18 \le N \le 10^7 M = \lfloor\sqrt{2N}\rfloor

Input Specification

The only line of input contains two integers N and M.

Output Specification

The first line should contain an integer L, the length of the array A you have found.

The next line should contain L integers A_i (1 \le A_i \le N), the elements of the array.

Sample Input

18 7

Sample Output

2 3 16 4 8 5 13


There are no comments at the moment.