TopCoder problem "Scruffle" used in TCCC07 MM 1 (Division I Level One)



Problem Statement

    

Scruffle is a single player word game, played on a rectangular board. The goal of the game is to score as many point as possible by placing words on the board. The board contains obstacles in some of the cells; no word may be placed to overlap with one of these obstacles. The player is given a list of available words; each word may be placed on the board only once. A word may be placed horizontally or vertically and must read from left to right or top to bottom. A word may be placed such that it overlaps with an already placed word, in which case the overlapping letters of the words must be the same. A word may not go off the edge of the board. When placing a word, at least one of its letters must not overlap with any previously placed word.

Each letter is worth a specific amount of points.

  • The letters A, E, I, L, N, O, R, S, T and U is worth 1 point.
  • The letters D and G are worth 2 points.
  • The letters B, C, M and P are worth 3 points.
  • The letters F, H, V, W and Y are worth 4 points.
  • The letter K is worth 5 points.
  • The letters J and X are worth 8 points.
  • The letters Q and Z are worth 10 points.

Each cell of the board can contain one of the following:

  • # : The cell contains an obstacle, no word may overlap with this cell.
  • 0-9 : Letter multiplier. The score of the letter that is placed on this cell will be multiplied by the given number. Ex. If the cell contains a 5 and the player places a letter B on the cell, the score for that placement will be 5 * 3 = 15.
  • D : Double word multiplier. The score of the word placed over this cell will be multiplied by 2. The score of the letter placed on this cell will be just the letter points (Letter multiplier of 1.). If a word overlaps with more than one word multiplier, the word score will be cumulative. Ex. If the score of a word before applying the word multiplier is 12 and the word overlaps with 2 D?s, then the total score for the placement will be 12 * 2 * 2 = 48.
  • T : Triple word multiplier. The score of the word placed over this cell will be multiplied by 3. This multiplier works cumulatively with the double word multiplier.

The score for each word placement will be calculated independently from previously placed words. All letter and word multipliers that form part of the placement will be used in the calculation. Pseudo code for calculating the score of a word placement:

letterScore = 0
wordMultiplier = 1
for each letter in the word
	cell = cell where this letter will be placed
	if cell contains a D
		letterScore = letterScore + worth of letter
		wordMultiplier = wordMultiplier * 2
	else if cell contains a T
		letterScore = letterScore + worth of letter
		wordMultiplier = wordMultiplier * 3
	else
		letterScore = letterScore + worth of letter * letter multiplier of cell
	end 
score for placement = letterScore * wordMultiplier

You will play the game by writing a single method play. The play method will take a String[] that contains the definition of the board and a String[] that contains a list of all the available words. The method will be called only once. You must return a String[] that contains all your word placements. Each element contains a single placement. Words will be placed on the board in the same order as in your return. The format of a placement is the direction of the placement followed by the 0-based index of the word that must be placed, followed by the (x, y) 0-based position where the first letter of the word must be placed. The direction character must be a H for horizontal placement or a V for vertical placement. Ex. ?H 10 5 3? indicates the horizontal placement of the word at index 10, and the placement starts at position (5, 3) of the board.

Your score for a test case will be the sum of all the scores for each placement. You will receive a score of 0 when you perform an invalid placement or when the method runs out of time. Your final score will be found by taking the sum over test cases of (your score)/(highest score).

Test case generation

All random values are computed uniformly and ranges are stated inclusively. The horizontal dimension X of the board will be chosen between 10 and 100. The vertical dimension Y of the board will be chosen between 10 and 100.

A fraction 0 <= B <= 0.2 of the cells are blocked with obstacles, a fraction 0 <= D <= 0.05 of the cells are doubles ('D'), and a fraction 0 <= T <= 0.02 of the cells are triples ('T'). All these cells are selected randomly, with a new random selection being made if a selected cell was already previously marked. The remaining cells are filled with numbers '0'-'9'.

The number of words W will be chosen between 10 and 10000. Words will then be randomly selected from the English dictionary. The same word may appear more than once in the list given to your method. See the notes section for a link to the words of our dictionary.

 

Definition

    
Class:Scruffle
Method:play
Parameters:String[], String[]
Returns:String[]
Method signature:String[] play(String[] board, String[] words)
(be sure your method is public)
    
 

Notes

-There are 50 non-example tests.
-The complete list of words can be downloaded from here. The words between length 1 and 8 were extracted.
-Each word will only contain uppercase characters between A and Z.
-Each word may be placed on the board only once.
 

Constraints

-The memory limit is 1024MB.
-The time limit is 30 seconds.
 

Examples

0)
    
"1"
Returns: 
"5#17475928
9158971908
61662#6593
29#2909138
15950557T7
858912#029
098668#528
025121716#
9D31739229
##D683##74
Number of words=15
DOPAMINE
CUTISES
IMAGOS
COCOANUT
SOLECISM
GLOM
INBRED
DABSTERS
YARN
CRABBIER
HOPPLING
UNRIPPED
FUSIONS
DOPED
AGONY
"

The following placements results in a score of 802.

V 10 1 1 ( Placement score = 130 )

H 9 2 1 ( Placement score = 73 )

V 0 0 1 ( Placement score = 64 )

H 11 2 0 ( Placement score = 79 )

V 12 3 2 ( Placement score = 48 )

H 2 4 4 ( Placement score = 126 )

V 6 2 4 ( Placement score = 102 )

H 13 4 3 ( Placement score = 52 )

V 14 4 5 ( Placement score = 54 )

H 5 6 2 ( Placement score = 35 )

V 8 5 6 ( Placement score = 39 )

The resulting board looks like this:

.#UNRIPPED
DHCRABBIER
OO.F.#GLOM
PP#UDOPED.
APISIMAGOS
MLNIA.#...
IIBOGY#...
NNRNOA...#
EGESNR....
##D.YN##..
1)
    
