Statistics

Problem Statement for "TheCardShufflingDivOne"

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.

Definition

Class:
TheCardShufflingDivOne
Method:
shuffle
Parameters:
int, int, int
Returns:
int
Method signature:
int shuffle(int n, int left, int right)
(be sure your method is public)

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

  1. 3

    0

    0

    Returns: 1

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

  2. 3

    1

    1

    Returns: 3

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

  3. 5

    0

    0

    Returns: 2

  4. 17

    12

    21

    Returns: 17

  5. 5

    6

    0

    Returns: 2

  6. 3

    8

    8

    Returns: 1

  7. 4

    0

    3

    Returns: 1

  8. 48

    9

    66

    Returns: 47

  9. 25

    92

    51

    Returns: 17

  10. 88

    27

    69

    Returns: 66

  11. 73

    18

    96

    Returns: 49

  12. 45

    4

    55

    Returns: 5

  13. 23

    95

    58

    Returns: 11

  14. 34

    35

    30

    Returns: 13

  15. 27

    65

    89

    Returns: 16

  16. 5

    79

    75

    Returns: 1

  17. 84

    49

    7

    Returns: 24

  18. 61

    88

    82

    Returns: 59

  19. 81

    59

    99

    Returns: 57

  20. 11

    43

    99

    Returns: 1

  21. 148

    317

    244

    Returns: 113

  22. 125

    429

    819

    Returns: 16

  23. 388

    966

    560

    Returns: 99

  24. 573

    599

    410

    Returns: 217

  25. 545

    711

    713

    Returns: 318

  26. 523

    541

    350

    Returns: 440

  27. 434

    915

    369

    Returns: 76

  28. 227

    528

    616

    Returns: 178

  29. 605

    753

    294

    Returns: 564

  30. 784

    858

    166

    Returns: 590

  31. 757148

    850833

    413055

    Returns: 200126

  32. 971125

    597709

    567065

    Returns: 319142

  33. 749388

    890847

    766255

    Returns: 512006

  34. 239573

    37691

    597006

    Returns: 229403

  35. 615545

    51110

    289218

    Returns: 573794

  36. 341523

    427628

    215491

    Returns: 253050

  37. 16434

    544122

    446450

    Returns: 15465

  38. 90227

    426790

    752135

    Returns: 45406

  39. 41605

    220562

    908065

    Returns: 32411

  40. 655784

    970659

    417541

    Returns: 6039

  41. 1000000

    949322

    910342

    Returns: 257220

  42. 1000000

    991773

    965620

    Returns: 33667

  43. 1000000

    990803

    965933

    Returns: 641167

  44. 999999

    951001

    913357

    Returns: 47064

  45. 999999

    998369

    967226

    Returns: 791604

  46. 999999

    990852

    966291

    Returns: 17052

  47. 1000000

    1000000

    1000000

    Returns: 368436

  48. 345

    6

    54

    Returns: 47

  49. 999999

    287

    2987

    Returns: 939833

  50. 999100

    0

    517222

    Returns: 263033

  51. 1000000

    4367

    544768

    Returns: 66015

  52. 100000

    0

    100000

    Returns: 9066

  53. 1000000

    21

    32

    Returns: 666038

  54. 1000000

    1001

    9999

    Returns: 637626

  55. 999771

    123457

    75431

    Returns: 594309

  56. 959564

    956314

    955622

    Returns: 118319

  57. 1000000

    0

    0

    Returns: 9026

  58. 2

    0

    0

    Returns: 2

  59. 100

    12

    23

    Returns: 6

  60. 1000000

    77777

    97896

    Returns: 361394

  61. 1000000

    999998

    999991

    Returns: 341388

  62. 1000000

    2

    3

    Returns: 447596

  63. 989992

    9881

    984082

    Returns: 311065

  64. 3

    197

    956

    Returns: 3

  65. 4

    0

    0

    Returns: 1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: