VerySmoothDecompositions
SRM 519 · 2011-05-25 · by misof
SRM 519 · 2011-05-25 · by misof · Dynamic Programming, Math, Simple Search, Iteration
Problem Statement
Problem Statement
You are given a
We are interested in very smooth decompositions of D; that is, the ways in which D can be written as a product of numbers not exceeding 16.
(In the product, each factor must be greater than 1. The order of factors does not matter, i.e., 24=3*8 is the same decomposition as 24=8*3.)
Your method must return the number of very smooth decompositions of D, modulo 1,000,000,009.
Constraints
- digits will contain between 1 and 50 elements, inclusive.
- Each element of digits will contain between 1 and 50 characters, inclusive.
- Each character of each element of digits will be a digit ('0'-'9').
- Character 0 of element 0 of digits will not be '0'.
Examples
0)
{"47"}
Returns: 0
No valid decompositions.
1)
{"2"}
Returns: 1
The only valid decomposition is the one with a single factor equal to 2.
2)
{"10"}
Returns: 2
Two valid decompositions: 10 and 2*5.
3)
{"36"}
Returns: 7
All decompositions of 36 are: 36 = 2*18 = 3*12 = 4*9 = 6*6 = 2*2*9 = 2*3*6 = 3*3*4 = 2*2*3*3. The first two of these (36 and 2*18) contain a factor larger than 16. The other seven decompositions are very smooth.
4)
{"1","21"}
Returns: 1
Here the only valid decomposition is 11*11.
6)
{ "96690072263727817109456077437978989865611921905494" , "79233290314037140385229147975704119591395524082167" , "26867939347216007836430628155531884377919141768420" , "06365610954378487525351370599956313412511681025238" , "16842562137672909907446584262552211332161773654107" , "14260376811856200875016101361725787269290838040005" , "96028142922009082953996848601725204390818710563936" , "26773500396954771415236987332150522010696271965128" , "32686632687770608012956717743015704972749156248032" , "40141288877806302292753216709779406694812292814549" , "87855756756508147746449645782450499022271812386155" , "67095286396800001609379846422344574536977229538904" , "76337532451937711378318452198406223039471781203266" , "98136358396467473373231619628610559526681611035933" , "83436063973998022201216911879812025766127766857341" , "46793749081932889769848400301606974999594240250402" , "17799063890822519527796321212443561200317039829819" , "57625879121598537833940116254607758209654717422369" , "05897286557642479442993937774381064692798217499998" , "96369486814466151936216932964152382164014756601852" , "67999797084915743765936026218076419457387416075554" , "95473896083149223705614558824725889390342057857970" , "02780707775897987675857934647165762190021399724731" , "61918596469176616554853906207609511305228048087639" , "10824229482017261134654313857708793722055060617304" , "79985613792955648240475663987823138489983115374761" , "31950683130856295439942280142418867306038719930426" , "26179269330204117601738078665115544831999419468824" , "43146906149033879879842988763376285019047889003501" , "31710756830436381806004504699720029035224076197522" , "92185783410228553587751535570541679666309375823943" , "56309619860227003909194090167060527273472752597399" , "19905822771088365004384047677996769815710183028468" , "00354252339930827728524100829146253458226052958810" , "13206948008098253503835448497614642881014615484213" , "35512975616062928753539300374158442161719757690502" , "69925132426059391244886513269268159585878997564359" , "72764844927492872657349215050240078155379857040803" , "06344742199096215520911882698896225894714800728070" , "38027070830483777728341908672061939100151470754710" , "84399657451263451756636547173321903134640618830925" , "76880744413061379668804208150177008669049843806230" , "41419197655363100312005750355047601061185056500360" , "42294908555869745632246792947998162267498893304519" , "80698106595539327743825321318996099228330426998446" , "59354546726954941110236316547336279996476041119554" , "41220528391033343119714826406721374590600123202726" , "85575817727679363799351284354293208144207372934339" , "87640167038996635693106529509073824912516772842492" , "51971111526006929225064574398820737296585099051008"}
Returns: 181566959
2^4149 3^2622
7)
{ "14493559129346584162509360446925905497894166596261" , "39252146520872233237766858635263985223778884818635" , "94198001282381869975732576116523722976804211545442" , "37423565652937964627853551673291702030216126302549" , "54742164982736719790504918434882756692005953263174" , "60228992959975005496020865187350132259181072293224" , "43355275577030662350647997465688946270667642348602" , "91522315196234041293780472008581058167648638071666" , "97487692389972065502430175624148101229734561900077" , "45462460888498176403066779193984742782247535687081" , "58227157680972127806873998086247212917679461149307" , "17447340551779917778198899777526196634005705878001" , "22110572697718410438661056799698802322397992934693" , "01732003553898488132399421329058997163491627419177" , "86102835881299787306711967472095292359894992026515" , "23447731317987859220293775597252962706835752012921" , "62514967814194973481862129575964275696582417735772" , "80830176587770998557270841755390020906945290037657" , "46329973353906805189631291599213687501882963235444" , "41681005225625320380010020565980785551473328038096" , "51198607100518879799634709127666434130385263915527" , "94214209052278302452896830321675726928866932944393" , "00027712178703885592220697861620140967655685802568" , "09683168190745622017189078136434819885991729194913" , "88711365367540007735349430181798943494477966800449" , "12470247052491420591187448055287923436466736556358" , "07747598225374760415021473606134596896896216611441" , "49213514462071548287782625147302280582128924105954" , "77536216185085254919058932370067103014035253775064" , "90752454081870733557641250139355860583540340093074" , "43187595190547208328811627018107365656327265273190" , "73890356001287354239235738945912891345441403917426" , "51259895957067882462890908586452152406150317914307" , "31205664541739730134387997507711642457254293385635" , "51656650436315660942748912110945175211568697797696" , "39883202410573898582864848255299149086881527708615" , "98247865137205990931808833649797734910891467228732" , "22998852402510522893594831740037430763511186319099" , "98382127938409384230940223354684630604214104218787" , "71246186897655179770248136330967610066585019493794" , "02619647315706408055930322249599302417341317459830" , "00493466099522476548756351740901243117694403414226" , "39349024041404402640805941392722652139882627074801" , "42610014120981399571839797111274524529498340022960" , "79528075492942324478415541834587370793630995281052" , "25868022242438942222074440176780949447497735989802" , "42634419395179437453079034566035264198069161144582" , "17268552720335891920143156954229039511410814617353" , "25550097232087925582455137951342702000028560035554" , "021867520000000000000000000000000000000000000000"}
Returns: 356538439
2^4029 3^2512 5^40 7^32 11^21 13^8
9)
{ "64305784254373336211601859748999331434004158648391" , "79682842778365606066429768965869187822315005310200" , "30021024645510322918135024268731294892821570301821" , "38514594796545714861111216092771989254629530802891" , "73823124595099034589553227290695726683567120486924" , "07324345312132575368148879514227383126304116652257" , "67240919051756355194619552499020260345285395018314" , "32271001052424337595518552936134232986120966535915" , "20046011722342013705727214399912481676110654019122" , "17444061919555911798762659156264477404549852822637" , "50097088046745975374549934409454936639076959336122" , "95910963043157714200576927460131761536622226030912" , "18326689612927786239493981226350921545231973746529" , "32942499809911669281040540890660181344880930028084" , "14785945765779328109872969533336151749382512707874" , "25050594442829697465194591743564586301286542342131" , "05128751246398820470361745058210022762514109847375" , "43253104479900329586881982768937755791059296592912" , "01789696314215633886328736483465155556258693241856" , "02188507775304925169587173497969386329216342819484" , "57443036176371924928750820930227708475245296583282" , "42186102820222596189124561782443811749412566446897" , "96096798663295975134829710356945356871443991824463" , "22910036264321605151044255787305415265866673715462" , "17264134624440181037459898043537200180237099321172" , "59923855619798345005312439119962175000495124200329" , "71229591686779872765431140565722777848263450248168" , "75214731466970176658024517931686312654317324039917" , "40885897896781141045000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "00000000000000000000000000000000000000000000000000" , "000000000000000000000000000000000000000000000"}
Returns: 256271394
2^1075 3^1072 5^1076 7^1074
11)
{"88356743690364996826891211898889898251635759913216","03203299114541318746248798935434742499297920330205","77941545947179707693232564011290895573349310986932","05862323953765211844359558327635337369596404898930","54759684278688848243821052136904212989484622743455","99839989224963339681750991129160066000958771395391","23534569817366037840874054999119144580686273215678","67463744887864117093255262550803747644717804707214","58828704650204484780316888762416319035305757701785","64662772427581013980381446371479601559155201037159","69796158634816751197192047003210427693371780717270","35776997870904147653715276820865671051260081369751","47120773884582543857630294270568389813948627056405","29555573569808524115212513900403133033671021082284","96739057585356800000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000"}
Returns: 34872754
2^4160 5^1785
12)
{"93552706652674268906623348607397931902221744175188","34507891730219952859860871271398063422830495693423","10319146345905820641494865417458473622722170738725","31761678210933844346217032151719245783132173817092","91918452414186708001256835452966562945537249501180","79458492730893594285224800928045661844081426075425","23996963480889557277138741345544654305281072821860","79007596691642794666926580099491479394775215917584","76270848593633574782933819714225283144269948974829","76633402471743456208608823283504010492384823588722","52541568502751711016688689599023079667556419144934","84009791500260128370346954297726292304279497781035","71429147201280518700931524357664714229469021598225","07649969102423036900966393836114389523620644097691","43845658095531037293839325264935118856080439493066","87000123174332390842935901277020203433735870657345","98022739502590764813931448152787481485104064974186","65732045454639657088759661066551682519026364619346","34666265841274192037571805007353839886247207331190","98270848864304556455682617516713746095118763425342","92246880776951965851375245508706521483259171682466","77282836449479212625105683871852091114707466203922","88343244925298237660131981940271796598181305733887","79991806238941032669528011732961658210302881160297","38693478623286552278063923872248499515130905759707","74636415475826058466045718173649564986227042399981","20564116820409163690484860146698385230771529511864","50393268996859238132905267784357384118300595524222","51849395647174249799684860130443973594806485002339","82806096087805844966111841024950295318680683524866","81620115635834031572738988037463399720583670353830","95674563751264122071247581345926772116121719929435","51859416787051185904612337379709728224560274729230","75256117735702601126112801680760940920516758181665","35400937141971048169794880430002942976064387716576","08713011131225642953314658819675479674299848211312","92492665643284559583159188010727927774553935825247","16974788928262050536793651109105950445735014590156","34857587466793407530384781247796562010033709799066","46469260718796889408064983646251725740089757379045","11975646215858105915896728183692407572766827068301","93325358959365172506489209707549460262087933789637","42421087900601229036372611736478167153684433199591","60407571302133874929214289358934946487537617967573","95138775442611808678696889300869502911834732629269","36361120187257447423947580675018547460299609719598","37498262676626442368115290217627233651287856429112","36426236278871763220368983237651162948966994135044","88780698988027728617452217390559472796505336088957","10823718204485199834152808762155473232269287109375"}
Returns: 1541046
3^2613 5^1793
13)
{"97752678303721433905311748999364883967415448845211","91501919723876970245731498645823947268809588858554","89725739707821339413249990144721706220944959792978","46547613794685443731231919070208689394478025811118","27881361778986486114355512812421616724532755186925","52355047811893077053473923948673523435916135432930","12777483130514082707464850543885195825855682380066","60844208380101334006200801249955699082738360472648","20853032938414325577976342013691709558812174830658","31219849209558024557164844062968428012009391379944","59472845260638687568722446208930029015536243505664","33787703189875694503588920846992310305460768669194","06949940410939226824796840900816257220804192638500","33210341324060141722228285827644419487081453817978","62721727756913249547851763374186552853955943624488","72556165809700142628891123740138148155892200994506","66927353544027746312964778885859235337442123121002","23332424480657666825915017423204306321326298141052","45296125083500897179506823039200856186992425656266","54682202758921903814847248378722332286465539710679","15415281458249157603061914234339157700300254693331","21039758268298416767644599643084169723456054848072","50676166247034959032381863739868428534160380007206","11776737774723111775577808047327288748513520199309","88327970600016180329255321917932031507899747557689","68776730843566348445041388316094175857433813317864","47186894540142767026178633469357102684295214157832","73668897942890709918531407872343460188466223159379","69581046206002414928690388304217548587037594740310","52669300524405015695697624413705171614828330237950","24498805327366220079940095674644549184037356009933","95806254667105505752384515126395691047128969044565","83932086296010096193510952331515602352667609582432","02805021518998611721095855905394532705415587897032","26672155660069728008931907203306385273993473867118","39727999827178640462019964739955523850738792145493","69557297063860482158362524099008719813181529693562","04060884927759681409028105337029021027071700805212","11382675674852197992031511700325749907145220471834","40522729604179769144008780729097640431368451154359","48761917599311837148198290601432552827644891969816","64655496344100354072647756941550891201872758513757","87224917294378870752758627063818413062323661688055","86831215489420614926556020941456312919013766050271","78027887439709224261716098515258083884771090992280","78059619356068497985812032768619776428842105317601","17636076534536266987962020820662001064649384346608","28445800403951248870514022435948137280627537657964","43801417802498302186818553542169557530867340524724","49378590497912461039932810358455430515076538302464"}
Returns: 278335805
2^5256 7^1086
14)
{"91535441298905906303491529987384720387984562537145","01664441243853136819300505682157238911152110783915","41721153107968125951787453071277387478140032430321","40287143963166701983263742343916713863446251465373","98308432730508264775198912665956958939406739531196","25927600192470762078314004935828847392586158670198","74243147963954791257289654650639212630419546588171","47158177459782872050789666164744625682060987347092","79372465722800514893825376903680425175487114414391","88823583504186781644926838549719058708744074718613","15940666352065448183099616842123161757446922012608","88498264260007460522348546771240852404562210797951","13319078672685252836835084779254749230994020370112","40948992300395989585178268729721014190851688824753","36630977216613425570847024994791070992098706010556","93333811754072333288401762611675142537287052509016","69389876292710333485291975120648523867958865758565","55941987833269776951253920562741744426817721446775","54228500408553176090669734821951910335406795539863","64605988438295484325280498374062348669262602388281","88535608983677680044137819538440495768365841338308","18079566865911210256529006211270741808663059794327","94298940088012584930761213780236432024223622425973","74270125169339688187008004891384901214558401614309","30361274505185354974390514211021135524966903846695","66899664897342936285420909573707197431638197296827","30336842957102398481262154812963829111205167725287","23269788565165220425194527865569853049620034645218","03923634065313753431925805821525312239834905931648","36699914037459015415157797271774944641846396146135","95781516160103431612498323406878032994354784789569","37348271693644144385771648647017733189325489583237","91816959101444680714420327428249875682840562600457","87355048048077237331502449574864009485922333176949","77313141197233562539581835588807036060117542408298","05131254277073179792215940791143075927185504067032","62207667122611834290455276781357093734393751613804","53842209476148003874173597723168119025645149397347","48535491080624698573783896776925973575715658917575","12281032106927889267362682076529095502000479652439","84459051062199323975763668446486562937864338643096","65997842216248332207862890681144096326588815375812","63220750415809145437523489568755377697811350274029","86998473770644757012961014395042016523868173241548","82326095307057047768825663062550540549732161491470","24903739291056527935140397588711725282491998084972","92553518361323524207513146539776562942890244022210","39776126520599160329625823081727408551080976222899","75407943976576265088843096529856265572492978936657","49913758473594055662233718525284287121486612791296"}
Returns: 900057143
2^4147 7^1481
94)
{"56634881180294134530431951355845905739182358273044","91782369381393998322448149833471001414274960689221","90061827147678428711271059622143250252102872577925","28327354332970919175631616371817620615186283771841","55773263150217387176952033313192917605688917111001","08666401006992089481556996324147604232584784681487","15372951469740392830496273640359255405368035602264","76878690912625847187576603996266692852316340611264","26533409928311430935133742270647713340624496568219","35032058700028301176927149103172477175080132858150","55451105949610222215744905472157291594652413929926","46189408608226808472923508047565726812847229091563","72098102613144838517594213338343830778834403875471","72181142117713628686537064159194942407225068966820","01520571526564090245659071194939279109697980314471","05241990681519586951250820044719666603692606601899","12345947794825625296295636425020842063748299054633","80437383572019161913876365833462112771926224883575","98890683088109948713231049444512219842134665266399","65965732799846466902869119225617095426874541929339","45879344378211502441566815289979663344304402998636","40751090079932845617713852918849390124497722686857","60165350450369740528038144829107267731404427529743","26676503294518845615635475448775184922736205439605","22061156934776130034593146059135322610911275489601","56734184696796733798576661026441778775639561737771","86262718309735448793625531328620941375848399086068","78771325398434398179072176779624432228885916997574","16642813418347439883961944818311765426917839667601","04515715798983467722338243063141271591743606425099","65458301646476062694888970004426781232691030873654","70278932507069204922377214659369848579446657514746","57006854793586261179878662790074400406616288831719","70527918389374070709479401696969565896362899870181","25719696231342556278842288335294233636612277699537","11360805021135936196258799184876571811555793669271","76663656223430710437103480161441073895718904958244","70584574539430846683925906217524219919940032730096","25878394611219519516518004315532326004359484922843","66459240713657706289622351720632643344386760057131","87854743650539202609656090241324863955925639936678","33099603646555666020491057402916902351413595502570","31232555383917237005693585379264679125914291707205","48849222156805254661626777206490236464384140911556","45272417191378623355405687794935266999246717621120","92640301192426209659306721823206341411007271331629","34143515159336871088311166882057375312481527185660","42837094702248273390050950360591304247391085735224","91267283235452091503199351828202698295723139666466","33525103251277778609728690037348415195421937238016"}
Returns: 983673742
2^MAXV
95)
{"43476390042319230693525845175603626492960263679446","74872772794390430983423271462237546927184632826999","61914924611769035240607658915125030912767384568366","37468494029985382174609873539983435333515881305768","73773446944285458862845467376757246569306100554754","35487955587361361373254613415328692217022799877096","42292509128384364202654333396566660823857160042770","41927876652646951135425059155571761850113409714499","52954667888829335340231456058907041359894077224361","21686828271762056920584967140682228390127267088413","91494684371431888229313523710786605889323122465196","55128819504475895459331774794227054659373417643786","20111586563832892536662007651602404489420486957470","52123973524707716280944415904409156509748691678043","86742323941012289738133170516638198706809173322406","63902717737381354677092326923801578203359890654181","57965771792572551015672188489652301190240642498555","54612556253381827573161056477647202423511439519151","97387343476613167485186124428954371545451653799017","81467310810596272431583484789549259609593835645913","90869993257471559701585435263167817698349596119792","51135432630233309687313946390315038566283117636891","03894737559746187956055850498236288977808806906824","70608337283005398276442809808954298256087039524910","26682368419549573968515562343886821558350197576563","47153575113587781369743231494182879018800277585310","99345141393761798088284747808240940654390598589238","37450265830571221634060130776967996582056787096378","46981292740214570292346154806907011163067910692607","79006728649908970243955373199004403766200713619837","36189412426662727898549444016340271755778619017792","99264638399666531337034765969607894644681897312192","57258885594005169122516242167875298391834614607795","87304751505672049158252144704249639688746118950441","63227617501218772046002189304950255235893823978775","28529562572862483008732723954649785152310008106269","23605397824192313986267091249245400906880412841067","85668616147477980532478569594254478299447621097863","72458998027870177886072877390690781496779415979356","68256240040079630832304569391148980506270920503278","03465044163460253922478990822664525685094807368326","23842127095789288095437278893917664737807641126283","15789549544018833062416047161842289437927867596365","35320483554959128847864270048571870751848447354420","96356261579161785305607176383652130458956910790977","62254422138166543667854106276927759371531831447277","92783966481076545300712058274528750929280648841438","38293514876770600947571775883789353640366180312776","63338848893132957719462045615987891373878226202703","81076100958631334663366757639078496360062726424267"}
Returns: 2620
3^MAXV
96)
{"32865141434873944247126035287561875315425224108883","08209170772449692736431959606638645775894813980437","96044567898937604637900890823489606814435098641568","36961234014024170261950911927141089404893715038199","55708165566728622858843325622243930122343180699766","60485848327354375550797473983927939947760011307787","55080491006101724670251800895309846545871296093164","94652450449381292860282489575304875786423721631839","38596586672636426176833607247499850501448488377777","63747432334720050600688071881367967040936643514290","19536778333594099747538535250190577435051775896544","34144361938667712848331617285721701606284811087729","54417874618443750398574638306717822787312033173067","72219270634855281638468332944173889073911978189468","00410072461346958100747527842115990329210486681105","89407262669198832966320930970546158594203647446546","71987331025195350800164525061852600904267964993101","57434985731842826000290646661580998302660647354861","76977518973912051328684140389144807123116661878038","27104529166946867127182851442002646204450130361726","09122625201309737364666161508271070172246918892198","41719461170537202680431866511674628749544048995558","25165232982490396082334804871472259081752637455626","70776100713752011548502295499973781588529183434223","52101165682415593535242144626706982792492544596319","12492737508029764167302616150195866903026302871203","76118323038443756477970745648082001224282786838407","55694386643641275327087401086728276682292721236826","30792034069281481063970848309008628343257310891656","60750575887961279450396392746303422067965463984468","76819385767024216808899641211510464688927219933913","11197935888942380418976013955989110195538945160315","39530575084670899555017488804549548359357119374474","13583464582612560182206088997197143228388269184474","92626663704684991599690317555856443300522862810693","15762897762700704820321516093471269839052079209564","31910038012824128062663003006212864816143414591310","95504750891358674678176165115469833546717844142337","96179731709108886305966132543231439786491745166302","67919924209071545715004017588042423340853779964270","25243122694848477030399962544938919198092072220381","13652756890607129908119564777855733957377038898369","77461314961151349463048525992224284045165392458419","89743118534692242704872952001417920293868832405797","54519669110908980499908694411360667482634450403433","99714391045766309932961562899708053813602721138999","06934255301965577739464430502911283442548333957259","13597924385539460719509558775614630168484030076079","98423221527423753259626608543695018735378612020368","59266232583787203935798970633186399936676025390625"}
Returns: 1
5^MAXV
97)
{"10000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000","00000000000000000000000000000000000000000000000000"}
Returns: 306272027
10^MAXV
98)
{"26412908827575891418402147017349390826035417240946","76954868656279740377861246401137080131692979047525","24484547262794530523354357517466745139850922064239","89440198375220646062737753763287135251641707204734","00812187409956731010957767543058194301218706135763","67690373378153266517216489807053552139738806271245","43309753740633288822741661504761796206135990327118","65583893543090202092793076736522067339806339228998","52283070615859088386194461892974898061118140722566","16185785638893974764040473812945355834093631248973","35623086189311024936671546546680954918934567343130","21204527736277953708530171873703311829011131031065","52913743076763166559089516818498389187712238654819","16639663923899559270408721551535105551553029994801","94393433480034234279865534775138258895886468280160","94919945191633287670754579786759196588768106254428","03651728367742788624412594115923191785901776188773","22429173558437689416908729917019499613903522297860","84403469129127353239703455326012364748682919006651","78336329372618835010511771265033463634451322201513","17048244816729414090609539071420525943561525236958","08241252757010385275346608237556394716456784081252","78034738109588847101026873031803004901660669775183","50089905437347158526621245265705516382714356216614","85877124318610093093299447619945341056901735481155","00958519933262759720603891403282976964933568189582","20632362396396263194637635377422503066583791072132","90847637548667190412279386145986075856173013725191","96298093979520669720914251268223329822682251358452","58307744738119516762091719043038703482961324781882","52040901535105576353341635248425660778085457847279","48178569682329455962181924399809055359105695349667","39658931125024784829123195490718496458144689951128","42204945972804315418936604612092910401802514270311","33541268763443107222466524650009588930187642578614","05838324579237615187506574876901877642591102948497","61351718795910329765820921102145105396098996300167","75825240285967696874219416743347560417432958737134","59995693918649379116317622280764026230665505768188","97759068615258513511581620265885786993553888034637","83909901527761778398610175611162865225713765150032","20465057145189802132668199645236073963704399968973","19190547683418545883705672892499648711352641333706","49100180272653549179297891548797382597399615162586","83605974134603633102113255016418628596375564774028","34766840432723513851105544876396522287787532957335","44858332434605761884114962035872662191428302845848","01799353627257464876047916056383468346160866366818","36453423777526888946966388739638265729466992039468","92146532576565565394082154428954613174907317518336"}
Returns: 273790177
6^MAXV
99)
{"15628794952150546098047089339128876706325758426646","80125974905116923692434709564891401383211500878549","98541151018027039832289275979064209580035598347201","04230750219268416571898856375650183620189468765347","76982638079894612258068359665016411736940829082809","63406728009248973486625619449876968347910104874731","13290957162206752158358944055807339705467768961818","98268465485164092198920041871416135112608571205267","34133642883279917363844550166587562168770885368592","42093076859172370460035316772258310521226797631193","97960177263871328864934471357333623213186140591810","32147574846780515916486350412020500390976966115643","34426903163835983007021096880314600989216231179995","48827244702337590005965357748353939245039420915727","38805908125971157024625176274900733579577750282028","65376441897671999230468776689969641729605645472210","10511468558203052445873068227061907557632222902391","04985522130007291577824455075795099348568707930603","44266918754019512808584264446249623060330705728510","61914105068887763580382558323526067005159658037105","64939677866005372264790434011408599907195951810468","29117435664989253370125425417287009177423289987439","05264881721921094261638746339321050926165264196044","94801436651800280729124103325153728482155710655009","33937037414926538952083544861107667559694950221806","27263685270936700354004369815845256017898398251958","99094431632078758960190053277146551919339365397543","88701888167927083406371418467873195386456020604049","74633422865142254400518132215247878127661676120818","74012749703674056315249038441810202364708636737081","82473341792357137031093529308107480117250233017869","67289646565786195404763178968941041452069041479339","36487966859022433706198088837730653715173444271985","00474142140253646522832525216595300370112964820577","36562010559362390925240068822655303356945790506916","77018068296453171786674607293753106440205603994878","25251754772255870633334751554613513826314211761573","32299812562995198873636884448822004320679205393945","17142923705956355201043205862390426703595405213939","00300312773672356987837062460571653576453141277273","32786689526302312046096873072272624569189644405401","68688770928335415227428701619566537134761386625807","61625806651637386723086836248550659066341394833658","71687286745594289348239409909409939939671302792852","81734884839555331862837628639589387580354740105485","39371237110843168524067994174148144166843390623031","90089956516213921283215134850042765249310958085270","63843712516658247681008934442284098383315606482145","17144151563922285264987259402290086135647701601769","16309418236605832674968041828833520412445068359375"}
Returns: 1131032
15^MAXV
100)
{"50727775039836842194469733696601784920973529009155","98948089617161413562804817390803940530043465793854","34817659296266150876026349039968185126559533579640","74260016956711085598028769937779360390931250327994","95758702379587940563256270943561502475113653808789","32375069455041035513034170387175173575581250568000","76465214078617084285953067640576996506527390690867","41551054570390989954587125044382816046437734778548","50272289682144397341284255986245157724971469696335","76610133458717220789494014620242248771608800955239","88203171282339264438384363954723657218006490742060","54012543610061894219124029140809573872975453743813","03713863275567546641393889678445022275903816442788","39018684740973345306219350808701009509752475390114","56647336442278133606193127654453988617624645248476","30574993231287629470719241071713626800367800429353","33796055930481179851532247615471647486114728205789","07716618752203980607095949679161907818237723955404","00810594732814477637253464086298337201687739570562","60441778611080144498921088519032970957688986666637","75277041928518696815952925496094475011565898546029","71229466763296609242900350127544931096871393053381","52482157426203277324224141727531242697268216500761","12572056963529651977876199945082079234753303995494","05274792072432622361689533162681720215189239916394","49210613205854634806212725875706964470175151018847","26649833053283249785833527525856894001466733759280","92895437115063169605716901170196456018591719868308","50377042518281894203057224827573881203019570112560","00953855059989943254094491986609818770065967745225","98764768325306013998710099732553804539268292946808","23171853306061591275654609458614454568501428253640","24513606081205234415904856934885310618043428735904","19354475123790748344405371925248287002694189962115","87815019354169774871134906124837408464266516455092","82039370753439586211572294440272159123592820158480","44923067343729255854869358889553643083288059231426","49206746096897592907827040282281761619752816291586","86575598665089800760178643717600536169073905396862","14617162465316880605053369961745104274515518090538","82143616133661118678074840628937877451106769130911","58711425798420238824469826296720405348659701467897","00196668452973505136033343468765151761234638472295","30438240420761818630238175446502013476079544592131","93422479454453411414224164722058202570997593575931","96719807646892715903378096890370986043885756861170","96504048267023958627060290558339450809244951109193","06400398019970509864233489752995418291718688925490","50875301208540356331867272941894057981444776664499","34294494924806161279545337804440979301302181822464"}
Returns: 680216316
14^MAXV
Submissions are judged against all 119 archived test cases, of which 19 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class VerySmoothDecompositions with a public method int solve(vector<string> digits) · 119 test cases · 2 s / 256 MB per case