"2"
Returns: 
"45907606097855716D07
22402890009467790483
D89#4409987128989678
1377T90D832410496926
D866513417D673621357
40377191947836T24494
76873205#46981717311
146593608D04142D1886
709702200D7957680836
2948926139D647794687
Num of words=20"
2)
    
"3"
Returns: 
"36400492T0018425929623105271770055D06654520DT231745892774D2615704375224236571021301427D1380112164148
388T76726D56726T3592820611873T742322717884025509117934792926959917485299516236940433D18682164D650622
22T77992031358175721T0234DD54T66443524711D09052332D604879661211D48941T078T752374900458873657D17T0915
0427D6D1785061707833262545878732466384480925281307T318953074992263244184782251158233637059013534433D
01214783D7791837972852467741819706873931411652318096939185736270377912621729480805D36683520693551D61
85863759317957995D09851187087D21037D303282D80310738D69830085497229078275949744595054522D882965735548
9628125D0D459366569818D5D705202T30878D55655289256054325545D63T79114105754783106192861260744085209846
68264761613458T1070499671110338117935782D50329004T691885790102130531003897760T1809D14824076863551867
897419DD490837758243581266956348821827T584131599T6575689D039D3074891129735725875550126D3601809837605
03238006D16D373831611591723835DT66679111266531D371495150005884576961765038514D79D9944803D90109876D06
188D40533577522D71154344D2966377498059D5446763238175291411657160608851D2940T9325D927D65D4D8T41102983
279121823940716245710D9266477217317908579424472244182335894D310175033T7300203349536449897T3092T99181
07396D539804287D345D35438569501T997D72D775945601349D32372D316822532451109538158914D29482280047877867
7488258617D44134288493245730T980195273862521507690925D23D8D877D1843817378173311567720699636713412040
6454710550D069D543951D0661620065051005D5273T446904701644168657225724908958194536481586842728540DD7D9
5D403370D3338332D67154717209397D9067T17798128514100D1D200D642678290403546192554267533186179641492934
1D8998280999D422089555517472899387D4308757570067200343632010056740D904579506T33985963768283587035075
D0542219876357926541D1069130008454101556971457527552D81887106D3D2D219387415237DD51932452T44379D32004
69T7T4396540557914T79032420811309074240D24031553548557691599031T3744D9353981072271363737851850695922
07T42111346140177101513T5237686533164557585T37D6D436D9522074474D1111220945D7240144677D95239624015448
D9961167616270128581D9043172340079178D753094368915819196867961113026573DD0453949402D0630026914064733
6479T69128DT32003215683628D90D440D6T660D0458265732144625495750250539352372309554D742614T0D1563971759
864847004D35417390535D867847342D3D77D2021992663534451306687268028425551134597097168542D1D979657387D4
8546D0D04729844660373840842440D01352342405589922D667T351727499262565276075603T1403598202485848800473
10043093440674137490D853909561629D1209524475870721590624708D147581645DD602416316398T5D637D4213D54909
821191420485894T595282916T07987768986484T233506482133882436991821674156D57T696D9784009092T844075D847
6908946164613D0501325843168D80DDDT06043858464825039451975T18T55540039T3133382567553D5T25226375539960
65931969D7110345049974386592714901527835040460682416657D611T37731D17413449058758789325T9424846483329
668T57D732500842775666T644831457698090130693D09428720T1459228608174809D3987725050639309T302089181642
15571311050D162D4837017244551210982216827047687953863D40T11239D66788840309249114141714806369D7729326
0571518452097273D7086767D4D576144593T564777D638778281754055392485361T7D7672579530D595725D14DD67133DD
8848D3249163006181658685D06888060790T571D7068117542541693644D27T94796793047D56061978430D592440807873
D715999500231733901928282440071564255958642794778643002520086DD60T0D10446516515873501293389235335064
360D38457104D090D02437D77664810702267653064T8326993T098770900T14107075045105042850T01383648140906T26
1113666T98409941353992D3D2994D05492108025411965D1833484097957117484204301093520945935827229T69038248
26264251597126996101D137141410DD02325324033216338496D4337909430T0D489587956D804D74170475914920938986
878971067907274388579499377851589T407193969591650818567074D88D12755226T160890034477578T329D82D4T0903
98574650540178836699147914148069354143218D300854115T10999010458767566144D247D16139675004421919492449
2D3157725493019186888133962831051492207319705829124053142907785099751244180963957974341548636873D994
99732T57T758433946489520727543359474912984098161241929785D0561454T24D1795517D77470192712655258D31331
26644365070093068767749973447048205166D92D57493720454855416822400T61816644008131754078T498014D950504
925282297776635843080920587700218738572691659109794992999929171119422775342558046610T23424986D298828
4101931D0975143D20528D2925D24579782881T72149877991602648070618208856034T58789991466116024344244D5621
40978328010800DD32716857356209962468547622240541201543523776817DD08469846T05417200272663634634109187
178281627688907923796553020D422121397099771320109240317172348T5687235D272866877066411227D121T3854976
138591719T1417D8T5240989020600840159992798934305058944640D8872346318738187603749641943298768751791D4
0967044726828386165792D685D585825913346594096567078543875715562899737950434D213836069473001094552894
8692293353D639D54781892D0030290349D0DD48T904131310D9156634790D0777TD4412186990T7205079118471T1023016
1319594138D61114592067088721682582888049907344T8D912D36780435538242387756170664956009959587793249847
20882641885807657D5589833D2730D903210607542868614243D10377300990793063T061434502759309766102D9888349
579340841388T2469527221T1787064608539606450129881798565568682634153409389492871957979004914398537124
D59820839824521778T40432207D1703179431810460268668784442048407520291208236555592099423T9043551669138
308D615207D8D020193T6142D2811592645454D3D655516686329846868733313T8155DD9318000D05248394648300454530
9927894940679538494D7750251341362095D1266691344394858769D97865388956235119703621493D9038394644979495
69312796D50613515T4D9D84D432354D79436745D6640520940016797911667837066676937856488662310521D193554608
6426D5D79811779988611205D4327D116133050D2515257584D5611533232827541129488514637815137209333493737630
7T9423705805979114973135553829549T15T44690179976892455634834029D8847T52DD201T191082325960151991D2417
47563237476074453284314D80T033101083TD2518218091902353084168915564267584253D17289607921D723D4T798380
48264700286969217041DT13519145358126D15869235774383849592802184962T5D6054554355644109959031816245688
44045847991D41016D033787D375793524D32T80776T1T2850706614D9T14895D652772664175215D5121356463480287303
74D4D913869133113458749443522997145091T3060350082685848505216030T9830283694834023871D850725010521575
D50661D7280873T3839261075D7166628T35DT7D2671871832349550370D000751563D934303219861646532285613384494
9113T9829322T4673844T115114285508742DD585532892575543043D39472430088403111T7D5008363928D3664T4D1D148
28363DT50749706923180695D19709422105759D900356992360T819431727T30073714799T15D88D4992480325597666029
0240507716841748047024144520991DD83T00962304180219D8D4222341693D785092985429T518259470286218290T90D0
8T279027263186565324D917862584937030595153022985850817813919404648146240131020477D19T3193544D41438D4
88298203051D742947795D4535100D8348019084400276700962D4479D4581389248574859D5D8T858D26464T7D517324270
0120017823D3358889182D93545261973124714999D6830182609T07108147D8342611DD430405D13019D88872777448395D
547860871190604288D4368249982875316376D675757234139D13D7201556T2327D27364396474017603167607105299153
058T460D706837419221540798717451D153618387987044278D69792534D290279643373199032838289447483371761788
58505853888T21872755800769965807053513100145T0071232754018949088848T6816D032766323641846D64652676293
98811349212951934704303920107T0312D394471567633979478071882017D1601118111586690651176713285496492082
170523612626927279529D9D859994287605802524453371744789DD484023719063D579247783377913318D552842538494
3955998329019169136262158491913T774941097654T0192156D5T84806T70909117D1449274578245T6655272636315183
16830716D89868529716082T745111038D460226D20D410D6115726846877234952535291650433120764928353856DT7724
085304305622D728816038618264532857947D83610D603199249D0434589348517578D35296381795TD27T596377D571425
D7159965706380452821217978114984716D632171599907371109928881072D50250991620042276T6270835633T6981933
592671537544T2132DT8509853460147D4431624D5207D4D4D1D840796986398814175641085269D84799999307893D1569D
6592296079209314825442189155313074837D0T39109649D2DT340317120325491929D69712069117242061111139005702
155196379677657T484276T182981450T860994859617D04D84395101D59892438790019624417496363407936216855T950
D73520090345165509080DD88273598351229T82D4T7078239707517051881875093216737029749472T218935D486597112
655T021141015357911395T894972D953D6622769411375D712D398D42725581855036092D19403518DD2214893769774003
5534298094839825T55327104138595T7853157557201812270235D34459743089676222D558045053082D30657875191044
596210025351D14753699216T5004DD2871DT57283193492281762449399851991475192444275000911T78974628360D516
238671D22D80D238469708649061609938D0810517781931773523932656DD17145546060559766308274D72763639628980
379445738269D9987086842455D44541102D47442433995D45756098551318683041314611663D54560D8402186185278442
84332723197370135181536138314362688D415011801313750810D84D4D3D56663147522810654700604636157059375590
42170537595048071020553589873197722318997514450515201344386738490048D101504975660066D13591D34D394896
9948521D40640950088028449144938677D143T183010248127999726820906907D7395514704033292776D1356352D49465
06T40038025958D501542279985D092095305654627543521D29937338836327025D9D36656T55853897477798404D791015
59209D7822199984066159308D2277149577629264912388271622D927039093119997772951628509672060208353358959
6431547588108761696467993620270223402290536105037791979308548TT11023158559T255076683268651736018578T
01128370698D30359083T398D8905342616D7D98156282072992417583801376788D60245253685471D5683391T617862455
890639D250T846703719904629D0268258252622D9D6666D951220653018007405967470227874492876191D2459564404T8
2027219167946709868D2134514046D530265673747995655948011218TD0715579D74858410574779345349665200943613
4513602966979833066DD79269079905T81D223843D00385711314677D0416176493010D529766440267828581949D632692
976617738756899065793498896576531D59630901T13D572585223718775048033D7D3482295868507522770174T4151594
73535846556608429923028128068D6684727473261032895578746D1D304118269689278D35506D8D316719533604894239
41D102450954017D1041830984634017007T3T4492681T130238992340D6D9T563233529D76770T957404047118147251499
45T26D26988D56823920660624D469211560D55T87D3771D8384T62290D878306079895488753606107699422396022D8499
Number of words=10000
"
3)
    
