Statistics

Problem Statement for "KiloManX"

Problem Statement

The KiloMan series has always had a consistent pattern: you start off with one (rather weak) default weapon, and then defeat some number of bosses. When you defeat a boss, you then acquire his weapon, which can then be used against other bosses, and so on. Usually, each boss is weak against some weapon acquired from another boss, so there is a recommended order in which to tackle the bosses. You have been playing for a while and wonder exactly how efficient you can get at playing the game. Your metric for efficiency is the total number of weapon shots fired to defeat all of the bosses.

You have a chart in front of you detailing how much damage each weapon does to each boss per shot, and you know how much health each boss has. When a boss's health is reduced to 0 or less, he is defeated. You start off only with the Kilo Buster, which does 1 damage per shot to any boss. The chart is represented as a String[], with the ith element containing N one-digit numbers ('0'-'9'), detailing the damage done to bosses 0, 1, 2, ..., N-1 by the weapon obtained from boss i, and the health is represented as a int[], with the ith element representing the amount of health that boss i has.

Given a String[] damageChart representing all the weapon damages, and a int[] bossHealth showing how much health each boss has, your method should return an int which is the least number of shots that need to be fired to defeat all of the bosses.

Definition

Class:
KiloManX
Method:
leastShots
Parameters:
String[], int[]
Returns:
int
Method signature:
int leastShots(String[] damageChart, int[] bossHealth)
(be sure your method is public)

Constraints

  • damageChart will contain between 1 and 15 elements, inclusive.
  • each element of damageChart will be of the same length, which will be the same as the number of elements in damageChart.
  • each element of damageChart will contain only the characters '0'-'9'.
  • bossHealth will contain between 1 and 15 elements, inclusive.
  • damageChart and bossHealth will contain the same number of elements.
  • each element in bossHealth will be between 1 and 1000000, inclusive.

