Statistics

Problem Statement for "TheCardShufflingDivTwo"

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

  1. 5

    1

    Returns: 2

    After the shuffling the card order (from top to bottom) will be 2, 4, 1, 3, 5.

  2. 5

    2

    Returns: 4

    And here the card order will be 4, 3, 2, 1, 5.

  3. 2

    10

    Returns: 1

  4. 17

    9

    Returns: 2

  5. 1

    3

    Returns: 1

  6. 5

    7

    Returns: 3

  7. 5

    7

    Returns: 3

  8. 48

    1

    Returns: 2

  9. 57

    25

    Returns: 14

  10. 69

    26

    Returns: 16

  11. 88

    52

    Returns: 78

  12. 91

    73

    Returns: 2

  13. 65

    7

    Returns: 63

  14. 45

    37

    Returns: 2

  15. 11

    23

    Returns: 8

  16. 99

    29

    Returns: 50

  17. 34

    91

    Returns: 23

  18. 34

    27

    Returns: 8

  19. 73

    52

    Returns: 55

  20. 5

    69

    Returns: 2

  21. 148

    1

    Returns: 2

  22. 357

    125

    Returns: 32

  23. 369

    226

    Returns: 187

  24. 388

    852

    Returns: 193

  25. 291

    573

    Returns: 182

  26. 165

    7

    Returns: 128

  27. 545

    437

    Returns: 32

  28. 611

    523

    Returns: 271

  29. 799

    529

    Returns: 189

  30. 434

    291

    Returns: 308

  31. 757148

    851001

    Returns: 300266

  32. 413357

    971125

    Returns: 19168

  33. 598369

    567226

    Returns: 594726

  34. 749388

    890852

    Returns: 318320

  35. 766291

    239573

    Returns: 432807

  36. 38165

    597007

    Returns: 22228

  37. 615545

    51437

    Returns: 115672

  38. 289611

    341523

    Returns: 101186

  39. 427799

    215529

    Returns: 90056

  40. 16434

    544291

    Returns: 1838

  41. 957148

    951001

    Returns: 167358

  42. 913357

    971125

    Returns: 279980

  43. 998369

    967226

    Returns: 927632

  44. 949388

    990852

    Returns: 118714

  45. 1000000

    1000000

    Returns: 605496

  46. 999999

    999999

    Returns: 399680

  47. 555555

    777777

    Returns: 347222

  48. 100000

    100000

    Returns: 1024

  49. 6

    3

    Returns: 1

  50. 1

    1

    Returns: 1

  51. 999997

    999997

    Returns: 295776

  52. 1000000

    999999

    Returns: 302748

  53. 10

    5

    Returns: 10

  54. 999999

    880977

    Returns: 188063

  55. 1000000

    100000

    Returns: 230887

  56. 997763

    997763

    Returns: 402227

  57. 1235

    124312

    Returns: 16

  58. 999201

    1000000

    Returns: 243322

  59. 23423

    34534

    Returns: 7115

  60. 123456

    12345

    Returns: 71582

  61. 987654

    987654

    Returns: 821029

  62. 999998

    999998

    Returns: 199840

  63. 999

    998001

    Returns: 512

  64. 30

    10

    Returns: 1

  65. 50000

    12345

    Returns: 25166

  66. 100000

    10000

    Returns: 45453

  67. 987891

    987653

    Returns: 681077

  68. 100000

    1000000

    Returns: 29503

  69. 999979

    1000000

    Returns: 194388

  70. 16

    5

    Returns: 15

  71. 243254

    234454

    Returns: 9859

  72. 2

    1

    Returns: 2

  73. 999999

    453123

    Returns: 36044

  74. 1

    2

    Returns: 1

  75. 999999

    888888

    Returns: 185914

  76. 1000000

    1000

    Returns: 230887

  77. 8

    2

    Returns: 4

  78. 98452

    1212

    Returns: 18090

  79. 12345

    1234

    Returns: 11524

  80. 100

    1000000

    Returns: 1

  81. 954125

    125487

    Returns: 785528

  82. 987654

    654321

    Returns: 801392

  83. 1000000

    999198

    Returns: 551031

  84. 10

    4

    Returns: 5

  85. 4

    2

    Returns: 4

  86. 50

    50

    Returns: 4

  87. 999999

    1000000

    Returns: 799360

  88. 8

    4

    Returns: 7

  89. 4

    3

    Returns: 3

  90. 1

    979797

    Returns: 1

  91. 999999

    999998

    Returns: 199840

  92. 999997

    1000000

    Returns: 366214

  93. 1

    92

    Returns: 1

  94. 3

    2

    Returns: 1

  95. 1234

    1234

    Returns: 1024

  96. 42

    68

    Returns: 11

  97. 987933

    999977

    Returns: 269558

  98. 1

    10

    Returns: 1

  99. 7

    3

    Returns: 1

  100. 12

    8

    Returns: 9

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: