Card Stacking
Time limit1sMemory limit128 MB
Simulate a deck where each dealt card is followed by moving P cards to the bottom, and report the original positions that reach Bessie.
- Level
Medium4 of 10
- Topics
- Simulation, Queue, Implementation, Math
- Solved
- No attempts yet
Problem
Bessie is playing a card game together with her cow friends, so there are players in total (). They use a deck of cards (, and is a multiple of ). Exactly of the cards are "good" and the remaining are "bad".
Bessie is the dealer and naturally wants to keep every "good" card for herself. Her friends suspect she will cheat, so they force her to deal by the following rules:
- Deal the card on the top of the deck to the cow on Bessie's right.
- Every time she deals one card, she must move the next cards () from the top of the deck to the bottom.
- Continue dealing to each player in turn, going counterclockwise.
Because Bessie starts by dealing to the cow on her right and she herself sits last in the counterclockwise order, she receives every -th card that is dealt.
The cards are numbered from the top of the original deck. Determine the positions in the original deck where the "good" cards must be placed so that Bessie ends up with all of them.
Input
The first line contains three space-separated integers , , and .
Output
Print the positions (counted from the top of the original deck) where the good cards must be placed, in ascending order, one per line. With those placements, Bessie receives every good card when the deck is dealt out.
Hint
Consider the case , , . Each time Bessie deals one card she moves the top two cards to the bottom of the deck.
Placing the good cards at positions , , and of the original deck works. The deck is dealt as follows (every number is a card's position in the original deck):
Bessie ends up holding the good cards that were placed at positions , , and .