Examples

  1. {"070","500","140"}

    {150,150,150}

    Returns: 218

    The best way to go is to use the KiloBuster to defeat boss 2 (indexed from 0), then use the weapon from boss 2 to defeat boss 1, and then use the weapon from boss 1 to defeat boss 0. This leads to total damage of 150 + 38 + 30 = 218.

  2. {"1542", "7935", "1139", "8882"}

    {150,150,150,150}

    Returns: 205

    Defeat boss 2, use his weapon to defeat boss 3, and then use boss 3's weapon to defeat both bosses 0 and 1, for a total shot count of 150 + 17 + 19 + 19 = 205. It would be more efficient to defeat boss 1 with his own weapon, but it would be cheating to get his weapon before defeating him.

  3. {"07", "40"}

    {150,10}

    Returns: 48

  4. {"198573618294842", "159819849819205", "698849290010992", "000000000000000", "139581938009384", "158919111891911", "182731827381787", "135788359198718", "187587819218927", "185783759199192", "857819038188122", "897387187472737", "159938981818247", "128974182773177", "135885818282838"}

    {157, 1984, 577, 3001, 2003, 2984, 5988, 190003, 9000, 102930, 5938, 1000000, 1000000, 5892, 38}

    Returns: 260445

  5. {"02111111", "10711111", "11071111", "11104111", "41110111", "11111031", "11111107", "11111210"}

    {28,28,28,28,28,28,28,28}

    Returns: 92

  6. {"84864526478851", "83416770395308", "29625489225615", "78951390260665", "18359094695830", "75743617007499", "07535006290985", "94789444361580", "99026753769079", "18622313057331", "04193312077057", "24852776009269", "71077373905992", "14131085782981"}

    {297135, 157577, 887133, 28164, 114079, 557243, 816852, 369128, 751517, 502951, 363721, 899916, 299081, 276958}

    Returns: 745116

  7. {"2006339", "5454474", "2009339", "7685892", "1693811", "4419064", "6509700"}

    {652153, 980136, 832152, 294711, 368023, 836430, 205136}

    Returns: 725805

  8. {"083", "796", "708"}

    {72932, 146107, 457622}

    Returns: 167467

  9. {"997547639664", "968931936825", "843916225971", "844720428434", "727432916429", "271781875269", "521396769724", "937779798087", "166814867116", "814907390060", "151060778581", "969691474984"}

    {831317, 158824, 270956, 285349, 757854, 32612, 731529, 217458, 732090, 889443, 718218, 807436}

    Returns: 753756

  10. {"6423262051", "0859268641", "1375366553", "9394620847", "1667885870", "9038766341", "6346900116", "9235113792", "7032108762", "9485298419"}

    {212362, 298531, 30914, 584797, 334478, 397056, 190720, 798943, 674405, 161301}

    Returns: 480159

  11. {"320532", "338845", "897972", "085221", "190452", "984138"}

    {604614, 165979, 608674, 98075, 514929, 428848}

    Returns: 421420

  12. {"88888", "28673", "00412", "86496", "90196"}

    {61661, 606003, 289541, 92941, 551202}

    Returns: 252833

  13. {"919792781202", "944701990109", "923936027217", "407737921614", "725965858371", "975618578453", "447721193881", "487414723215", "282237874566", "888286527260", "833276916349", "128775585323"}

    {243373, 100978, 861809, 422712, 635101, 559077, 857692, 163029, 550681, 162507, 746743, 603340}

    Returns: 784127

  14. {"1115728917", "8826588026", "8387689518", "9410983976", "6861411535", "1401169032", "0372582800", "6802945291", "7259568581", "9846027327"}

    {288446, 247870, 802506, 270826, 447494, 242448, 64642, 45702, 140380, 490604}

    Returns: 417607

  15. {"97783560", "30914848", "59146013", "58660901", "97124829", "83341738", "86266693", "45067276"}

    {659481, 32220, 3259, 998577, 689280, 811653, 997887, 721590}

    Returns: 626346

  16. {"349", "306", "111"}

    {842902, 378131, 564185}

    Returns: 721787

  17. {"06788115499601", "64930443404748", "70876576901391", "02488338771378", "03873662268382", "68582960291284", "78481275967327", "60940432515838", "21299793178057", "57439480034641", "67981492395485", "73242981581518", "37995198792008", "60555007908482"}

    {124692, 285022, 901351, 290396, 108259, 601712, 76447, 435356, 398463, 682677, 693514, 197572, 667468, 886079}

    Returns: 802419

  18. {"760937439", "129989300", "571736192", "360858841", "887719730", "860127290", "822270466", "262643324", "417494608"}

    {623146, 223833, 460770, 700649, 974084, 902542, 501653, 375478, 172240}

    Returns: 720103

  19. {"2506134867004", "3802495249142", "2623160124472", "2643073397241", "8623061222824", "1600036489112", "1067343576318", "5370908029583", "3956388971438", "3916790611691", "8889410994775", "6019878236154", "2713014928257"}

    {142903, 772162, 693397, 400552, 432697, 523483, 419103, 167481, 220683, 898241, 216508, 812903, 233515}

    Returns: 810350

  20. {"8"}

    {870606}

    Returns: 870606

  21. {"395655996", "479163226", "068001935", "233084769", "488147053", "597196226", "339055573", "040998002", "929598407"}

    {349781, 836503, 29892, 502230, 56058, 968396, 122441, 274879, 232511}

    Returns: 423494

  22. {"50954173195", "58943828110", "33910010560", "64771280030", "97601613668", "67860039303", "29640843863", "66629995975", "95700650172", "71258764042", "77388805592"}

    {777814, 934660, 703583, 806362, 762115, 647936, 432564, 623714, 235028, 978711, 89576}

    Returns: 876722

  23. {"836699038988768", "440879106639566", "661442347365254", "228207437213169", "045399625363909", "321373219930269", "363802987733045", "199426847760907", "845247665331835", "375519196982102", "086623599342457", "984656677288698", "808781032968303", "224709566404266", "076966269678428"}

    {69629, 6425, 103883, 792273, 675524, 440994, 503822, 197479, 973032, 747181, 213634, 930395, 780485, 180706, 550801}

    Returns: 811936

  24. {"898", "956", "336"}

    {601150, 963313, 778625}

    Returns: 805514

  25. {"4411", "9344", "7357", "8933"}

    {406273, 301367, 812474, 47932}

    Returns: 329679

  26. {"0341", "2281", "4182", "4464"}

    {373584, 247162, 983985, 57336}

    Returns: 335522

  27. {"60475289", "56902324", "36064501", "36441239", "27670687", "40773138", "76441754", "39041456"}

    {777602, 305834, 61996, 674534, 920180, 326075, 257391, 994835}

    Returns: 712123

  28. {"93", "11"}

    {491419, 361980}

    Returns: 612079

  29. {"45272936942280", "01365327987418", "20895360206360", "66087464902009", "41981779069587", "84760059614728", "72934837736097", "57433423674208", "94689715542571", "58827550995560", "99083764699254", "95743781233339", "01992998872564", "92007762643979"}

    {581673, 915733, 983339, 589606, 683787, 58980, 690665, 678189, 237749, 148325, 795127, 175270, 595642, 693682}

    Returns: 935167

  30. {"0574573", "4350719", "6041097", "9579960", "3763239", "9223593", "4051212"}

    {353753, 70283, 259402, 88604, 361148, 264821, 61204}

    Returns: 251363

  31. {"6343297786", "0015170423", "6551786689", "7551070848", "6600427481", "9466754434", "5190229306", "3826860528", "8146921385", "8389601753"}

    {856344, 347400, 749515, 725809, 808538, 849293, 195765, 65978, 624581, 361720}

    Returns: 715831

  32. {"02972307177", "55738003644", "04140069572", "74604324199", "02724180704", "15511470866", "66300731655", "47078068573", "09768974632", "95360445005", "09326173794"}

    {268567, 466307, 894575, 552596, 889466, 975749, 725964, 392559, 138752, 218743, 891897}

    Returns: 888269

  33. {"060520792725", "354824502967", "815161760734", "013405130635", "085283165891", "069255658928", "631694315953", "461950276291", "779763526808", "249755293318", "337178565631", "985568514501"}

    {404503, 465234, 212901, 697836, 115739, 764652, 386887, 400863, 49548, 322734, 506954, 882355}

    Returns: 664579

  34. {"039", "661", "778"}

    {322686, 25024, 375719}

    Returns: 120552

  35. {"6"}

    {373953}

    Returns: 373953

  36. { "111111111111111", "111111111111111", "111111111111111", "111111111111111", "111111111111111", "111111111111111", "111111111111111", "111111111111111", "111111111111111", "111111111111111", "111111111111111", "111111111111111", "111111111111111", "111111111111111", "111111111111111" }

    { 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150, 150 }

    Returns: 2250

  37. { "222222222222222", "222222222222222", "222222222222222", "222222222222222", "222222222222222", "222222222222222", "222222222222222", "222222222222222", "222222222222222", "222222222222222", "222222222222222", "222222222222222", "222222222222222", "222222222222222", "222222222222222" }

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

    Returns: 800

  38. { "09900", "00090", "00009", "00000", "00000" }

    { 1000, 1000, 1000, 1000, 1000 }

    Returns: 1448

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: