Anti-knapsack
Contest: Codeforces Round 705 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy

You are given two integers $$$n$$$ and $$$k$$$. You are asked to choose maximum number of distinct integers from $$$1$$$ to $$$n$$$ so that there is no subset of chosen numbers with sum equal to $$$k$$$.

A subset of a set is a set that can be obtained from initial one by removing some (possibly all or none) elements of it.

Input format:
The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 100$$$).

Each of the next $$$T$$$ lines contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 1000$$$) — the description of test cases.

Output format:
For each test case output two lines. In the first line output a single integer $$$m$$$ — the number of chosen integers.

In the second line output $$$m$$$ distinct integers from $$$1$$$ to $$$n$$$ — the chosen numbers.

If there are multiple answers, print any. You can print the numbers in any order.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
3
3 2
5 3
1 1

Example output:
2
3 1 
3
4 5 2 
0

Editorial:
Let's notice that we can take all numbers $$$k+1, k+2 \ldots n$$$, because every one of them is greater than $$$k$$$, and sum of any number from $$$k+1, k+2 \ldots n$$$ and any number from $$$1,2 \ldots n$$$ also is greater than $$$k$$$. Let's also take numbers from $$$\left \lceil \frac{k}{2} \right \rceil$$$ to $$$k - 1$$$ inclusive. Notice that the sum of any two chosen numbers is already greater than $$$k$$$, and no chosen number is equal to $$$k$$$, therefore such set is correct. It contains $$$(n - k) + (k -\left \lceil \frac{k}{2} \right \rceil) = n - \left \lceil \frac{k}{2} \right \rceil$$$ numbers.
Let's show why such size of a set is the maximal possible. Numbers from $$$k+1$$$ to $$$n$$$ won't give subsets with sum $$$k$$$ with any other numbers, so we can take them to the answer: their amount is $$$n - k$$$. The number $$$k$$$ can't be taken to the answer, because if we take a subset consisting from that number only, the sum in it will be $$$k$$$. Let's consider numbers from $$$1$$$ to $$$k-1$$$. They can be divided into $$$\left \lfloor \frac{k}{2} \right \rfloor$$$ pairs, in each of which the sum of numbers will be $$$k$$$ ($$$1$$$ and $$$k-1$$$, $$$2$$$ and $$$k-2$$$ etc.; if $$$k$$$ is even, then the pair with number $$$\frac{k}{2}$$$ will consist of one number). If we took at least $$$\left \lfloor \frac{k}{2} \right \rfloor + 1$$$ numbers from $$$1$$$ to $$$k-1$$$, then at least two chosen numbers will be in one pair, and their sum will be equal to $$$k$$$, what contradicts with problem condition. It means that we can take not more than $$$\left \lfloor \frac{k}{2} \right \rfloor$$$ numbers from $$$1$$$ to $$$k-1$$$.
Then the total size of the set will not exceed $$$(n - k) + \left \lfloor \frac{k}{2} \right \rfloor$$$. As known, $$$k$$$ = $$$\left \lfloor \frac{k}{2} \right \rfloor + \left \lceil \frac{k}{2} \right \rceil$$$ (you can prove that fact by considering two cases: when $$$k$$$ is even, and when $$$k$$$ is odd). Let's replace $$$k$$$ in recieved estimation: $$$n - (\left \lfloor \frac{k}{2} \right \rfloor + \left \lceil \frac{k}{2} \right \rceil) + \left \lfloor \frac{k}{2} \right \rfloor=n - \left \lceil \frac{k}{2} \right \rceil$$$, which is the size of mentioned set, therefore mentioned set is the answer to the problem.