Statistics

Problem Statement for "NumbersAndMatches"

Problem Statement

You have a piece of paper with exactly D positions laid out in a horizontal row. Each position looks like the following: 
 _
|_|
|_|
There are 7 line segments in each position, and each line segment can hold exactly one match. Matches cannot be placed anywhere except on the line segments.
You are given an integer N containing exactly D digits (with no leading zeroes). Spell out the number using matches on the paper. Each digit must occupy a single position. The following diagram shows how each digit should be formed: 
      _	               _        _                 _       _        _        _        _
 0 - | |  1 -  |  2 -  _|  3 -  _|  4 - |_|  5 - |_  6 - |_   7 -   |  8 - |_|  9 - |_|
     |_|      _|      |_        _|        |       _|     |_|        |      |_|       _|
After you lay out the initial arrangement, you are allowed to move up to K matches. You cannot discard matches or add new matches. After you make all your moves, the final arrangement must be valid (as described above) and the integer formed by the arrangement must contain the same number of digits as the original integer. Leading zeroes are allowed. Return the number of distinct integers that can be formed in this manner. Note that the original integer counts toward the total because it always obtainable by making 0 moves.

Definition

Class:
NumbersAndMatches
Method:
differentNumbers
Parameters:
long, int
Returns:
long
Method signature:
long differentNumbers(long N, int K)
(be sure your method is public)

Constraints

  • N will be between 1 and 10^18 - 1, inclusive.
  • K will be between 1 and 126, inclusive.

