favorite We need a little bit of your help to keep things running, click on this banner to learn more

Data Structures contest

Throwing cards away

Given is an ordered deck of n cards numbered from 1 to n with card 1 at the top and card n at the bottom. The following operation is performed as long as there are at least two cards in the deck: throw away the top card and move the card that is now on the top of the deck to the bottom of the deck. Your task is to find the sequence of discarded cards and the last, remaining card.


Each line contains number of cards n (n1000) in the deck. The last line contains n = 0 and should not be processed.


For each input number produce two lines. The first line presents the sequence of discarded cards, the second line reports the last remaining card. See the sample for the expected format.

Time limit 1 second
Memory limit 128 MiB
Input example #1
Output example #1
Discarded cards: 1, 3, 5, 7, 4, 2
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 2, 6, 10, 8
Remaining card: 4
Discarded cards: 1, 3, 5, 2, 6
Remaining card: 4