"53245"
Returns: 
"T975#4237316#4197###8#40#1362#2655403D07816868D17506106867#581655387865639
7279181435#7372636526D500597D#80171631##5010473302116D9005614939D3#5472#90
3##D861869276837D164T664777D12569570038795663069#5552687601#######938921#5
8573286525186D29#703##0515188333#5147725492661681D9640#0221953##3548#22195
6801064441#7054#3986442621057206138#671143#63319D0#6906T58##1D112#9#262295
#271D687T8804340916753#52#90390D144637677117634445D9446677097##1#2829#52#8
6124#2312#5T59395#53289#8263#1954132D6402225011#D19#D3418#66749895#39#9092
10815087868#3243359D55DD078196548403056253D03412#T73D#628D64D293##52068662
#74737627579209D4#386981229534T4059#92894#204781106953#33#5381295862#41388
442859863380#345#770#8D9T065485439T0T8415565699121917##66D7177#9T#63#D868D
28281387128#494394372#75#509795D29#68D91577D6661287D6#97#7515285##5#023020
72332#042215856760080574#96568T798D627864##64D2#053960535108937##6740#12#8
28642#290972D933D#605127#5#278434936334#2#56DT5#7706#5748#332542364#65982T
41#T80D#606#5851#34849389806296#3398757980D779716660##0241#622258608#36973
05950233099D20961916###673D636853722534301#59136870877D812962263#09#312396
##767#0#797741177694#79825797D683#4154#33##D14#140D#7#5#724034550T2217#2D9
59537268439991475#5252823D#35#675#D399486#D9110015#4885284882#97661##3#837
D6773036841TD3#1580999890D64#9D06D2#2648126564#7#19#311947#9#291147008#135
9#2063196D162D34913#82858D654D65149#85#2014177#D32658016995574975708T37#95
5101#639622088D99714829076014995993968516#9#26169#2278330418002#0117#7#441
9#55508D55#D1614#464#020DT#4#435#5D61#2#171396#D9#3226208892727D3563887#62
8D782606200179398129#81#13095#39885400609476715167#D8419658809222585960#78
72D6285#3446D7894573697651#1#6#306292#4T#702911#9#8#883#158#6173712###3086
50#965406899238#D590#46392854795108777#4743739925482388#590694968965#56011
658711605D49162DD9785275176279005#869934#D16459#0283828856#85387#591291801
7D0818572081##720375192#16#091575583D29768593#31978753185410#190711733D0D6
2481520670192027481219402D18#9856909666429834228921D2D73#904092863D7#41022
334316745D59D135#52300318777D1116938400414T#624277968842505#354915671#0#1D
5381667659##5D4D8#558D236D782218515D53446213#TDT#326D94006D443761##7933#67
709#557156841287D7892678#3#5224742430D1#372499366266#455383989D795#02#2450
246#3650##T773#97672457D44#18909443D992D77968#688#D12401104737#58694050373
4116#83##025#7106624D4#128203605991860634#7683#11919022#458DD9370220883418
350615633157338467D4#00555#0598470#56###89D96123962954#615#7T3596#5696338#
#92089339#4569#96#99#2#643#7#103686356612315524215825389296846068#71839390
137969081790#90#9#2620#260199#46#490500204#6#2D5134642146165534518514##418
#588#361428T7364260##097T9D411#06826T84877019675384291D0374003#05243061226
1835D2T70#7T4945508#09596648556847298411857281D50641#613910398581#40553512
7776925409D4474003184#7027#30564#4#01D87961628344#5962090D#4710202309517D9
50#7#3610#57917159577274126886#37D0#9#431928616012317#990441287819D9551904
185#9905976852D#868746499#D04#9355778#666179T839#689D137582199057180830157
84#8555943D988552181D5572#9##3#50D3612099587#995#31308#09641799758D8#82857
7#141D33TT581D54#6T159#5##9##73#4684067#1#14206D41401125D201509098T104417#
2D3D365214#6803#41D617647600#511511D37D06508842#09577634833315#D82638#9892
760#7031125#T35842910228D75380089119364D1T5693382728D335#7431830452084927T
701358#25775##684D4847866##4#47592683869#835T491DD484709455#905#746624743#
4357945567410#6D89#684218#06139779#70210185822405#883117806#251#8567098249
#67#74#T110385582113#53231611#0#3407#9070821251008#23586065454#19154575#27
712094586714808D328#02701#9#704D13249##183504745702#1D252497#085#2483290D#
5792772#92819278288#2624T8772#2#805505866T07#10003#169620#0844#03002#10157
37723507426#6##580349488#840#7#752871D4#20158295792#3#896039D0#12#0076##86
6612321677597593938301916015417#85D17106041119#8677907#3889702508T68T67318
1258285259841297200613407#8554D8913#073770989##2112700621776385#0454527682
013#6DD5#5208860683#73261293172567D093609#74377504#355606051#9#84825453221
4255796#923228#D53403D22232146##0D2113087166#06#D3#93D25#2D551473D13074066
67D4762#1618T6231D8#D16039891226003#15650858#4#D940188D##62##0#83988240D80
1889T167192#6#066T93D4885275#79498674961261329#8521#2#38414700947408#71001
1D725631725856409956293097153645D0156680970327295912376180774#056714858D53
46752299#415#5#33534170579051#475D723738300167#31T3350#71#762132544382#990
75220#91D47#D#04824736#916700#28141246233879##6#135166997D2112#57824053486
988573#2942906679962949077139#02873D107D#64D35#029024282589D5918790272643D
9842717#17478049##34168901T2651561690#3048D30#17714911783##518089#8338#498
2761T865#10176#8935296045#78951#550831070729#89343#69512#0572706#31059572#
23659D46981541847435#1973970D7626845#876800255996576#596876#755689421#1D#1
#901626863#3417230#3##4#943864637296#260359591#5651187D6997D61#123T#T96169
036165#2D437117DD592774T2D35915852989450406105066D55758695##618559#1943374
45699874825465#92D14637459409DD59827D438#1T43#378681#711670184395616766494
177#DD4868041#4937858D305#6636850142630448110808766508#4745736#8#374D#6487
7910280#76464#6540860D2#411972231366088#424367043379450408D30#88D5D68#7316
6640#45#47##9#9T00#822324210910091016#314069889#31782#3253316575201#11##76
0069D004246667629#124112264#8D0D42705505346772#80DD55658#0983#507593692466
2177779506#82694#7#3075030403965#02543#87777225037#09915554235100#575#0#30
292#24D936D4417135734#D499674##16193#1419#4#14D4933#095982388344301026#648
118492783590649666111862498#98230979#30677D6002106045098997991T008#757#13#
923#31004209#D84#T#006802#3558T490393#7D3369717052349673#04#630845302505#7
9D3416#770#66D680847895229##52#5D23758#2689912478009#01#20#9#0032244#D17#3
97339D747#7363##6479#675521T675D279#345561157#40915148#4477681#7D2712#55D2
0533769542566026039199698#360D59#65243519489641276#D74461#40617509708T1#22
1D67593#51#06023#61429506#47#5759173#957T20923D056544199387062#251#05162#7
2137085041769454001#78998562351#452#87690294538778D06131855#62286749T56967
7#4##53D7279180#76568288176379768906369824D4603D2691981136827788#D06373#12
2977#1D#D203#457135150#6997802968#6610002368614261454925746534#53D0836109#
#5265526081533648095904480697326143765932#04449478717247T#138943D#80D41301
37551#60#365287172#9528#83919#4018D4337524T622709#6556###909D44#7465411279
6637#4333556899#9D3362213D5596#41398#4432136D57#84#28030995484#20147#513D4
8#950626883#97554#585116006405671230242516256D792927447#2D#4870208600253#5
093376#631##612260541##89932D2##63242254490#4016699#60#1#04##2087D78312607
532471474216049#2281467D21692873347169571#26##32595532349395#2936900888#50
3490D014686#15#7D4248##742#30340836#21429112313#09#70D0390D123341671258851
91#63#887#2##597771050763628094#50#012847996#3#8#914211470638D190911390##4
006772#6D6641483D9#7#867576D26#102095D959473215D3665402###509D922765111376
#1243#307DT4014494295059686#9DD383#214#69#07#345#148884D185165177143#98422
49D5094661#5#D82583##0#86500#8951715967#D#374273143417797#2629858D8D741113
5287299902220888802616147###97#761536##62#5#4#3D268753377582#11#8250593#10
992950994951824D32282546D521046986#052##38#1806D2##7#16724431450D370133D6#
59100#D32#338#6#67D47301408#666531#T98897#D10#2970331869#501#1645556#31960
791#6784545879030#4012##08916368802400815453#85813#32#41567387#7655898#697
Num of words=2156"
4)
    
