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
tsioftas:
2017-04-22 08:54:35
The constraints of n are wrong, it gets bigger than 20000. It costed me a wa (not a sigsev somehow xD) |
|
avisheksanvas:
2017-02-02 12:22:19
BIT to the rescue _/\_ |
|
Rakend Chauhan:
2017-01-04 18:20:21
easy one with vector |
|
king:
2016-12-18 13:01:47
Bit + binary search = AC ;)
|
|
code_inception:
2016-12-12 20:45:06
a tough one with BIT Last edit: 2016-12-12 20:46:52 |
|
Sajal Sarkar:
2016-12-01 10:29:41
got AC using BIT, now trying Segment Tree and getting TLE. Complexity of my solution using segment tree is O(n*logn) and with BIT it is O(n*logn*logn) with different constant factors, so segment tree should be performing better in time, am I missing something? Kindly help me on this. |
|
Rahul Jain:
2016-11-25 09:47:45
For those who couldn't understand the problem, see this : https://www.youtube.com/watch?v=kP7FJGzorpI
|
|
Rahul Jain:
2016-11-24 20:39:40
Since SPOJ removed their Pyramid Clyster, even O(n^2) solutions are passing. They should modify the time limit on Cube Cluster for every problem that was for Pyramid. |
|
malibarbar:
2016-11-01 19:18:40
ono of best tasks to learn Fenwick Tre;
|
|
Nallagatla Manikanta:
2016-08-05 10:18:30
not able to understand whats happening |
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 |