TopCoder problem "TheCardShufflingDivTwo" used in SRM 448 (Division II Level Two)



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.
Return the number of the card at the top of the main deck after the shuffling is complete.

 

Definition

    
Class:TheCardShufflingDivTwo
Method:shuffle
Parameters:int, int
Returns:int
Method signature:int shuffle(int n, int m)
(be sure your method is public)
    
 

Constraints

-n and m will each be between 1 and 1,000,000, inclusive.
 

Examples

0)
    
5
1
Returns: 2
After the shuffling the card order (from top to bottom) will be 2, 4, 1, 3, 5.
1)
    
5
2
Returns: 4
And here the card order will be 4, 3, 2, 1, 5.
2)
    
2
10
Returns: 1
3)
    
17
9
Returns: 2

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10618

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13902&pm=10618

Writer:

Vasyl[alphacom]

Testers:

PabloGilberto , ivan_metelsky , Chmel_Tolstiy

Problem categories:

Simple Search, Iteration