"8762345"
Returns: 
"D212983457061447132439
491D003755459114593511
64978642294280377873D9
7088870746208032977931
D57617639653D42D337381
65461501252D1893695570
25D7D47240600838T98318
60445D8709919D52697697
8722696305634368277920
3483331136344839390039
33049D5228354539431879
1865948439653334360268
2465760678191767703037
65934525T90663214DD630
1076616436D52568672648
57457874005054326882TD
4887780670D51D01240978
7099684779064111909824
3360128995695202464531
8926184785975123110959
1496446109253618997510
1944724497163605969932
3302452867494848146368
573320479352T79969536D
805D678330DD212558T744
558D0623272312392594D1
83029303732D2509074089
1495951501760180175739
344859848D02617D01551D
9749D5600426019274D502
Num of words=7904"
5)
    
"786644"
Returns: 
"913859147#446534148D1649#1#5821#40912#135#641#775798652#69107#7188#39406#8601131402454881538854#
5620D00679769122#77009220#338#5896#60874#36#065584881852#44#07254804808000422321254#48453269#8#0
299#9353#126#4874538#214145#9362D7D617317843#20120259844379814#3784539048#24133#9154797192712537
8#3289#535786859527D040361521849#3102038349621#9488657888451699916959044D#77941707336#0191957143
732138#551#9#626#8081#98514#3T9631956D5641970#5#403#3947#69299017636690462#1397581#5102850595585
#9019D24904##8D757058308#826022D67#6030870#880#D649455847019998480D36614961927173971365#17933924
885010858D240##123#811#81D248T1404360#9769T12234654395#46960094D96#2D5446289361288474#4685824291
15032436D6D28D36991644508#92D##26735#DD2937189149006481658#14#2611245967#69584489#103618081##84#
313#535578#34949#55479931599#6868#819118084##5D20467715096##43#DD3968#248137304209#1D6#06#351470
D4166910431177239782093D02#6536#19510#964#7258D20534#5#3160166972D962#653D635654470010D614211375
68979632D79465934449#78553287D09D47#5638398947029841445##271#068#494825327822715#041#1D2222#7911
7199D9#574#94738887623#0037792#037958677707774273727#9337#1#98539237240579##D453536#73#82D488112
27778959778430607733900570#1149802456333669904634441255317006#4#3840321274#856225741#73792340987
7##1763624023862418033986763#78540317628D1536532392909709#443312077T263587998138368888505#098307
20589##09290236##D4084376770851816#9#799#9D2344DDD852533343816701031D85651162#301433957896189030
67#51760735476719D321244933D451340187001#2831722#25#1926978#534D7230D347017D559397953#71461#4134
2T9095369977056305#98#3581042#2649#04#17203516236##90221726063#003348D#8951809488795733266400527
#36195055903472464398#29809496686#7128594#264#11#9241899781783#T7710013D6777571335D56350D8408374
242348862278407809604D9202#3#D954728151028314663579D492429604053784499#0750#7074#63012335#726797
32903006518247772#77079#91872078364#70D5032331187#42510#D928667022185249##852#6469047#270#087244
54198988492##7525971D65##444224566153719252#7020431531994739#8#627##2289830788524#40531363#21428
#0006385#95346317351#595569085916#435106870#4743#1658662687D544337#8069108#79#864001913869535228
2807242967106801398#29#D0#74675151D2#36465779#7601#2160028247216#4#7329815491399D65427#8#9D0036#
51#595##4565D6931#9663924#768544227944957#98#211452872611674216#064457873D4509#13181D38D673#9346
9644344327620155#6845998022723340569078#5#4548#8#11#4406083035#7073950D#670D1302528#35D171D51160
3#468#2571447#25348349915#428#4328#314820#2172T817#3345063254321696797560936#1D64#25#751#810#375
336882671#869788411#76585#9170643313177#4863#5610742361#788#94#07759480595DD48241258171961#4D826
045D#9#4D65#39694#083#76#7889960792#549##0044718T783408723049D128331709#0421978258#D62D375003980
53220973125862D2097#056555#8042661#D0314861438943#657511201513640236708D54#1534429975#5033389#03
D64808073306#413327723#D67630D6205D81#729#58625909070#92035#974366#419#0019400532220199463321#06
9978397483410901067288517543010D831427002#269577D6#081933#8003#058279918971425154243859#70DD98#0
#D33087064987362D#06131496215551497392122707#278401#11D#6349938#1669##54052088195655023977#D4163
9409##22681#950449#7478#55834D10235#18#2#207621492260164076#398314677358195857529#7664#230915#40
349927272#102921#51850423375518#0197#795995092440204301444781D85130883913233#09132931228701##197
#18835D616528891344273212359570241010D18#38950439772832D2862890401342174#69327#746711#47346#2466
5#952766##3216798627#732967#351#9363192D83989431676D3#D5445D13D48##D0037687010797659#5D718D#T448
3930019213042711446375436426519299358#211#84261#984D738739848329430294#86795D14#6434539501865052
6#38030384291624478707307788D05##2#5#1#872#374043537#05031DD9623695430755618436#1182771#7591238#
##17#72#07687D#690D783656713835368554159869#6042364#5561016672051#32657##5493504254#31#857779757
0D9967#867343054500863808548D27D9D#708#360136#868700976D8#9440#77687D85557439244802#8423752084D0
78#303259857517DD2292#99D9#7859189D16#0307#1889D006217608#39#94167580096#904874#9#D#18#401D66378
8969447275507670266581287#1#0001D8723#6674#249D773#211D78760#82148D094#946#31817#570#80690958#5D
3727495797#8#24848#268#133D145079931225328706#13#7D#6882291157#457638617#7D594558#72D55D#7063061
8374099169330#4865208D328030#98#1649304505936#6173493522502882819#15259#35#518388D3257#307458#97
8420951#875802583974#9330#469#1759090#768T46T8D8894913#8#7688#92569535D3189940898804392630629456
9#911159#884743494398053640606340790#873729626#3778900006#423265137329#06##7984#19351#301#367568
D0760#0615#8820559024#8#64D28603459844#646#0#20378723274797D4#2261370171#72736403064D72174570819
2#814#7561913418099923388230797#97317D45#74048772830#5748#157D#026D#5684215776D824162453313503#6
7946178934651#561200D4555178101696657233D904DD4354924726#17220386#772#296#5693401861587733789846
5085D#06828236168#4575D078913#017##75#4126#7#93531780852238933#0D87#D152D45064#92390D5092303#846
#219528#830474#2#230058#3#D89#613#71#9796029D#84426D28456DD51#74663405#371#4895D2557#8455703#567
040560D1570353#9D4417277163542449D62771121140#706814830#38575#14841521#25#91549#440#3#7836#75##0
32#72879D8449#6301339710D08746587703308795536686109239424703#2421298184669874841672028227603###7
83941#50D2195756105765497763177D6741#7#835201D#67191T0695179#3513894D382##5631480764350722142005
4852066456672666#290#144376371D466#14326124329493#9466#03#4772126D75#0037623273953#876539#9746#9
Num of words=3858"
6)
    
