Statistics

Problem Statement for "RoundOfEleven"

Problem Statement

The government of a neighboring country is running a game show called "Let's Make Some Money!". During the final round (the "Round of Eleven"), the contestant is given a number n and some money. The goal is to change the number into a multiple of 11. Contestants are allowed to spend 1 dollar to either increment a digit of n (to a maximum of 9) or decrement a digit of n (to a minimum of 0). Upon reaching a multiple of 11 that has not been selected this week, the contestant can either leave with the money that they have not spent or choose to keep going. For example, if n is 31 and the contestant has 4 dollars, he can change n to 11 (by decrementing the 3 twice), 22 (by decrementing 3 and incrementing 1) or 33 (by incrementing 1 twice). For each one, he would receive 2 dollars.

As ruler of Rainban, you have decided that you will allow each of your subjects to attend the show and collect all of their winnings; fortunately for you, you have so many subjects that you can win every prize on the show. This week, all subjects will get to start with the same values of n and money. Once one subject selects a multiple of 11, that multiple cannot be used by any future subject. In addition, you cannot add any digits to the number (so you cannot change 9 into 19), but you can create leading zeroes (for example, changing 19 into 09). Return the total amount of money that can be won, if your subjects play optimally. See the examples for clarification.

Definition

Class:
RoundOfEleven
Method:
maxIncome
Parameters:
int, int
Returns:
long
Method signature:
long maxIncome(int n, int money)
(be sure your method is public)

Constraints

  • n will be between 1 and 2^31-1, inclusive, with no leading zeroes.
  • money will be between 1 and 500, inclusive.

Examples

  1. 31

    4

    Returns: 6

    The example from the statement.

  2. 31

    5

    Returns: 11

    With 1 more dollar in the pot, you reach 33, 22 and 11 for 3 dollars each, as well as 00 and 44 for 1 dollar each.

  3. 110

    3

    Returns: 7

  4. 18392091

    103

    Returns: 660000066

  5. 2147483647

    500

    Returns: 427636364064

  6. 2147483645

    500

    Returns: 428181818610

    Close to the maximum possible return.

  7. 1555555555

    500

    Returns: 430727273158

    Closer to the max return.

  8. 1545454545

    500

    Returns: 430727273158

  9. 39

    4

    Returns: 0

  10. 999

    3

    Returns: 1

  11. 555

    6

    Returns: 20

  12. 25325362

    123

    Returns: 914545546

  13. 2134874533

    1

    Returns: 1

  14. 23598723

    1

    Returns: 0

  15. 11

    1

    Returns: 1

  16. 846930886

    384

    Returns: 32118181835

  17. 1714636915

    278

    Returns: 223818182042

  18. 424238335

    29

    Returns: 406835794

  19. 1649760492

    387

    Returns: 321090909412

  20. 1189641421

    10

    Returns: 235366

  21. 1350490027

    363

    Returns: 297636363934

  22. 1102520059

    191

    Returns: 140363636504

  23. 1967513926

    2

    Returns: 0

  24. 1540383426

    41

    Returns: 9601620939

  25. 130736

    173

    Returns: 13963776

  26. 521595368

    212

    Returns: 16736363637

  27. 1726956429

    68

    Returns: 32363636396

  28. 861021530

    283

    Returns: 22900000012

  29. 233665123

    363

    Returns: 30645454567

  30. 468703135

    68

    Returns: 3627272724

  31. 1801979802

    430

    Returns: 355454545810

  32. 635723058

    23

    Returns: 76839876

  33. 112587

    7

    Returns: 1139

  34. 2089018456

    394

    Returns: 326000000326

  35. 1656478042

    12

    Returns: 1388614

  36. 1653377373

    230

    Returns: 182727272910

  37. 1914544919

    422

    Returns: 352181818534

  38. 756898537

    25

    Returns: 110083921

  39. 1973594324

    199

    Returns: 152000000152

  40. 2038664370

    316

    Returns: 258000000258

  41. 18

    414

    Returns: 4066

  42. 1424268980

    92

    Returns: 52727272780

  43. 749241873

    457

    Returns: 38918181833

  44. 42999170

    363

    Returns: 3023636666

  45. 135497281

    497

    Returns: 42500000040

  46. 2084420925

    306

    Returns: 247272727520

  47. 1827336327

    8

    Returns: 60752

  48. 1159126505

    337

    Returns: 276000000276

  49. 1632621729

    347

    Returns: 286000000286

  50. 1433925857

    31

    Returns: 2438718205

  51. 84353895

    125

    Returns: 910909182

  52. 2001100545

    83

    Returns: 42727272770

  53. 1548233367

    5

    Returns: 904

  54. 1585990364

    435

    Returns: 364727273092

  55. 760313750

    44

    Returns: 1321385662

  56. 356426808

    88

    Returns: 5445454531

  57. 1889947178

    277

    Returns: 218909091128

  58. 709393584

    289

    Returns: 23481818180

  59. 1918502651

    404

    Returns: 335818182154

  60. 147461239

    255

    Returns: 20590909091

  61. 12640950

    433

    Returns: 3681818550

  62. 1843993

    177

    Returns: 138818196

  63. 198421

    240

    Returns: 19891108

  64. 19759

    435

    Returns: 3788217

  65. 1892

    468

    Returns: 412230

  66. 927

    98

    Returns: 7932

  67. 60

    318

    Returns: 3108

  68. 7

    500

    Returns: 493

  69. 9

    8

    Returns: 0

  70. 6

    34

    Returns: 28

  71. 1

    1

    Returns: 0

  72. 9

    10

    Returns: 1

  73. 1555555555

    4

    Returns: 0

  74. 548673492

    498

    Returns: 42790909121

  75. 2147483647

    497

    Returns: 424909091334

  76. 1846345234

    25

    Returns: 938924575

  77. 1234657890

    500

    Returns: 424545454970

  78. 2103324123

    500

    Returns: 425636364062

  79. 2100000000

    500

    Returns: 415636364052

  80. 1111111111

    500

    Returns: 420909091330

  81. 2000000000

    500

    Returns: 414909091324

  82. 2147483646

    499

    Returns: 427090909518

  83. 123456789

    500

    Returns: 42863636394

  84. 1909090909

    500

    Returns: 414363636778

  85. 2000000000

    200

    Returns: 142181818324

  86. 1023456789

    456

    Returns: 384545454930

  87. 1222222222

    500

    Returns: 425818182244

  88. 1564738574

    499

    Returns: 427272727700

  89. 1173741824

    40

    Returns: 7856160812

  90. 1000000000

    500

    Returns: 414363636778

  91. 999999999

    500

    Returns: 41772727310

  92. 1000000000

    499

    Returns: 413454545868

  93. 1923342882

    28

    Returns: 979403484

  94. 1

    499

    Returns: 498

  95. 1023456789

    500

    Returns: 424545454970

  96. 1234567890

    500

    Returns: 424545454970

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: