Statistics

Problem Statement for "ShortestPathWithMagic"

Problem Statement

There are n cities, numbered from 0 to n-1. It is possible to travel directly between any two cities. Different pairs of cities may require different travel times. You are given the travel times as a String[] dist with n elements, each consisting of n digits. The digit dist[i][j] represents the time needed to travel between cities i and j in either direction.

You are also given an int k. You have k magic potions. The potion makes you twice as fast as you normally are. Each time you travel (directly) from some city to some other city, you may take one of the potions. If you do, that travel will only take half of what it normally would. You are not allowed to take more than one potion at the same time. You are not required to drink all potions you have.

Compute and return the smallest amount of time in which you can travel from city 0 to city 1.

Definition

Class:
ShortestPathWithMagic
Method:
getTime
Parameters:
String[], int
Returns:
double
Method signature:
double getTime(String[] dist, int k)
(be sure your method is public)

Notes

  • The travel times given in dist don't have to satisfy the triangle inequality.
  • Your return value must have a relative or absolute error less than 1e-9

Constraints

  • dist will contain between 2 and 50 elements, inclusive.
  • Each string in dist will contain exactly |dist| characters.
  • Each character in dist will be between '0' and '9', inclusive.
  • For any valid i and j: dist[i][j] = dist[j][i].
  • For any valid i: dist[i][i] = 0.
  • k will be between 0 and 50, inclusive.