Examples

  1. 10

    1

    Returns: 4

    Here you can compose numbers 10, 19, 16 and 70: _ _ | | | -----> | | | _| |_| _| |_| _ _ | | | -----> | |_| _| |_| _| _| _ _ | | | -----> | |_ _| |_| _| |_| _ _ _ | | | -----> | | | _| |_| | |_|

  2. 23

    1

    Returns: 4

    This time it's possible to compose 22, 23, 25 and 33.

  3. 66

    2

    Returns: 15

    Here you can move up to 2 matches, so quite a lot of numbers can be composed. Note that you are allowed to move a match from one digit to another one, so, for example, it's possible to compose 38. However, you can't discard a match or add a new match, so, for example, you can't compose 55 or 88.

  4. 888888888

    100

    Returns: 1

    You are allowed to move a lot of matches, but still it's only possible to compose 888888888.

  5. 444444444444444444

    2

    Returns: 1

    Given that at most 2 matches can be moved, only the initial number can be composed.

  6. 444444444444444444

    3

    Returns: 1225

  7. 1

    10

    Returns: 2

  8. 4

    10

    Returns: 1

  9. 6

    10

    Returns: 3

  10. 9

    10

    Returns: 3

  11. 8

    10

    Returns: 1

  12. 584780

    7

    Returns: 64583

  13. 1457

    2

    Returns: 12

  14. 179789

    2

    Returns: 168

  15. 2933596

    7

    Returns: 505644

  16. 447460

    6

    Returns: 9420

  17. 78689

    4

    Returns: 2555

  18. 7244

    8

    Returns: 465

  19. 66212

    1

    Returns: 10

  20. 25311

    8

    Returns: 4728

  21. 538

    1

    Returns: 13

  22. 71032

    9

    Returns: 7783

  23. 96

    2

    Returns: 15

  24. 396

    4

    Returns: 132

  25. 59481

    1

    Returns: 18

  26. 3318876

    12

    Returns: 1138862

  27. 94492

    5

    Returns: 3620

  28. 39857

    5

    Returns: 6524

  29. 5649257

    10

    Returns: 831739

  30. 5806545

    9

    Returns: 765790

  31. 299351

    1

    Returns: 26

  32. 5671702

    10

    Returns: 351549

  33. 5041963

    14

    Returns: 1167792

  34. 2770

    7

    Returns: 734

  35. 4378253

    5

    Returns: 32015

  36. 3352

    3

    Returns: 237

  37. 569

    3

    Returns: 112

  38. 912

    5

    Returns: 147

  39. 79418

    10

    Returns: 10521

  40. 239

    2

    Returns: 35

  41. 4243

    9

    Returns: 1098

  42. 5891911393

    9

    Returns: 141044049

  43. 810

    1

    Returns: 7

  44. 58866962718526

    18

    Returns: 2796495743545

  45. 77457252

    5

    Returns: 6409

  46. 369048204097567

    16

    Returns: 15329445832838

  47. 72222962555318370

    9

    Returns: 21840703301

  48. 9948674

    5

    Returns: 44617

  49. 968204

    8

    Returns: 60198

  50. 89337183138636

    8

    Returns: 4757717426

  51. 815178010

    5

    Returns: 133717

  52. 29791019054717928

    3

    Returns: 71771

  53. 84424056394501305

    16

    Returns: 228739684270103

  54. 95480254595884168

    9

    Returns: 175540553740

  55. 5

    36

    Returns: 3

  56. 73386163865874

    1

    Returns: 110

  57. 49045826563

    11

    Returns: 1688392108

  58. 618

    1

    Returns: 7

  59. 21208323598517225

    5

    Returns: 12447266

  60. 6795227713992567

    34

    Returns: 474380414263848

  61. 8

    60

    Returns: 1

  62. 571625929

    1

    Returns: 43

  63. 40384360072744351

    27

    Returns: 5480331841122702

  64. 437

    2

    Returns: 12

  65. 70

    1

    Returns: 4

  66. 73593195

    9

    Returns: 4903784

  67. 95218853389

    7

    Returns: 88236832

  68. 87

    4

    Returns: 19

  69. 9606773610310312

    11

    Returns: 240195937548

  70. 46953996133488729

    1

    Returns: 189

  71. 2597152058426292

    1

    Returns: 94

  72. 44888823

    3

    Returns: 3397

  73. 3944694855090580

    12

    Returns: 4972523101620

  74. 3679831

    9

    Returns: 913451

  75. 23528

    1

    Returns: 15

  76. 555144151

    14

    Returns: 10529252

  77. 52

    2

    Returns: 6

  78. 144776303177556463

    36

    Returns: 9462320934663752

  79. 566

    1

    Returns: 12

  80. 625024

    3

    Returns: 461

  81. 753

    1

    Returns: 5

  82. 84647859393083902

    4

    Returns: 5752005

  83. 18802230967797

    4

    Returns: 511339

  84. 83573501233396242

    6

    Returns: 188980848

  85. 3061307575233837

    6

    Returns: 96062950

  86. 9391332969073671

    27

    Returns: 761305760293876

  87. 8590430783287900

    10

    Returns: 289574049548

  88. 7327210417031947

    17

    Returns: 4029386929968

  89. 811406970855869192

    17

    Returns: 3664510893077393

  90. 337972959334662208

    23

    Returns: 53459276914630388

  91. 328352453435175

    13

    Returns: 726369733414

  92. 2795465984945472

    15

    Returns: 15734819733474

  93. 966264404849669735

    11

    Returns: 4463132890261

  94. 17032331246316251

    6

    Returns: 26349378

  95. 535167791648838

    8

    Returns: 4799186304

  96. 751452600138841876

    4

    Returns: 1600248

  97. 90020061282502153

    8

    Returns: 6675645800

  98. 712916399035092062

    13

    Returns: 66913890482787

  99. 877552597773714842

    34

    Returns: 9462224772921064

  100. 8745998130609693

    20

    Returns: 302264148195226

  101. 4607457303101098

    24

    Returns: 685330255502119

  102. 55269389046032838

    16

    Returns: 354019876642158

  103. 7269326896563393

    17

    Returns: 187543404025831

  104. 571152816476731599

    37

    Returns: 18415520351694236

  105. 669291984052404

    12

    Returns: 528272692048

  106. 1303625962603750

    9

    Returns: 34965179849

  107. 341518108736536963

    2

    Returns: 8582

  108. 9076500865561527

    12

    Returns: 1964443222396

  109. 1016578928468547

    20

    Returns: 368592135484824

  110. 45867338383585985

    20

    Returns: 1690850760269308

  111. 7945346246416888

    7

    Returns: 792834613

  112. 20870941125871905

    23

    Returns: 4948770722157148

  113. 6136393239367948

    18

    Returns: 370196604937287

  114. 70454790698050302

    125

    Returns: 5834803841784360

  115. 168227367326959853

    125

    Returns: 64527700155023418

  116. 13278173218807769

    125

    Returns: 4735794663165804

  117. 17887262576459834

    126

    Returns: 7400894886230503

  118. 9020404399103103

    125

    Returns: 735117180482704

  119. 7639400097564080

    125

    Returns: 499226907048416

  120. 4508862073077470

    125

    Returns: 761316888721584

  121. 6836400496017025

    126

    Returns: 591462657520232

  122. 999999999999999999

    126

    Returns: 147519902109597

  123. 666666666666666666

    126

    Returns: 147519902109597

  124. 811189876543210111

    35

    Returns: 24462028021923946

  125. 888811111111188888

    126

    Returns: 73756864709370409

  126. 123456543216789987

    25

    Returns: 55714945330330022

  127. 103456859212945679

    126

    Returns: 73756864709370409

  128. 123456789123456789

    8

    Returns: 16726023513

  129. 12345678901234567

    99

    Returns: 5575389364259316

  130. 888888811012345679

    126

    Returns: 25164471596521500

  131. 88123344556677990

    122

    Returns: 7504216310916973

  132. 666666666666666666

    100

    Returns: 147519902109597

  133. 404404012211439

    27

    Returns: 29248248238223

  134. 1234567890123234

    126

    Returns: 646475143167696

  135. 66666666666666666

    126

    Returns: 21817331427269

  136. 123456789111299765

    126

    Returns: 39166520188298994

  137. 716385113497812334

    123

    Returns: 24462048267074250

  138. 48209834123

    13

    Returns: 4429759478

  139. 123456789012345677

    126

    Returns: 39166520188298994

  140. 23885619856348745

    100

    Returns: 4975000553975848

  141. 98765432109876123

    126

    Returns: 7585959247501861

  142. 123456789012345678

    126

    Returns: 68090790265439823

  143. 122252525252521337

    125

    Returns: 39166520188298994

  144. 444444444444444444

    126

    Returns: 314403345046093

  145. 111111111888888888

    126

    Returns: 73756864709370409

  146. 1234567891234567

    126

    Returns: 474380414264208

  147. 123456789123456

    126

    Returns: 65924729666145

  148. 12345678998765432

    125

    Returns: 7585959247501861

  149. 111111111999999999

    126

    Returns: 18415520400090492

  150. 12345678912345678

    126

    Returns: 6342769928297556

  151. 2

    1

    Returns: 2

  152. 11

    1

    Returns: 3

  153. 111111111111111111

    126

    Returns: 262144

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: