CTRICK - Card Trick
The magician shuffles a small pack of cards, holds it face down and performs the following procedure:
- The top card is moved to the bottom of the pack. The new top card is dealt face up onto the table. It is the Ace of Spades.
- Two cards are moved one at a time from the top to the bottom. The next card is dealt face up onto the table. It is the Two of Spades.
- Three cards are moved one at a time…
- This goes on until the nth and last card turns out to be the n of Spades.
This impressive trick works if the magician knows how to arrange the cards beforehand (and knows how to give a false shuffle). Your program has to determine the initial order of the cards for a given number of cards, 1 ≤ n ≤ 20000.
Input
On the first line of the input is a single positive integer, telling the number of test cases to follow. Each case consists of one line containing the integer n.
Output
For each test case, output a line with the correct permutation of the values 1 to n, space separated. The first number showing the top card of the pack, etc…
Example
Input: 2 4 5 Output: 2 1 4 3 3 1 4 5 2
hide comments
|
omar_hafez:
2022-05-16 00:08:05
HINT:
|
|
pravesh_pandey:
2022-04-13 08:18:59
Will someone correct me if I'm wrong, I think the time complexity will be N*log(N)*log(N) if I have done with the BIT method. |
|
madhav10:
2021-05-12 17:42:51
@r15habhgup11
|
|
princemishra:
2021-04-08 09:57:59
input:
|
|
karelisp:
2021-03-30 01:12:42
Take care of testcase where N=1 |
|
sharjeel_spoj:
2021-01-25 22:20:21
Segment tree can be used to find the Kth largest element. |
|
sangmai:
2021-01-18 14:09:16
bruteforce passes. |
|
anirudh_1999:
2020-05-06 21:15:02
Can anyone explain the sample test cases given in the problem..I couldn't understand any of it. |
|
jwalinarora:
2020-04-18 17:19:46
There can be multiple answers, right? |
|
atharvat77:
2019-11-19 20:11:18
BIT On Point Nice Problem |
Added by: | Camilo Andrés Varela León |
Date: | 2006-11-23 |
Time limit: | 3.279s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Nordic Collegiate Contest 2006 |