10143. 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.

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

Output. 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.

Sample input	Sample output
7 10 6 0	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

SOLUTION

deque

Algorithm analysis

For the given number n, initialize the deck of cards – fill the double - sided queue with the numbers 1, 2,…, n. Then, while the queue contains more than one element, make n – 1 iterations: print and remove the top card, and then put the top card down the deck.

Example

Let's simulate the operations with a deck of cards for n = 7.

Card number 6 is the remaining card.

Algorithm realization

Declare the working deque.

deque<int> d;

Read the input value of n.

while (scanf("%d", &n), n)

{

Clear the deque.

d.clear();

Initialize the deque (the deck of cards): push into it sequentially the numbers from 1 to n.

for (i = 1; i <= n; i++) d.push_back(i);

printf("Discarded cards:");

for (i = 1; i < n; i++)

{

Print the top card and delete it.

printf(" %d", d[0]); d.pop_front();

Put the top card down the deck.

d.push_back(d[0]); d.pop_front();

Print the comma between the printed cards.

if (i < n - 1) printf(",");

}

Print the number of the remaining card.

printf("\nRemaining card: %d\n", d[0]);

}

Java realization

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

LinkedList<Integer> q = new LinkedList<Integer>();

while(true)

{

int n = con.nextInt();

if (n == 0) break;

q.clear();

for (int i = 1; i <= n; i++)

q.addLast(i);

System.out.print("Discarded cards:");

for(int i = 1; i < n; i++)

{

System.out.print(" " + q.getFirst());

q.removeFirst();

q.addLast(q.getFirst());

q.removeFirst();

if (i < n-1) System.out.print(",");

}

System.out.println("\nRemaining card: " + q.getFirst());

}

con.close();

}

}

Python realization

from collections import deque

while True:

n = int(input())

if n == 0: break

d = deque()

for i in range(n):

d.append(i + 1)

print("Discarded cards:",end = " ")

for i in range(n - 1):

print(d.popleft(),end = "")

d.append(d.popleft())

if i < n - 2: print(",",end = " ")

print("\nRemaining card:", d[0])