TheCardShufflingDivTwo
SRM 448 · 2009-09-10 · by Vasyl[alphacom]
Problem Statement
John and Brus are training for a card game tournament. John is practicing his shuffling technique. John is using a deck of n cards, numbered 1 to n from top to bottom. This initial deck is called the main deck. There are two additional decks on the table, called the left and right decks. These two decks are initially empty. To shuffle the deck, John will repeat the following sequence of actions m times:
- Move one card from the top of the main deck to the top of the left deck, then one card from the top of the main deck to the top of the right deck, then one card from the top of the main deck to the top of the left deck, and so on, until the main deck is empty.
- While the left deck is not empty, move one card from the top of the left deck to the top of the main deck.
- While the right deck is not empty, move one card from the top of the right deck to the top of the main deck.
Constraints
- n and m will each be between 1 and 1,000,000, inclusive.
5 1 Returns: 2
After the shuffling the card order (from top to bottom) will be 2, 4, 1, 3, 5.
5 2 Returns: 4
And here the card order will be 4, 3, 2, 1, 5.
2 10 Returns: 1
17 9 Returns: 2
1 3 Returns: 1
Submissions are judged against all 100 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TheCardShufflingDivTwo with a public method int shuffle(int n, int m) · 100 test cases · 2 s / 256 MB per case