Connection Status:
Competition Arena > TheCardShufflingDivOne

TheCardShufflingDivOne

SRM 448 · 2009-09-10 · by Vasyl[alphacom]

SRM 448 · 2009-09-10 · by Vasyl[alphacom] · Search
Class Name: TheCardShufflingDivOne
Return Type: int
Method Name: shuffle
Arg Types: (int, int, int)
Problem Statement

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 three additional decks on the table, called the left, right and resulting decks. These three decks are initially empty. To shuffle the deck, John will repeat the following sequence of actions until the main deck contains less than two cards:

  • 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 top of the main deck to the top of the left deck, and so on, until the main deck is empty.
  • Repeat the following left times: Move one card from the top of the left deck to the bottom of the left deck.
  • Repeat the following right times: Move one card from the top of the right deck to the bottom of the right deck.
  • Move one card from the top of the left deck to the top of the resulting deck.
  • Move one card from the top of the right deck to the top of the resulting deck.
  • 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.
If there is one card left in the main deck, John will move it to the top of the resulting deck. Return the number of the card at the top of the resulting deck after the shuffling is complete.

Constraints

  • n will be between 1 and 1,000,000, inclusive.
  • left and right will each be between 0 and 1,000,000, inclusive.
Examples
0)
3
0
0
Returns: 1

The resulting deck will contain cards in the same order as the main deck at the beginning.

1)
3
1
1
Returns: 3

Here the order of cards in the resulting deck (from top to bottom) will be 3, 2, 1.

2)
5
0
0
Returns: 2
3)
17
12
21
Returns: 17
4)
5
6
0
Returns: 2

Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TheCardShufflingDivOne with a public method int shuffle(int n, int left, int right) · 65 test cases · 2 s / 256 MB per case

Submitting as anonymous