Examples

  1. {"094", "904", "440"}

    1

    Returns: 4.5

    According to dist, you need: 9 units of time to travel between cities 0 and 1 4 units of time to travel between cities 0 and 2 4 units of time to travel between cities 1 and 2 You have a single magic potion. The optimal solution is to drink the potion and to travel directly from city 0 to city 1. This trip will take 9/2 = 4.5 units of time.

  2. {"094", "904", "440"}

    2

    Returns: 4.0

    The normal travel times are the same as in Example 0, but now you have two magic potions. This changes the optimal solution. Now it is better to travel from 0 to 2 and then from 2 to 1. For each segment of your trip you will drink one of the potions. Thus, each segment will only take 4/2 = 2 units of time.

  3. {"094", "904", "440"}

    50

    Returns: 4.0

    You are not allowed to use more than one potion at the same time. The optimal solution remains the same as in Example 1, only now you will still have 48 magic potions when you reach city 1.

  4. {"094", "904", "440"}

    0

    Returns: 8.0

  5. {"076237", "708937", "680641", "296059", "334508", "771980"}

    1

    Returns: 3.5

  6. {"00", "00"}

    50

    Returns: 0.0

  7. {"056998476599558689478","502146030849262764588","620919995209221769820","919068146420804527896","941603087557165394341","869830545472333706527","409105017021051001804","739484109955552943666","605675790163957329686","582454091057902124824","940257256505081454287","999072153750950319670","522813059909040388597","562063555085404884572","821453127210040383225","677537093143383039138","866290042251888301056","949746139449843910876","458835866826552108015","782942068287972357107","880617466470725866570"}

    9

    Returns: 2.0

  8. {"0139687624125885756875581556088149021","1090830320660168509208459191334930468","3906268662170683368549346022735436169","9060127988285725549951542982558609540","6821007941921668155904739117306470295","8362002070713194241182988705179524136","7087720766873408777359409068391649137","6369907022613483204006670871812481991","2268476205605039802463145974988393491","4028106250732062221621376757793704511","1612978667088812477575525326721034920","2678217103802651406973790417929498639","5005133352820182159872085540216361130","8167614400861022403478931269751807408","8682690836158207106975957243149799734","5835848392212270508778663012075938359","7535127282441415029266340506061677831","5064547002705000203873763791239013945","6989517421769368930716084840415623117","8259913046598497287022204033913153746","7045085062777777671205130400145109879","5891429631532858636250925709024553862","5435794613570996370219022344233447843","8544380747298356468032206270115058664","1962989056505173034405260724258515195","5109170897345220578047327024530479065","5928106775214641094300472200373595016","6122758147670932610309404400019542972","0375313897792710024910212530005716629","8335079189221547631142315371007181058","8458691283196195195354358039570693195","1946456437043879606115405455716059768","4330724890396093712505451794189501074","9069049134481798733393785952613910793","0415211945961473891788861009601707024","2664933991233035341476469617259679203","1890567111090849157692345562985843430"}

    2

    Returns: 0.0

  9. {"09247266124","90123790803","21068509704","42607851294","73870470851","27584008427","69057008220","60910880035","18728420068","20095223606","43441705860"}

    1

    Returns: 0.5

  10. {"0949243810922254666","9019601912008107196","4103046990576418474","9930167464143461097","2601098137140184870","4046901947593881379","3167810600950839631","8994196081220156531","1196340800176005144","0204770100926889082","9051159219001622912","2074495272007777236","2863030066170070572","2144188108670004932","5016883508277008931","4781419659270480267","6140836510925992048","6979773348137336400","6647091142262217800"}

    14

    Returns: 0.0

  11. {"097688776986696889955596777899887","906975556996999999599798775995789","760695699657695858755658686869968","696077988858659569976658868858697","879707576799875759987566979775798","855770698958996875779857996969555","756956066676998985975597579565658","759879609897759555867658779869977","669868690886975778558879898896957","996879688098985867798689888969895","895595798906778688697869556865589","667898676860758696577886767859985","696689979977058875859696999795565","999579957875508558977675859687798","695956895588880985695859686657595","898578957866859079658896669589677","895657857689758707895587896889965","998995558786585970599978599979889","957997985765896685055767698596657","595787765997579599506677759779699","595679578877975859560558796979577","576658568688668859765085658558676","995565957868975987675806765958867","688867789996659678778560556997698","776899578857986685677675085855967","778679779856958699959565806776676","756896998867996969896856560979797","898879588988766589579599879058657","996576669665985887977559577506769","959859596959577999699887569860876","879675699859575698665686967678088","886995575988699768597769679567807","798785877595585759797678767796870"}

    6

    Returns: 4.5

  12. {"098566956765876785896586877","906795877676965586979776679","860956959669689865856899776","579055787568577787669977989","695505976869877777578999875","656550995758989588859676855","989799086678587577559668597","575879807787996998899796977","679765670759569575958956986","766587677067788886867768675","676665785609895769956557566","569898879790757796956896887","896589595787097685596859577","768778896895907987965566955","659779769857770777868567767","758775595877697065695855859","886878797869887607786755859","565778785696577570675869676","898658589899598676056858575","975675595655966987505559786","696989998766658565650575995","578996679758855878855058798","879797695659566556557506778","669796866876967559895860897","867988599658597886579778076","777875978768756557789979708","796955776567757996565887680"}

    7

    Returns: 4.5

  13. {"098755668","905589889","850776599","757077996","587706788","596760595","685975097","689989905","899685750"}

    5

    Returns: 4.5

  14. {"099558788967598857585997","908587979687856698566668","980776957657585667955875","557087789775599659865579","587808959988988857877778","876780597675599857595879","799795077596886557878976","875859708567897985878968","897997780596779966577856","966796555088895988589889","685787969807665675577996","777585676870589879685887","585595887865096585567876","958989897968907598569986","865989679559670985587879","866688599968559096667788","596555586877898905567857","787977756859585650795787","559885885556555657068679","865679777878668669608976","565575887975797775880896","968578998898898787698079","967777765898787858779706","785989686967669877966960"}

    8

    Returns: 4.5

  15. {"0977797997577997869899966776678965779699","9056867875786675859997789588689697698599","7508786887957759669957887778765868898955","7680689969966957568766568558778877888776","7876099859895996997565886956885657779777","9688905867987659567695989799586766878559","7769950567755699859765895555998778667776","9889885069699988687679556957759956795977","9786566608559977596595597776677895585695","7579977980788985658869999669658787656699","5799897657075897868865778885789589865795","7856985958709976969598775555975599975689","7676575998590889589658756889777896657665","9679966999898088587879766757898687595758","9755959878978809669756989968586566699976","7597699875769890856979755669667995789796","8865958656895568086556956699958866989758","6566965895668865809889866779568977585659","9998779768899796690665575867869687556785","8997567658856879586098758679857556569855","9956696796695757586906587855559567696588","9776555959588969695860988656778895577799","9785898559777797985759068965596896579755","6886889599775685567588605856969589878858","6978695679856695665878850896589979555657","7575975976858796678686988096895588899595","7875595576858566976755659905579597997755","6888695769559789997956566650675995976995","6677859766797856958857595856058665679886","7867889575877986566557968977508888986688","8958568978957867889798699595880686598769","9688677987558659896558859559686078978689","6967567598899869678569987899688706556567","5787768657996765677675699875586860755856","7688786756896567955565585899695957098958","7998776985675998885697775997789755905856","9888987556557599956967985976968865850958","6597757966766797767857786579867658989097","9957757799986579558589555959886865555909","9956796759595866895589587555689976868790"}

    0

    Returns: 9.0

  16. {"0955799655857","9067879886568","5608977679967","5780875776968","7898096677696","9777908965756","9975680976785","6867699069577","5877767609957","5696756990699","8599677596075","5666958759706","7878665779560"}

    1

    Returns: 4.5

  17. {"098655656599586977677866676596","908565678885795579888755659855","880965987668797588969879685667","659097858665895657785987659568","566905685568585765668977577756","555750765958565988666577788776","669867076595988987565857786675","578586709897985878766557955888","687855690977779985657885889765","586659589079758665567585975866","986665997708699965799885889955","958588577980855778768857868675","577855997768088879667969979787","899986887595808576776875785965","657555859895880878878955557659","955679989697858079869678785577","778568878667777709959779957796","798758785558968990985666976856","689766576577678899088755969556","786866665696677658808878668595","789586567798768995880675788796","878995858588989676786088567587","657877558885675776577805759557","659777775557955896585850565895","666657798988975799967575079698","758578858786785857668656708666","695978659598957576988795980899","586577687896796578557558668089","956657786657865795599859969807","657866585655759766656775869970"}

    9

    Returns: 4.5

  18. {"09998959656858795765959878675576657","90667598895878557988775896599958999","96098999597759759997899676766679656","96906876595598659779679788895966989","87860555768966685897686557578769976","95985068977958877676877965678658789","59975607997558767755856858698676965","98965870958667897585875659996875975","68557999058855785579999796569567759","59996795505667876755667995785975688","65758778850697876675566588878755666","88759956866087677566965587877766787","57596556569805858558655999967769998","88986887577750995957657776997579656","75766878788689078787597959976997555","95558769877759708598899856866556897","57995777566785880587778596665897688","79978675576559755098886977958799597","68979758757655898908569957697577666","58797655955687787880655978559995656","97866888965966587856058876599577878","57978757966655997865505979775885898","95996765976557798695850955757988698","88675986795597985999899098968675568","79785655998897559757775906977759885","86687589658796966778695860696678597","65785669578899986965577996058656677","79697799687769766595975679509585679","59658886958777665879957876890695988","59697668597775958759589676656079586","75766577675667959979788757589708899","68969865755699767975758598655980686","69699799766796586566886585669586065","59587867586895598965799689778898605","79696955986786578766888857798696550"}

    9

    Returns: 4.5

  19. {"09869696698879775768685756678967","90966998969886767987686895599977","89056687767989885978997689586665","66509587576856766585885977856997","96690858957589997679659676597598","69658076575666665759675686775669","99885708769897556877558675586566","68778680979897565595765757878789","69759579085959888895599787575975","96675767806698585958997589679658","89767599560976858688795856988569","88985688969098576585767996975685","78858699597906756765859569577896","96969677986860689998785575987599","77879655858576068759967879569785","76869656885758607775768795699678","57567565858669870775798765899766","79956785896579777086598887966596","68787579958869577806977687777765","87859975588558955660558788965986","66986657597787977595065659596698","88985756999658669975605699999598","56759585975795788878550855998587","78696667758955877867668097789996","59877875885967796888595906699969","65976657796695955778995760675857","65585758569959568979599766087986","79859787778778699676999897807596","89667568598577999675698995770868","99695657965685767579655998958087","67699668756899876968998965896806","77578969589569586656887697668760"}

    6

    Returns: 4.5

  20. {"0985686689587676958575657766568979","9055978898896759957685878695669757","8505588997959968657557675585677586","5550979666566977587968695888765866","6959068986868675879957985799656858","8787608577579975899888559885985968","6889880858695688968898885777587768","6896958075796895856895565757875696","8996875707986969978567879669866556","9876678570675568879769998679678557","5895856796057887565789796589566676","8956679987506968579765558995987998","7696895665760859977555978886595668","6799696895898068595658955658758996","7567778966865609588867686765977867","6987558598789890689598787677975755","9965889898559556088778877659576595","5558796577677988805889568899686577","8777998689597589850899958659995979","5659988857775685788079785676756869","7856589966865569789705789766768886","5578788579955878899950879659679889","6866958589759967859778075955758699","5779858679957588765887709866667959","7855595598688567788599590565569785","7658787766598676686676985085868957","6988987567898567595765566808766899","6558957799956857999669565580795988","5667695886595799569776765877065685","6676588767689577789567566669606695","8975657568675875665689879865560555","9758897655696987559888697989665097","7586566955796965977688958598895908","9766888667688675579969995798555780"}

    0

    Returns: 9.0

  21. {"095956755988559867","908996565776986985","580779987869578876","997069675689775756","597605669556795787","669950596967896666","759665056669989576","568769509969688755","557596690979778875","978659699089599597","876856667805865676","869967999950988596","595778967589055559","587799887968509588","968556988958590867","898776578565558077","687586757979586705","756676655766987750"}

    8

    Returns: 4.5

  22. {"0959865699985","9085557966897","5806957795786","9560986695595","8599065566588","6558605956975","5776550897857","6976598087585","9699659806976","9655667760986","9875598599067","8989875878606","5765857566760"}

    4

    Returns: 4.5

  23. {"09559865759759798965","90688658675987777787","56066799568769668886","58608775658877665576","98680696788975888867","86776086975889988975","65979807866685595665","58956670776577968877","76567987058979958857","57658767508955975869","95888566880895789669","79789865998099797856","58677887759907958857","97975957955970856969","77668959997798097868","97668896578955906698","87858858859786760696","97858968886889866057","68876767566556699507","57667557799679886770"}

    6

    Returns: 4.5

  24. {"095778899577887","909985597778779","590679759668599","796098676978658","787909766875898","859890776988586","857677055889779","995767505876668","979666550685798","576989886059988","776778878505569","788858965950875","875685767958078","879598769867705","799886988895850"}

    0

    Returns: 9.0

  25. {"09589777979779865879856597","90878867559857696588677759","58089657966997675968575767","87807885979756595769985559","98970657566759978599886676","78686096999667986988659985","76585908586857657975956987","77757680975796565778768788","95995959058967658667858755","75676987505859865678887869","99696965850575965569977665","78977687985069688768589657","75955659657607897757675977","97769776795970967556595957","86659965689689088787657597","69797856566896805979769989","56558675855877850967575869","85975997665775799067797578","78669877676655876606669957","98899858789876797760567557","86598697889565675765068778","57788556587879567966607679","67556968877955795797870795","57756997786699598595767055","95657888566575986755779509","79796578595777799877895590"}

    3

    Returns: 4.5

  26. {"096698989766686978879767959779976855686787","909957679778898679857989579678989589576796","690789796856977576887695588575868769857565","697075767878566788865885559899586988886696","958707558955758595575878866757677999988597","879570656988768789975887778666977899977979","967756095889576779889995788675685858997579","879655906757968566896686986669889675896589","996786560556685699658687985776779596799957","778899875055656886599685568779656777796655","675758855507897688799657768855697876765969","686858976570887559568999677656565667898587","689577596688065875676886766886859595757655","897656768598609857657856889775689986755687","687688685677590676787799568575897857977996","965757756865886077855599975855667757777657","777898769885757707579776659666567787785555","896859969689576770979967869599986576767659","888859886575667859056595568985659759757689","758677895996758577509899779977876665568779","977555968998677599690958698587877678996867","796888966669887579589095787786779659857857","689878988859859976995908989579588858675876","795587567579669967598580658997758667887997","955587799576785968576796057559579657598796","578567888667686756679885508658997896598876","998968865887698599898798780675557999769558","765876667786875865995759566076969669975799","777956767755877569878879557709756966565578","985976596956655569577697985690886779755786","998569687665868659688757595978079657958595","786877887596589668577785795658705987566659","698677599675997776967988977966950659985679","857998865786598775766686689697696059856666","586899579776985587567556599667585506587896","599899856767567776958987769969779960855769","658899987778779777759868557957959858098695","875887999969557786569578996765568585905659","667687769658757757786757889555865675850765","775659559695669656678889785757566687667096","896997785568589555876579975978957696956909","765679997597576759997767668986599669595690"}

    4

    Returns: 4.5

  27. {"0976569688988778679596686567767667559856688867","9078585765955695689676958788999769966659558897","7705978899555859888885757575878797555599558877","6850795995586776698696789869896979665899569768","5597056669598575977887798886758599799865769876","6879508599897779665966786856999759657959857857","9585680898978956888988956878856787855598798896","6789658056888675795689875767879798965969565687","8699699506668675799665966766999569659887877755","8595998660957759889665588565856588585879557956","9955589869076785658668755998995859569866966785","8558997865705775898568757975586769767958698588","8556878887650858969756856569569886797767569586","7687579667778056969787575558859556677565589688","7957775775875509788955598785585757699695958588","8596596559558690576557985875696578786598869869","6686968778689975076695559966999995769885979559","7889768998596687708868699555669799666579985767","9988758599889986680577775875559565558775685797","5686899666657795685059555765658969879978899878","9789868866665855967508966768699675878659798785","6656768955886757587980677755558565989569659988","6977779895778559567596075575558677557968688899","8558985768555798597567709587995599579759757686","6879866568576585995567590677895697876958868796","5758888775995578958777556079998598777596866998","6876857666976587657665787709657897599767986685","7859668765859855655585577990876575569557675578","7988798898955856965665598968068955659968568788","6979595795986589965595599957606988975859876678","7986896996569956999898855876860797667695678786","6779577755878575975965656585997067575678699875","6697958968568557996676799997589605969897676977","7979997898996678595955797875587750956889695867","5956768965577667765889558755696599058975598876","5656955658669798665778577796576765507955565698","9655975595977796968989796799957596870779675697","8658895988897565857965979575986688997087676867","5599659687656699877756655965659798757809659678","6999598979687558595899898677895879559790666856","6555787585965598996876678896586666556666099678","8556659675696856788995856687677979967756909596","8889978577689989955989878665868965855696990677","8887888679755658577879867965767898866868656077","6976759855888886569788989987878776799675797709","7778676756586889977858966858886577687786867790"}

    4

    Returns: 4.5

  28. {"095778677868975575675587676986755997678","908678778896588858867975658865789578985","580785659686698858869999997565888866878","767097799868855999997669999987985988587","778907965658958998579667558696696885699","885770599585689567555585769599795876677","676795065666755789786699995576857778856","775969607677867576557759968885558958676","789959570998767855665857679868975786777","886865669088576566979977779655678877596","698658679806757999798897967598666766787","866885678860597858659579598766595895559","956896787575098975565567888988595856858","789558566759906877765597786596698589855","588589577677860986575785958857798959696","588995758598989079785656777559968798977","755996875695778706777757978797867656765","588987965698576960869986968989857689587","688955756976575778057679999568956868897","766975856795667876508556668567799959868","579795675989555579780657958787556787995","599665678985557679656055985589555557956","879668955797698558755505777859685999699","759975997779775676967550555978867568997","669957996795879799969975059957979659857","759956967769885776965875506698797979967","687989589978868788988575960785995879799","985965588657958579557589967065786976978","866899786596895598668857598608685989587","655769658586867979877998785580555965765","778967859665567988975568979765066669865","588899557769999665595586799885609785559","598565785865588877696557975655690667788","958988797878859766897595698999676069576","976887758769585958658596577786686608657","786856886765699869897798999695957980968","698566867575886975889969897957857569065","787897577985559768969599569786658756606","858797667679856757785697779875598678560"}

    2

    Returns: 4.5

  29. {"09656596997678869978765568","90658777678886786986587676","66057785576785868766786569","55508959897866888786675967","68780596578598666596588599","57795099585856877789669669","97859909777855588686885865","67596990958595556765776995","96585579076577586856789555","97797875708869559998767755","78678578680568589986988675","68785885585058776895758969","78869559766508767978769779","86568655798880568779787777","87886855555775058769976599","68686785858766506878656859","96886786699678860786758579","99775767899897787097885556","78689886598977678907797975","86666965686589986770697867","75765687779777967876055979","68878687868568755899508595","57658956978897668577580757","56595689576977585598957078","67669669557677957576795709","86979955555997999657957890"}

    3

    Returns: 4.5

  30. {"09957559998767766997959568879557899875896","90676689685777877678759558955665859769967","96099559768558758596688667558585985668769","57908778587757895895585776755565886597798","76980657855966569798956655687796558769998","56576077758868668686558787677678598579977","58575705865759959998785595587899559989578","99987750677696779668798867587775857555597","96758786086687678685686689687658889875757","98685567807859666586956856559656657688769","85875857670555766875889558775686955999555","77579876685065968857966657597879678695876","67556659855607885557877886666659799956688","77876896795570768887577995798587896769897","78785697667987068889595866589976997585968","67596657766686607859878977678559796887756","67859899866858870958698868899667658776668","96587696658858889098689768999566579879755","97999896887558855909688578997585556668576","78658688565777998890888875679558699676599","97659577698985586668079766876765998697856","55885589858677979888706958978959576677585","99856858669677588988960968789858788598669","55676758685689898758799077658667959777878","65675896855589676677656709855858665559599","88765757968765678885688790687799775688676","89576655657567568996897686068779986685577","75558788857969879997778558608799686987655","95857777795768989979689857880597857556986","56557687666865956555798687775096979798898","56869797558758756685655659799907998859589","75556895866997697658598789997670988768767","88985558869678976556957967968999096855669","95885955855799995759978567885798908799756","99568897975896768969868955667988680678559","87657595869697587866665756695787876087596","76696785789956887767979758885956597809575","59879995589569576986778798576898598790669","89779955775868976755856856569857675556089","96699779565789656579586797758986655976805","67988787795687868569659896756897969659950"}

    9

    Returns: 4.5

  31. {"09666989885685889696868595587978858868695559795","90757778865758667675559758859987659668767576888","67066778569877988989599699878687777657887979889","65609775867766586767966966758858898655965755857","67690877886676955977657785699767758887989559657","97778099587878685565959896967858786796655855985","87777906597757886986585555695676657698678597967","98857960897667897868885887877988569867666799768","88588558055996658659987568895656685599895876887","86668899508699588565789998597676975686759598759","55976777580998876987859576655999885575997666979","67876876969056569757856667787766558777666699758","85767756999506765989695978576589787888588659775","58766877698660778985988896788877765897658786978","86959688658577095999755957889777958776566779956","86885889587667909556685785979795685777688798585","97865567886958590865868697879575798869768888997","66979598659799958066857959758587658758757687685","97867686568588956608576578768965895567568876786","65977568957795965680777675756558978858676997566","85596958978869768857098566676786699959895767878","65965588885598586577908979566689665777966969579","89967955799658558767880756559759777859955575668","57697858595698976956597058666877576686899595595","95968958697679589577675508799676866697885595888","58965657886786757985696880986855759667587598688","58876968856757898777655679086969877799966578558","85759697995878877565765698806989997669885755869","79889757575768999886669696660875967958898887688","99687869669758775595767868998096697958979786697","78856578579687797865885775687908599755989778969","87787868669697755758699765995680878597578989956","86787765698577967689667587899658059666997678578","55795856878586589597967765796997505979867869969","89788679555875858858957669777798950897997657986","86668768565788778758978666769975698069996766757","66558996987789776565575896965559679607978777678","88757687965787679878979677998857697970898555578","67899666879656567756899885988995989998079886858","96868576959685686567965988689787969979709666678","57759586597688688786565957658998777688990865755","55975857856667778689795555578779686775868096859","57755599796958798879667999758878765675866907885","96959579686996988767795558857689897675665670596","78886997879779959675856586586699599765867885077","98855866857577589886776988568965768577575589705","58977578799858657566898588898796896788885956750"}

    6

    Returns: 4.5

  32. {"09556995955979889687555666758","90599679866899785659788558565","55059598975755678856869566788","59509985979896889756989765679","69990888565797866687666685866","96598087597959559897677659776","97988807665976799856558659598","59858770797957989989976689595","98995567069598797768699776966","56776969608875689958896889988","56595757980787768656886999767","98787999587085979767689875595","79599575978807659667577689966","99567967857570887956689977589","87688579767968088666997778666","88786598986758806979959889897","95896999798997860797767665655","66876889796769697099696965768","85558958655665679908988576576","79667769886776697980795578579","57896659688656997697065879686","58686757998878956989605899595","58996786966979797685550596566","65576666789869786955885065559","65668558789787786677799608878","68655999699597895568996580955","75768755997595686755655589079","56876799686968695677896575709","85896685687569675869656985990"}

    0

    Returns: 9.0

  33. {"094", "904", "440" }

    0

    Returns: 8.0

  34. {"094", "904", "440" }

    1

    Returns: 4.5

  35. {"076237", "708937", "680641", "296059", "334508", "771980" }

    1

    Returns: 3.5

  36. {"00", "00" }

    50

    Returns: 0.0

  37. {"09000000000000000000", "90000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000", "00000000000000000000" }

    50

    Returns: 0.0

  38. {"094", "904", "440" }

    2

    Returns: 4.0

  39. {"0919", "9091", "1901", "9110" }

    0

    Returns: 3.0

  40. {"0919", "9091", "1904", "9140" }

    1

    Returns: 4.0

  41. {"01", "10" }

    1

    Returns: 0.5

  42. {"0919", "9063", "1602", "9320" }

    1

    Returns: 4.0

  43. {"0945", "9021", "4207", "5170" }

    1

    Returns: 3.5

  44. {"0991", "9019", "9101", "1910" }

    0

    Returns: 3.0

  45. {"091", "901", "110" }

    10

    Returns: 1.0

  46. {"095555", "901111", "510111", "511011", "511101", "511110" }

    1

    Returns: 3.5

  47. {"0174094882455171152761423221685761892795431233411", "1038742779319865028602486509006138934460661849637", "7308829135984076361542097372601657541200146071777", "4880733599818266038012509478351201640618984143988", "0787008778383710734965109968348499255333743808806", "9423008198972282890781586124258626539246182119762", "4293880952003918195325258677229419698255491250839", "8715719039679976935766582544161633553282536186214", "8739795306291503649293440596342887581257444442930", "2959882960778730382520372975343211325351222640703", "4398390627040053106750045495648216831484920706070", "5181870797405673849265774579830223671554026061117", "5948323918050300483012903885770893074783710083450", "1802729957063014562035666767719162727651399592653", "7676181703570102444279237315785832411595106453089", "1566028630330420134746365281031552217482363035280", "1030781963184541072259108507905341048592541395827", "5263399348048643709617719034175332412908745680774", "2818405592693244290313630190429314820559328748143", "7650973725720027263055268929594505880132227031337", "6041682692561374511500955837837939182801848609300", "1222515630052596973500876356583948397645861551964", "4405152543079623176298054253268266394562535661446", "2890085847470636013657502682551015176002433628234", "3679968202543675890856420343684739800880514363921", "2534916559458732501983263098234023198989135142538", "2077627497978618039235584909287014819359798014755", "1928847465595751740976323890509282450440511590838", "6063322133687770914585256225072693810338480154137", "8005452644437183072938658380703585690893606978941", "5611889123800951559473814479230566666714061214952", "7162464682228185333599207002655034152316882771260", "6350921381129635431034613218986304946036245881214", "1871969371633222124598659342356440982452998386986", "8956256553860742048813318184866199062382627578278", "9344539582377211412889970915196548600208928205527", "2410598315114717820027460890006262200678781609589", "7426322223457654595186508934387304326000072552148", "9601345855858598905304608854391135807006468983551", "5008365271443152289215220990834662288060558405472", "4619714542907313573288545175460829697045014990303", "3648489342221906442246331391806849228765105076783", "1164321642060963158781534581061258781288450644195", "2801812146700540367065663105192783526594906057473", "3474015844068953984305626419571788700580974504088", "3913890620613235508191183240484116859235064740152", "4679878297014602871339429578199229255154371401032", "1378063130715588274306432353345618728457089785304", "1778629403070390743704641858712046879812335382240" }

    49

    Returns: 0.0

  48. {"07077", "70770", "07007", "77000", "70700" }

    2

    Returns: 0.0

  49. {"0990", "9090", "9900", "0000" }

    1

    Returns: 0.0

  50. {"09999999999999999999", "90999999999999999999", "99099999999999999999", "99909999999999999999", "99990999999999999999", "99999099999999999999", "99999909999999999999", "99999990999999999999", "99999999099999999999", "99999999909999999999", "99999999990999999999", "99999999999099999999", "99999999999909999999", "99999999999990999999", "99999999999999099999", "99999999999999909999", "99999999999999990999", "99999999999999999099", "99999999999999999909", "99999999999999999990" }

    4

    Returns: 4.5

  51. {"0919", "9096", "1901", "9610" }

    3

    Returns: 4.0

  52. {"0999999999", "9099999999", "9909999999", "9990999999", "9999099999", "9999909999", "9999990999", "9999999099", "9999999909", "9999999990" }

    24

    Returns: 4.5

  53. {"0902", "9060", "0601", "2010" }

    1

    Returns: 0.5

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: