Statistics

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

Taro shows a magic trick to Hanako.

Taro: Hello Hanako. I'll show you a magic trick. Please imagine a positive integer less than or equal to 16.
Hanako: OK. I imagined it.
Taro: (Taro shows card 1 to Hanako.) Does this card contain your number?
Hanako: Yes.
Taro: (Taro shows card 2 to Hanako.) Does this card contain your number?
Hanako: No.
Taro: (Taro shows card 3 to Hanako.) Does this card contain your number?
Hanako: Yes.
Taro: (Taro shows card 4 to Hanako.) Does this card contain your number?
Hanako: Yes.
Taro: Your number is 5!


(Card 1 contains 1, 2, 3, 4, 5, 6, 7 and 8. Card 2 contains 1, 2, 3, 4, 9, 10, 11 and 12. Card 3 contains 1, 2, 5, 6, 9, 10, 13 and 14. Card 4 contains 1, 3, 5, 7, 9, 11, 13 and 15.)

Let's generalize this magic trick. Hanako imagines a positive integer less than or equal to N. Each card must contain exactly M different integers between 1 and N, inclusive. Taro must be able to determine Hanako's number correctly using her answers to his questions. Return the minimal number of cards required to perform this magic trick successfully every time.

Definition

Class:

NumberMagic

Method:

theMin

Parameters:

int, int

Returns:

int

Method signature:

int theMin(int N, int M)

(be sure your method is public)

Constraints

• N will be between 2 and 1,000,000,000, inclusive.
• M will be between 1 and N-1, inclusive.

Examples

1. 16

   8

   Returns: 4

   The example from the statement.

2. 2

   1

   Returns: 1

   Write 1 on the only card. If Hanako answers "yes", her number is 1. If she answers "no", her number is 2.

3. 3

   1

   Returns: 2

4. 1000000000

   58585858

   Returns: 101

5. 1000000000

   999999999

   Returns: 999999999

6. 1000000000

   487220633

   Returns: 30

7. 1000000000

   487220632

   Returns: 31

8. 1000000000

   423630625

   Returns: 31

9. 1000000000

   423630624

   Returns: 32

10. 1000000000

    615014966

    Returns: 32

11. 1000000000

    615014967

    Returns: 33

12. 1000000000

    644817456

    Returns: 33

13. 1000000000

    644817457

    Returns: 34

14. 1000000000

    671049375

    Returns: 34

15. 1000000000

    671049376

    Returns: 35

16. 1000000000

    601746

    Returns: 4965

17. 1000000000

    601745

    Returns: 4966

18. 1000000000

    481

    Returns: 4149378

19. 1000000000

    480

    Returns: 4158005

20. 1000000000

    999999996

    Returns: 400000000

21. 1000000000

    999999997

    Returns: 500000000

22. 1000000000

    992909691

    Returns: 560

23. 1000000000

    992909692

    Returns: 561

24. 1000000000

    1945532

    Returns: 1662

25. 1000000000

    1945531

    Returns: 1663

26. 1066

    1064

    Returns: 710

27. 1066

    1065

    Returns: 1065

28. 143466

    143435

    Returns: 8967

29. 143466

    143436

    Returns: 9256

30. 7

    5

    Returns: 4

31. 7

    6

    Returns: 6

32. 19905

    19520

    Returns: 132

33. 19905

    19521

    Returns: 133

34. 727

    476

    Returns: 11

35. 727

    477

    Returns: 12

36. 4

    2

    Returns: 2

37. 4

    1

    Returns: 3

38. 180311215

    160318171

    Returns: 60

39. 180311215

    160318172

    Returns: 61

40. 80

    25

    Returns: 8

41. 80

    24

    Returns: 9

42. 5455733

    1401

    Returns: 7783

43. 5455733

    1400

    Returns: 7789

44. 42

    40

    Returns: 28

45. 42

    41

    Returns: 41

46. 638580305

    51105

    Returns: 29165

47. 3000144

    2992242

    Returns: 1067

48. 40835

    36

    Returns: 2208

49. 894

    870

    Returns: 72

50. 841

    5

    Returns: 280

51. 5

    1

    Returns: 4

52. 361

    81

    Returns: 13

53. 767

    60

    Returns: 31

54. 825978418

    1469487

    Returns: 1696

55. 11

    4

    Returns: 4

56. 12

    4

    Returns: 5

57. 62656938

    4043405

    Returns: 85

58. 352907699

    9212942

    Returns: 187

59. 426136055

    359671822

    Returns: 50

60. 907701110

    214402198

    Returns: 40

61. 294150986

    12833641

    Returns: 121

62. 520656681

    376119647

    Returns: 36

63. 1654371

    976655

    Returns: 22

64. 614206798

    519432612

    Returns: 51

65. 504872092

    493470762

    Returns: 214

66. 557297208

    171833982

    Returns: 35

67. 1000000000

    1

    Returns: 999999999

68. 1000000000

    2

    Returns: 666666666

69. 1000000000

    2323

    Returns: 860586

70. 98779877

    9877

    Returns: 20000

71. 1000000000

    18276

    Returns: 109428

72. 999999997

    493608

    Returns: 6041

73. 1000000000

    113

    Returns: 17543860

74. 999999997

    997

    Returns: 2004009

75. 928198322

    4242

    Returns: 437520

76. 586243791

    845716

    Returns: 2078

77. 1000000000

    123

    Returns: 16129033

78. 987717893

    2753

    Returns: 717297

79. 17

    8

    Returns: 5

80. 5

    2

    Returns: 3

81. 1000000000

    10

    Returns: 181818182

82. 1000000000

    2000

    Returns: 999501

83. 10000

    4

    Returns: 4000

84. 5475474

    547457

    Returns: 54

85. 1000000000

    433434

    Returns: 6868

86. 57325484

    2527574

    Returns: 111

87. 47018974

    44342348

    Returns: 89

88. 324584819

    134128489

    Returns: 30

89. 300000000

    234224223

    Returns: 40