"-7634234"
Returns: 
"9570063171917348689829029602D#5744D0782796##1#69#110389#0#4332#457493#429###83633181
503096#568#67D6825##964916#9959666258D793850142884254766#096745775#6224#5#626#53#292
5185056248557362D2537#15038458##90#266#3D#626428D23079#27#8#95587263#4944499D1DD57#6
D293506072828371258276##3734452023847#D5404151716#70#987175696##962280079#77D5D60208
606#9517197#169#02035D24212#788966472464560032#741903818823#238688887646138#01014159
64#359D8755475905565153353893491689#1078212397355325699333#8716#74282035591851970516
0833#05167#0489395#781DD991#9670892239371941502#24844588#90#154814D1473899918#239613
534#101421811899778D75659143#327#580#827500495#83059737751250410D329941D569#1450#034
0822559797#D38505876781#689642034552D2730423223314523503#2792344060675#15#12040#9951
#7403721225658758895#7694#018631496111661873541421406054227867098DD93700D0##37206#80
76#9#28048##7D010#5560747##5829666387#473D64#6060665#5593#57583#2095#72343135898#747
083996300#6776356#369720#875D34D680995729093267827#8#0429D867087613197250#46525#83#4
608582D44695#15994129788424925#9531#5220121864072#015652259#8379714##3093#0908602T61
991#19028D76995D1401236##06D997#7309139794107D228957035763207#8606854905D53#4#507948
90T31903#77910589884130#593792014189#8165810#1057D541835#29665413617282#0D6989719461
409420796602#8769426928799153##20#16298D3#67#186105##9335353103192059100353#31#62702
#243466726690440#113709242036925433#0605306146840287D06#55068481319815775151D95#8712
3759811471D9834814#4#2745959473#33683020002#1#2738224##19804D4555637604#864740873422
36525867203851#59822183D62478#1666397185#5114D0077046####727D#6382#89881D3398#7902#2
6###6983D1202#3695668261205D63#1871007#71429#197404668046736525225399D89#30234#1826D
2285600D9055D42##5660762009636868852314#94D24411934074579530754788#734935229352240#6
7#96161D68262715605241111D647#43013556816#970653109659330058#537#51049772D7752296262
621187#207#82961#416352322761952683727924##171687#45678#286#708882945D501#32599D9109
760503677871756#514129#2181027#2#6714517425197962816742518#177608521663915#708D07145
47820951498948068528#28105##860171548#5028817#77816205449D214#6254909293188491323780
46586896933##3#197427#067#558045496#10274922#D739#2875D43978#3#4#1526#1#805091802##6
7#D8##144225792735015D72#1936921D5079013#35#20318#93496686543960893606D3962394916397
5##77365604#30941884122#8542508359#5304#D3992#09#8589505169222639#4453#6365958309355
0#6268659D1429#2#6203350525103235253068223D0#59273735247403849#57658#1126040735861#D
25#7500223###5165893#6#2829D8296#79103502#18327580231D8513817982D47408925338#4280300
3502623#116028#D905218D863161615#644537811342#976D9352#376#54#6574#53D36#5#370633#16
930#392685788889709#424D761233D3112662679514874#094D72919#68172605806645817434888313
8683#161086380606166D56#0193966450986#4833#0484525069698131#8#695145#45#940960521#89
647408#24D9#25071313747539628033#4#97#079690179193#64719486010733##14##63459854#00#3
882#15262222354161DD#1366456#27#85#51583869207239031615820835975513666D3197367#756D8
589587303487734601964656670#65355#6249188802877876415#0168230166#5D184936#3##7811984
35#794339#8515#8511##62387068540886795776678#1439636#4107869427344404673102#163#3658
#785369172708#63#88209409587396546724016742D2694966185567741903522776466090D77111332
9427#4451#038649642795D286435533890910292D45#76711476020052334357260907177198781474#
5966930174109423#712D534#28151#2011893359868#458574#298286#0110482017386496#747#7251
4#9#559442709#92#60189943775149273586953#762#2809#84D323404#4#2#96821726232927071325
08717961D81#74760735337D419520#6535924#5086271D2451#2911910656227505743602#0038#0198
5826662#8#7#1241#47#470963#023#50966D37802D2#5928D#16717013554DD34#714466449421D#303
2030339709945308415161#51D04498949266323987167D29#17073038060D0457808#542419##2D4411
70466485578#5098#20166178638067421#778055#2838907696093067523#065460997013380710653#
D#8955#87970445#8601795#10299#2152871#2#861D836793084167789D7377#72796003#8916#51833
2#16119#650684835#952014D165#2103010D78#75173383#657570518159#D9992877D9662815996755
#01605D17694976322841669D55#12449994965807#025#0541#8#2##D5#22#7264607493520#146#955
836#179058902#846#0886416330222691241050#DD5326783276342741694711976391###7##2159537
088#7#4358036#940#8391783#4113545082407861#924877371964385#7744765042380508300635625
1324375604#86666421140630#7#839#9831406994759954D1066277733662749#3473#2525224452102
4134893004854454#42894#5688641D71770#83#43#670#2#3D2783661796022198656622438683899D8
631314D95035078158298#9250610135617142##461919663421952239463964747016344#6848696813
2663139962476358111481323220#298019D9596#34487122D1538482D01611D24829#49802D69T22954
01800612#99#144416549325696246#D537D329#415046D8363932055433290##26#35356D#53143733D
567086347D267423D0247366821957663928739842#5510961#89277679#4654040918271#9848571353
6510509D249197667346319#D0#655418147386#03643#5108530#4D0#2129891#9#5#49357030D094#2
403208392886#5356936499D545716872#9#4#205#7802726DD968285D72#0627577#578460587983436
037D6868149655D8325195#5#108804989430#0024421350455188095952D4127192D#242102748572D9
D28801723#3708210244D44#271283482179108044627D53991121#2629#8662013#2996430756#21064
850640187#5396D85D36518546291#D96#572379325909860394988038726#6543#672#9279071937217
9##95#5637D92214#378779D657#46##337#0543#55432857964099858832485##41408666#6019335#8
06D31104##4043086#68551#842658#07##787D788462D655646430333#663618772584#008543002191
22787#62060352745358D40534###6620301409170907047#6#602812#4DD#D#7003D331826#8346##86
773083#3678241835#59435D0#33547396646537048813#0530937D0404D805902#51838951666634177
##955315580185225901008080301018#41254034711#58#95501882#33D9901563343#106784633#296
#8#611588240090047719570D71#710793151474968033480704176#80D11658879#D#54060247897590
15#58143044034D##706505#36454371474814159#489837#6490#828759#2234#43444#474111793052
52733790#2408641334717542544847927703700539024813242822205712050#2D##48843#263037631
81187647357354#94466#76#23070283###13706113200434966126651652798631#88324#514756#75#
12618303#38517D571#3296763246217657414432#6079#1919#5#48331387149829D#0D0511724#3698
50#58327417#02#539465604759882#182019D58012579243273975#9372276190341D#67458#42#6159
Num of words=7378"
7)
    
