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
Master Wad7a:
2013-06-16 14:09:36
My O(n*(n+1)/2) passes in 1.5 seconds with averagely slow input, BTW u can solve it using binary indexed trees |
|
karan173:
2013-03-28 16:39:14
O(n^2) is giving tle, has the test data been updated? |
|
maskit:
2012-04-10 19:00:56
m getting wa..is there any..special case........ |
|
Mitch Schwartz:
2012-01-06 12:37:58
It's possible for O(n^2) to pass in well under 1s. :P |
|
aang*™*:
2011-09-16 05:17:21
this assumes up to 20000 of Spades. and not just 13. |
|
darryl:
2011-05-04 05:25:46
Solve it as if the time limit is 1s Last edit: 2011-07-27 03:29:31 |
|
Sai Kiran Reddy Jakka:
2010-07-27 15:18:28
@shaka:thanks for the information:) |
|
Shaka Shadows:
2010-07-20 14:17:17
Time limit too easy to pass!!! Even a O(n^2) solution will get AC :) |
|
Raul Angel Ballester:
2010-05-09 03:50:49
time limit should be 1s not 11s ;)
|
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 |