Statistics

Problem Statement for "ReplacingDigit"

Problem Statement

Vasa is a shopkeeper in the small town Deronje. Currently, there are some items for sale in his store. The price of each item is a positive integer. You are given these prices in the int[] A. Each item has a price tag.

Vasa has just learned that a very rich shopper is going to visit his store. Therefore, Vasa wants to alter some of the price tags to make the items in his store more expensive.

Vasa has a collection of stickers. Each of those stickers contains a single digit between 1 and 9, inclusive. Note that he has no stickers with zeros. You are given the description of Vasa's stickers in the int[] D. For each i between 1 and 9, inclusive, Vasa has D[i-1] stickers with the digit i.

Vasa can take any sticker and use it to replace any digit on any price tag. However, there is no extra room on the price tags, so he cannot add new digits, he can only replace existing ones.

Compute and return the maximum total cost of items in Vasa's store after he applies some (possibly none, possibly all) of his stickers to the current price tags.

Definition

Class:
ReplacingDigit
Method:
getMaximumStockWorth
Parameters:
int[], int[]
Returns:
int
Method signature:
int getMaximumStockWorth(int[] A, int[] D)
(be sure your method is public)

Constraints

  • A will contain between 1 and 50 elements, inclusive.
  • Each element of A will be between 1 and 10^6, inclusive.
  • D will contain exactly 9 elements.
  • Each element of D will be between 0 and 10^3, inclusive.