"111728"
Returns: 
"297685239693929D0##500D31079D872670842617745979968131541#501961431058761552907306663D4
1368104##5740864818006216012010D685755806871837312136472#7061576665D688579074289460833
3020515#36871312391D571747628953765138T7281857D10226980768D152203240D745681T9#54002880
04311516#360T5T562185T70752703335493387#2319T5885614T534637622825066508797D#1705442D70
74241D171729696019247580855599DT95022727611711585715860D88369D6#15856533157940#29966T5
9557T7814500D55927955T920239999297D1633D94619D84937777#T40936639896511#647873947#16353
921086#0345840TT#1616121676712409972D9211D5774839008182566597051951611T70D234545904384
22309840#5445156358533695#97T489354925507705977372644636567#DD4973336729580615D612T089
6005456555D6187119#5T95641D06615183379531205D39380124200#35T19047142D339611868#7137143
11056159102#65895#1079255511D101#804278D362295738521#3377937968T73925096313273D4456437
3875D557331560DT866849210350T00706020TD21282401#73282616575436467259828452832#93294611
53224653862207481#3912137#466D621535922285854879277#2225961695919617684D294D5811794D07
9048014290##9#867738876774#48T07296712#564D3217421D083#042T33551184147558210785T234D28
3183#D2#D16D5086586421839381750#1T85584640T6610403506#84545344D395750#0D7D354112D85051
1##0247920212879331809692#20121823493184130488979511D6334419498DT901595747380642798024
9826884057796372539697618#14057#145677462#59019034T884D6411205362122136113471D9T814714
6162T52378TT95831269111873145344617094D886D288753961T9161585374400D8493#72D89D39240205
516713920023621586D7636776899796655D1042176160439##D#3876D5745878892D5889702208257009T
1977D26#624325T7D25071021499148491469856T080621TDD0T265323385022651409891569351538537#
4D244255774997270208D444976781D710DD4313D85450775#927D22D870202444907057#3365700533503
##62709118DD1T681D4203T9111400D86T38T479730#36736T405D17287656324138920138407118922422
00441945975214493898885465282777844231735355446629030522938707960167521583407D412389#8
51383T69DD68D30585D9038#3#400439#855T02274T944650TT541D5003965870970852T3#674#55564153
4363606092D455D932379659135501400905108D697#93DD#36495129615590751647D9D35990212910442
2140499975360T393T895265370189717202542T53688365078354946648550301535D1037992059679665
91023978119D8504T7259640774D16840567555363402##0001251130985533#T091234D285190723880D4
477294481502#367457421914955D739210T#163T#0866D61986080512#196391#4D70911D522459901827
594915349T191037538196D8273385D7D314420551D37690357#488738049#228448012721296614827219
#51484#77642##2391065404362064796640408510070130375T36593D25D2D60257860457273904901936
70621650802183970T71290615550304192116#66122T265549751733952#60035329592552438853D9138
9185D051186244#256878017T14043D99D51032253225015#75324226609#04#9269T43#74697232812303
81986578175960#5T49581DT1802212922440D0908000541131691041376#3177827187777494026675847
D70D7736816#4387352082920583483157261140#0076365103D7182#9616#050695260740141500474#30
3#76#55786D151475871#4523303383944406765176346#44861T21431515#343686D40454D641340879D4
60822382069552364757120D63980683D924D525D1403427303815928063849##15884D649763561547362
551715561881121713T183487746596725T86065D2658107536D668451950611100D045553203329D45931
86272577366952#194264960027659754959548855#D472#146543123102312954598TD#148D6524949305
73045310805T4168439848803574419946D19100T37718450#53558117661307#69062729185772850D820
467463174109816D45640429D27#567852060515535#30125D229851D19D19#320T25023261684407#5325
97892D661875165479#42563#0266884851T508811038#7215901T99106390988T23460003850785T66537
91593TD33T75923#9572290T1036587836729D#081438DT9442457427681626T2281662DD8143307473#78
207#6648151121133238D78785223092206040059D6623853423998138585##8426038527D198007700652
8#D94252224D259T4440239D116288106382126#536#40T01D0167891615579203677683224D9937688T72
028203756395306273443D88481T8685675291#4532278121259490983828944981#2D048313761150D983
4637651D340099537#823262065D43286960#468498D44302161843215608855948333217#537306075788
32664D22D4981683D89608218D004216176813T364T628D2#59335584D990082DT1#328644943970886008
D235996912092450310D002D60628158147294778#685627412D85546#092048753935#04126T168413326
23635138523996442138347252502779534#26253155780458D39T15078#49443502#26906388#34414419
17104963363063489941804278824072465935672498966222839866804256780#2438326399475567406D
1T1843T567D595723T596150D40387594422245D8D85#9230417853D63600336675724149D191365165296
6017225#D5316200334D683528799#46D#59#395D#7892539942D36D#79867822113D71702797#44316059
D10D237139#73451709#11036D2127666DD691870502#1#8291516199872653T9025737332336581340281
9850468199082D9151478D3299579D253990029079#737D36649250765D8696735T100943D171625709366
033763D8D#604225205252722894233470#263860236696398D69700D98434041827T962#8572456006D22
91551T95171134258463866247374D7T869689638423626330321900434TT9057#529755646139213#5387
#73D68047518312388790391#1194413T7853817156934515372T76152029346279821173482070T47#398
8544383#878#0583029604458945087#181082937861197188D197727350T34619144042994096097684#1
6628T9#40D870TDD4296342128644571#3D7549499936012756496TDT8952#54959470790#919650D51478
735374055268818039340470171597208D3487D839T3771023171T868597767T5495540807#74976787183
7T1T##0529D0214680813D4968T27007451#720715D813D3223592#84D64777999228D36395629D892#744
2663151375802556277024508#32435D850819021299#6672867394D#4443373D657790693497007T88197
7474123142422250183#718682334722414347T185015924751934#4707#605##4836597D3667207439032
0753560#13472075T7548498540770707254448229617809350036274D74260DD942737331627011302150
D61732840#9395513#34078#21175495#1733D9888174870173178D89829403D416921535510TD512#6903
3563401652D6585803910385257626918894448444621819580D55904480246363#4942144851#55482994
#196D3722902413029D76299578207331571376189730047037D8030D58703506431191784410933218011
255D557029#74#4132332D36D91719D4825D34#D85958221478458099T492054143747135#768488#97D01
2538226D82D8661291251D80855D793D7D6501373655D0859485747010038124721392888T6894D8531738
838755966196708D5800773492D90902118764128454288331D93573712137#73#25380763163T85512588
230535734D5T90D334300073802762509D007853052894136887#72987#46T7D6481T1#21358084#883449
0D3T008144#95D4073555#6T07141088T549534603432561644940000940295794#0595881#773585411#5
5644T45318D547985T004391662110#1836906052127364029345836822#81031D169#5957233025139628
4D41147418146959578587734087736D406796T02652810649541399260908#168D72771964173#2508516
#45534D30105#33423909D67426615142752231465963288437382402672059D7#1D#968309538D8817#18
72692140953669124467399D#17737988926052332876815913178D3472077686929412599657970184578
D24548700DD93299728573514863330411586#1600144#594172522816DT8D206139111DT6997798091648
320215150D2581414426546835911#554905#5#56066638278D532237691055494D#90300D71D#87691532
387285106597645D119574#8627D85911391134623287T4758D070017924777006086359741672409D344D
91715460822207444438#4407359T171#T44419648291D9689D315025733462843191D15T2500128282650
71490D1340366856741500#903620612933922409220D16619291699556790D9175387786D771852180#69
6D465037003394417570269388D139843967110544656077271373337481342D12923455176#402D189D90
70843603025209804383984#D19556365966890024429588159D0876038531003351#95274977#7D2D166D
779885D45704182787522586021713148#7D85734406778045746D4585D188#27D76885351483285003227
Num of words=5676"

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7861

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10500&pm=7861

Writer:

Unknown

Testers:

Problem categories:

Brute Force