Recollect Numbers

Research cross-check: I checked the official Codeforces problem page (https://codeforces.com/contest/2201/problem/B) and the Round 1082 tutorial discussion (https://codeforces.com/blog/entry/151515). The construction below is proved from the supplied statement; the links are just evidence, not copied text.

Call a turn successful if the two flipped cards are equal, and failed otherwise. A successful turn discards exactly one number-pair, and there are $n$ pairs total, so every winning run has exactly $n$ successful turns. Therefore

$\text{turns}=n+\text{failed turns}.$

So the whole problem is: which values of $f=k-n$ can be forced as the number of failed turns?

First, $f\ge 0$, so $k\ge n$. That lower bound is real: $1,1,2,2,\ldots,n,n$ finishes in exactly $n$ turns.

Now for the upper bound. Look at any failed turn. The algorithm is in the second main branch, so there is no already-known pair. It flips the first never-flipped card; say its value is $x$. If another non-discarded card with value $x$ had been flipped before, the greedy rule would immediately choose it as the second card and the turn would be successful. If value $x$ had already been discarded, both copies of $x$ would be gone, impossible. Therefore, in a failed turn, the first flipped value is a value never seen before.

Charge each failed turn to this new first value. These charged values are all distinct. If there is at least one failed turn, then in the first failed turn the second card has a different value, and before the first failed turn no failed turn has revealed anything. Previous successful turns can only have discarded complete pairs, so this second value is also new. It is not charged to that first failed turn, and it can never be charged later because it has now been seen. Thus, if $f>0$, at least one of the $n$ values is uncharged, so $f\le n-1$. For $f=0$ this is trivial. Hence

$0\le f\le n-1 \quad\Longleftrightarrow\quad n\le k\le 2n-1.$

No, you cannot make the greedy waste arbitrarily many turns. Once it knows a mate, it beelines to it. Annoyingly competent algorithm.

It remains to construct every value in that interval. Let

$f=k-n,\qquad m=f+1.$

Since $0\le f\le n-1$, we have $1\le m\le n$. Build the sequence like this:

1. For every $i=2,3,\ldots,m$, append $i, i-1$.
2. Append $1,m$.
3. For every $i=m+1,m+2,\ldots,n$, append $i,i$.

For example, the prefix for $m=5$ is

$2,1,3,2,4,3,5,4,1,5.$

Let's count what the greedy does on this prefix. If $m=1$, the prefix is just $1,1$, taking one successful turn. Otherwise, the first turn flips $2$ and $1$, so it fails. Then for each $x=2,3,\ldots,m-1$, the next unseen two cards are $x+1,x$. The value $x+1$ is new, while $x$ has already been seen, so the turn fails and creates a known pair of $x$; the next turn must discard that pair. Finally, the last two unseen cards in the prefix are $1,m$, and each matches a previously seen mate, so they are discarded successfully.

The prefix therefore has exactly $m-1$ failed turns and $m$ successful turns, for $2m-1$ turns total. The remaining numbers $m+1$ through $n$ are adjacent equal pairs, each taking one successful turn. Total turns:

$(2m-1)+(n-m)=n+m-1=n+f=k.$

The sequence clearly contains each number from $1$ to $n$ exactly twice, so it is valid.

Edge cases are already covered: $m=1$ gives all adjacent pairs and $k=n$; $m=n$ gives the maximum $k=2n-1$ and no suffix. The implementation just prints the construction.

Complexity is $O(n)$ time and $O(n)$ memory per test case, dominated by output.