Examples

  1. {100, 90}

    {0, 0, 0, 0, 2, 1, 0, 0, 0}

    Returns: 745

    Vasa has two digit stickers with digit 5 written on them, and one digit sticker with digit 6 written on it. There are two items in the shop: one with price 100, and the other one with price 90. Vasa can use one digit sticker with 5 to replace digit 0 of price tag 90 obtaining a new price of 95 of that item. Then, he can use the remaining stickers 5 and 6 to change the price tag of the other item from 100 to 650. In that case, the worth of his stock would be 650 + 95 = 745. Note that the same stock worth could be obtained by applying all the three digit stickers to 100 in order to obtain a new price of 655. In that case, the price 90 of the other item would remain unchanged.

  2. {9}

    {1, 1, 1, 1, 1, 1, 1, 1, 0}

    Returns: 9

    In this example, the maximum stock worth is obtained by leaving the price tag unchanged. Note that Vasa is not required to use all stickers.

  3. {123456}

    {9, 8, 7, 6, 5, 4, 3, 2, 1}

    Returns: 988777

  4. {10, 970019, 1976, 10936, 68750, 756309, 37600, 559601, 6750, 76091, 640, 312, 312, 90, 8870}

    {11, 2, 8, 10, 7, 6, 3, 1, 3}

    Returns: 3297500

  5. {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}

    {111, 111, 111, 111, 111, 111, 111, 111, 111}

    Returns: 198

  6. {94186, 855711, 183561, 704921, 413126, 959726, 167151, 347902, 343662, 562449, 153461}

    {91, 182, 535, 266, 99, 33, 962, 775, 871}

    Returns: 10099989

  7. {606737, 880533, 623194, 1707, 358461, 323849, 889751, 132800, 459566, 820852, 180384, 985241, 934057}

    {528, 854, 181, 274, 289, 7, 847, 946, 871}

    Returns: 12009987

  8. {367649, 682565, 70401, 847901, 862403, 128601, 177489, 69116, 316731, 665571, 579121, 193097, 177213, 173833, 580459, 192976, 657841, 804669, 369121, 236773, 375921, 920147, 312001, 29371, 458621, 485351, 758776, 801529, 782125, 5229, 532625, 370569, 816873, 723941, 764105, 358513, 799139}

    {888, 156, 703, 0, 598, 481, 948, 242, 254}

    Returns: 33309963

  9. {545858, 658326, 107070, 975358, 911081, 599308, 772426, 815937, 360247, 462491, 539133, 862621, 320853, 223853, 457619}

    {433, 760, 616, 597, 598, 675, 44, 548, 425}

    Returns: 14999985

  10. {528352, 790316, 46541, 793005, 638021, 602294}

    {450, 685, 808, 183, 847, 548, 580, 770, 438}

    Returns: 5099994

  11. {896605, 801825, 857296, 539937, 967431, 704693, 746051, 679873, 744113, 530991, 575106, 677033, 798225, 968741, 729460, 968201, 629804, 518751, 997801, 723009, 658703, 928180, 839219, 662785, 579385, 817365, 551554, 652192, 902201, 576885, 788211, 863261, 885871, 749981, 850457, 671296, 850049, 893242, 774403}

    {910, 553, 122, 562, 973, 500, 0, 0, 0}

    Returns: 30972755

  12. {626759, 693377, 993101, 587446, 614576, 929307, 741685, 913115, 921403, 700476, 777878, 533696, 989117, 690448, 841761, 767601, 955511, 680951, 706438, 916550, 636266, 595119, 579193, 720161, 844960, 956326, 617830, 644129, 840261, 691441, 839861, 912526, 888517, 619049, 821467, 836425, 537151, 843679, 558508, 862061, 943701, 515131}

    {741, 72, 221, 221, 679, 933, 0, 2, 1}

    Returns: 34375630

  13. {688065, 558085, 691130, 962609, 665573, 559321, 876103, 945571, 572072, 729728, 745053, 557586, 651231, 552338, 744806, 879811, 997149, 835120, 788436, 542117, 581355, 513957, 556651, 933715, 829441, 981417, 860475, 761960, 626177, 569401, 675856, 845581, 912309, 590436, 615201, 661081, 766736, 685206, 968289, 993407, 573567, 744939, 551824, 617249, 739037, 716493, 652986, 977067}

    {318, 310, 462, 780, 781, 952, 0, 0, 2}

    Returns: 37712498

  14. {530983, 536334, 701551, 580886, 596548, 815799, 723369, 676287, 632865, 774513, 705409, 626653, 749605, 747183, 658918, 550529, 629381, 506667, 928515, 898572, 949161, 825949, 740581, 867736, 918446, 672181, 838643, 922605, 951805, 885493, 572449, 534021, 888175, 621001, 672811, 786186}

    {234, 61, 2, 867, 924, 254, 0, 1, 0}

    Returns: 28115140

  15. {992865, 828929, 549603, 523181, 816181, 903293, 640265, 951277, 585639, 768914, 591357, 894825, 526529, 813136, 936839, 872187, 741413, 975690, 541265, 705161, 708641, 745094, 720453, 895719, 920994, 524752, 824251, 908211, 677665, 918121, 639201, 684505, 626801, 727884, 884396, 820670, 521137, 715035, 615571, 928230, 819025, 733411}

    {352, 595, 415, 708, 944, 646, 2, 1, 2}

    Returns: 34835351

  16. {593721}

    {715, 140, 294, 221, 51, 962, 0, 2, 0}

    Returns: 898766

  17. {773618}

    {704, 850, 251, 480, 370, 496, 0, 0, 0}

    Returns: 776668

  18. {870222}

    {553, 390, 572, 23, 369, 69, 2, 0, 0}

    Returns: 877766

  19. {837864}

    {0, 707, 992, 966, 325, 826, 0, 2, 0}

    Returns: 888866

  20. {722185}

    {385, 319, 654, 296, 702, 541, 0, 0, 0}

    Returns: 766686

  21. {800187, 553469, 710631, 763986, 988226, 577607, 552671, 594075, 647889, 799809, 932821, 876801, 827407, 937583, 973051, 675573, 671821, 536121, 844981, 908033, 594945, 883105, 600465, 871027, 661801, 838133, 672969, 882489, 581895, 793041, 629093, 598577, 990152, 585825, 623637, 858631, 698929, 927051, 534707, 960772, 700181, 880851, 671666, 781729, 582585, 984887, 523881}

    {999, 125, 371, 0, 0, 0, 0, 0, 0}

    Returns: 35317488

  22. {626503, 935876, 642230, 970249, 743841, 985971, 581793, 937749, 865429, 692384, 606979, 500829, 782559, 703335, 936417, 744545, 645135, 795196, 620521, 660673, 611591, 656658, 899201, 825919, 842116, 959888, 762161, 803011, 842843, 568033, 846683, 712771, 803434, 670156, 862209, 888056, 959801, 725496, 558261, 672381, 988425, 825449, 723230, 988833, 912237, 775915, 834965, 503961}

    {561, 448, 640, 0, 0, 0, 0, 0, 0}

    Returns: 37333788

  23. {616187, 730301, 660503, 544156, 504733, 754591, 963421, 564417, 736661, 697671, 753784, 568291, 897199, 546239, 718025, 848751, 863969, 583329, 578157, 559649, 546195, 768357, 702354, 814369, 531039, 768653, 762960, 765641, 612801, 659233, 584649, 959866, 741756, 619551, 933051, 626048, 568277, 605605, 658751, 805845, 606625, 663635, 563547, 709113, 735841, 682351, 950303, 835689, 601766}

    {563, 301, 352, 0, 0, 0, 0, 0, 0}

    Returns: 34415966

  24. {813323, 848989, 667509, 909014, 584371, 647041, 804541, 553985, 568917, 544356, 817979, 585201, 673089, 917361, 944133, 557051, 818081, 884859, 662100, 687369, 631346, 626095, 998139, 931609, 928725, 539809, 551549, 733501, 582489, 794651, 668867, 620121, 510201, 670393, 790211, 569213, 771651, 988307, 753621, 584777, 930097, 724601, 535307, 797642, 932291, 909965, 822544, 724728, 962730}

    {601, 798, 421, 0, 0, 0, 0, 0, 0}

    Returns: 36356318

  25. {840211, 653249, 865262, 521453, 789661, 548080, 926801, 935297, 891925, 990821, 768819, 523817, 800611, 593560, 869381, 996141, 738841, 742466, 532455, 653881, 838371, 915057, 902958, 795898, 844471, 531745, 694601, 665870, 510773, 541126, 844901, 790449, 804464, 788151, 889345, 900836, 804001, 904291, 529190, 970801, 999660, 831387, 881151, 569977, 677104, 790217, 820964}

    {906, 812, 154, 0, 0, 0, 0, 0, 0}

    Returns: 36535553

  26. {884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075, 884075}

    {43, 994, 143, 0, 0, 0, 0, 0, 0}

    Returns: 41565625

  27. {440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036, 440036}

    {884, 338, 420, 0, 0, 0, 0, 0, 0}

    Returns: 22166800

  28. {840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537, 840537}

    {848, 250, 91, 0, 0, 0, 0, 0, 0}

    Returns: 37959165

  29. {210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561, 210561}

    {649, 888, 749, 0, 0, 0, 0, 0, 0}

    Returns: 15010335

  30. {67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991, 67991}

    {858, 843, 533, 0, 0, 0, 0, 0, 0}

    Returns: 3263664

  31. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000}

    {1000, 0, 0, 0, 0, 0, 0, 0, 0}

    Returns: 55555550

  32. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000}

    {1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000}

    Returns: 499999950

  33. {1000000, 987654, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000}

    {1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000}

    Returns: 490999950

  34. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000}

    {0, 0, 0, 0, 0, 0, 0, 0, 0}

    Returns: 50000000

  35. {1000000}

    {1000, 1000, 999, 1000, 1000, 1000, 1000, 1000, 1000}

    Returns: 9999999

  36. {1000000}

    {0, 0, 0, 0, 0, 0, 0, 0, 0}

    Returns: 1000000

  37. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000}

    {9, 8, 7, 6, 5, 4, 3, 2, 1}

    Returns: 170900000

  38. {1000000, 987654, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000, 1000000}

    {1, 1, 1, 1, 1, 1, 1, 1, 1}

    Returns: 86087654

  39. {10, 970019, 1976, 10936, 68750, 756309, 37600, 559601, 6750, 76091, 640, 312, 312, 90, 8870 }

    {11, 2, 8, 10, 7, 6, 3, 1, 3 }

    Returns: 3297500

  40. {3222, 765, 1090, 22, 4210, 677 }

    {1, 2, 2, 1, 0, 2, 0, 0, 0 }

    Returns: 18599

  41. {1, 1, 1000 }

    {0, 0, 0, 0, 1, 1, 1, 0, 1 }

    Returns: 9767

  42. {1000000 }

    {0, 0, 0, 0, 0, 0, 0, 0, 100 }

    Returns: 9999999

  43. {10 }

    {1, 0, 0, 0, 0, 0, 0, 0, 0 }

    Returns: 11

  44. {1000000, 1000000, 1000000, 1000000, 1000000, 1000000 }

    {0, 0, 0, 0, 0, 0, 0, 0, 25 }

    Returns: 59994900

  45. {16, 23 }

    {0, 0, 0, 0, 0, 0, 0, 0, 3 }

    Returns: 195

  46. {100, 200, 300 }

    {0, 0, 0, 0, 0, 0, 0, 0, 3 }

    Returns: 2700

  47. {11 }

    {0, 0, 0, 0, 0, 0, 0, 0, 1 }

    Returns: 91

  48. {1000000 }

    {0, 0, 0, 0, 0, 0, 0, 0, 9 }

    Returns: 9999999

  49. {795, 7 }

    {0, 0, 0, 0, 0, 0, 0, 0, 2 }

    Returns: 1006

  50. {1000000 }

    {0, 0, 0, 0, 0, 0, 0, 0, 6 }

    Returns: 9999990

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: