JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: NYC Lightning Round
Problem: ColorCapture

Problem Statement

    Color Capture is a two-player game played on a square board of D x D pixels. Each pixel of the board is assigned a color. Two players start with one pixel each, player 0 in upper left corner of the board, player 1 in lower right corner of the board. Each player controls their starting pixel and all pixels of the same color connected to their starting pixel with a path of vertically or horizontally adjacent pixels of the same color.

Players take turns changing color of the area of the board they control; on their turn the player changes color of all pixels they control, and thus possibly takes new areas under control (areas of new color which were adjacent to areas of old color controlled by the player). The player can't change the color of his area to its current color or the opponent's area current color. The pixels which are entirely surrounded with pixels controlled by one of the players are considered to be controlled by that player (and change their color immediately), since the other player will never be able to reach them.

The game is over when each pixel is controlled by one of the players, or when a total of D2 turns have been made.

You will play this game against an AI opponent. AI will pick new color randomly from the colors of pixels which are adjacent to the area it controls. If no such color provides a valid move (for example, when the area controlled by the AI is surrounded by pixels of opponent's current color), AI will pick a random valid color.

Implementation

Your code must implement one method makeTurn(String[] board, int timeLeftMs). board describes current state of the board: board[i][j] gives the color of pixel in row i and column j denoted by uppercase letters of English alphabet. timeLeftMs gives the amount of time left of the initial timeout, based on tester measurements. The method must return an integer index of the color you want to switch the color of your area to (without letter encoding: return 0 to switch to color 'A', 1 to switch to 'B' etc.) Your code will play for player 0, and thus will do the first turn.

For example, in example 0 valid return values during your first move are 0 and 2 (for colors 'A' and 'C'). Colors 1 ('B') and 3 ('D') are invalid moves, because 'B' is your current color, and 'D' is your opponent's current color.

Scoring

The score for a test case will be calculated as follows. If your code returned an invalid color or exceeded time limit, your score for that test case will be 0. Otherwise, your score will be the number of pixels controlled by your player in the end of the game, divided by the total number of pixels on the board (D2). Your total score will be the arithmetic average of scores for each test case, multiplied by 106.

Tools

An offline tester is available here. You can use it to test/debug your solution locally. You can also check its source code for exact implementation of test case generation, game simulation and score calculation. That page also contains links to useful information and sample solutions in several languages.
 

Definition

    
Class:ColorCapture
Method:makeTurn
Parameters:String[], int
Returns:int
Method signature:int makeTurn(String[] board, int timeLeftMs)
(be sure your method is public)
    
 

Notes

-The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
-There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB.
-The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here.
-There are 5 example test cases and 20 full submission (provisional) test cases.
-The match is rated.
 

Examples

0)
    
seed = 1
D = 10
C = 4
BDBABADDCA
DDBDCDCDAD
ADCDBDBDAA
AAACCBDCBB
DCBDBBCDCD
BAAAAACBDA
ABCDBBDADB
BDABABCAAB
ADDABAAAAB
DCDDBBDDCD
1)
    
seed = 2
D = 20
C = 6
AFAFEEECDDEBEAEADBAF
DBFAACDEECCCCBACABCC
BDDAAEBFABAEEAFDADFA
EBAFCDADBDDEBCBAFCEB
CCDEDCAAEEEBFDEDBDCF
BECDDBFEEDDBFBDFADEF
AFECADCDEABFECDDEAFE
FFBDBBDBEEFFFCAEAEAF
CEFBECADCFBAECCAEFBB
BECEAFACBACFEEBFDDEC
DFBAACBAEFEFEBFACBAA
AACCBFFFDEDABDCCBDAC
BFFFFDBFCFCACECDBEBE
FAAEFBCBBFAADCBAAEBF
EAEEBEBAEFFFECFFCBEB
FFAFDDCCCBDDFBDEEABB
BEFCECEDDBCCCEAEACDC
FEAEFACCDBECDAFFEFDA
DBFFBFCEAFCEFACDFEBB
CEDBBBCEFDDAECAFFBED
2)
    
seed = 3
D = 30
C = 8
AGEEGCGGEBGFBCAABFGGDHFBHCCFEH
CDBFGGEHFAEFBEDBGGGEFFAFFEAEDE
CFDEACDEDAHDEADABHDGEGDGEAAHGC
GEGFEACCACDAHABHEBAFDCADHCCGBE
FCDHBBHEDGFEFBABHEEEBFCEBDGHAC
GABHEEEDCBDDAGFHBAGHDCDCCAGCBA
FAGABGCCFBFBCEFGBAGFEFABBBEECE
CEEFAGHAGCBEFGAHEFHEEDAADGGFHC
BHHBEHCEEDGGBADFCAHDHHGEHFCEHF
EGACDHGHGBBBFHDDFAHHABBEDEGGEF
FFFCCDHEBCGBHCBGDEAHEHGDFGHFAF
GBFDHEFADGAFBDDFFFCDGHHFEDBCHA
HBGFHBBHEFBCEDHDABEHBEDGBAEEEF
HBGABGFEAACHGCHDCCDDBABADBHHEG
EDDCDCGEADGCGEAHAEGACGAGFDGEHD
FDDCDBGAEAADAGDHBBDADBGCGFEEAE
AEFFBDHAFDCAEBBBDCAAEBCHADFCCB
BAEDDFFACFGGFACBEEHBEGCGHBFFHA
GHDDGAHBEDFHAADAFFDCHEFBAGEADA
BHEDDGCACHGDDHFAFBCGGFGEABBDCA
FDBBHGBEDGBGFHBGHHBABCAHADEADD
FACGBFBBDHFEDBGFBFBEDBCFEAEGCE
AHDAEGCHGCBEBCACBHACDFACECDAEC
CCDGFEBACCEHEDHHEHEAEGGDGHAEGG
GDACGAACHFAEHDFACFDEAACFFEEBCC
AHAFGEAEBEAECAHFEFCCCAEAGHDFFE
CHADFHDEBHCCFGCBCGAAADEDCEGFFA
FABCHCFDDHHDCADBDCCBFGBHAECEAE
DDFHFBDBDGEGAFEBGACFECEHGACGFD
HFFDDFHFAAFAABHHABGCFEBDHDGECC
3)
    
seed = 4
D = 100
C = 16
CMJCDCPFBEGCINLGIJNGDNFALODIODINNMIECOFCKDHMOCFPGLFFPKFONPKKBBEADDOKLGMLPCKDGODIHCEFIBLIILPADILKEMAE
JEKJBKNNHDIAMPNPICDDFOHDPMKBFBIBEBJJDKGDPDFFMMGLGIGJCNFDOANNBPNAAAHGKNJHCONJAKDECKPFFLOFNCLIPEIEAJFF
MDLHKOBIBFLLAIIHKFNCEINLNFCOPEJLGIJDGLPIBEEMPLJLJJPAFJNGDIFKFBNJOAFHJNFGCDODOBOIDCMADMJNKGGMCBLOKHLK
IOKGOHNMHCBNIHLFDOOBHCCCKMJLHGNFBKGGIEEAPFIFGAECIHABCDLBPLBOCMDOGHNPGAJLHOAJEMFPBBBBBFDOFBAKPFIGHLNF
EDKGGAHNDCJINNHNBBBJNGABEDPPLJDDKPKONJPNNGLEJNGDHPABEMFEFLBBGFCNIJMNJMFIFBHKMCCMAOLOCPHMEGLPPPOCNAJO
EECKADBFODKIFFPHPOAMKKEPNFHHMMNDDFPHOFDAMGMEGHKJMFLKAJBOFIFNFACGMMFPHFEIAIOEKANEHFGIKLFOAICGBNDBGKCO
MCDFDGMIHHOLKBPDJNLOAEBPCIDLBJFJABOMHECKBBPCLONEAFJLMMKIIHEMEGGNKKKKICNGCIAPJPFCFFOPDEKIEPPPFCKAICBM
DECAGAEEMACLJHMPINJHJHDEGMJHGAPIHJEGAONDIIGPIDEJHKPMBGEKFDHHNDBJJHOJGFIHFDFHIKMAEJKMKCFFGGBKEGPLBDJJ
INOFOLLBMJDBGBNJEABIGBNFCHFCPFDAFIOFFCCBKONPCOPAMALNDFHHPHIFMOKIHAMJNOHOHPJNIKPAEKANBBLFNOBIKGCJNJMO
CLFONFEDLNIILCFHPIBCLHLHNELLCKKCDGKINMGNCNDMCAGINOGFNIHHEOHABMDMFIDKGCBGKICKGGCPABDJAFBPAMDEJGLBLHEI
MIGJFMMHHJPKOCDPKONDDFMCEPOLCDOFPFPCPPGNNLBBGELHCHEBNBOGOEKFKHCMJIKBFAHALFLEJDPBFHCKEMNCGEIGODEJCFBD
NIOHMHCFJIPDINNBFEDACHLGHCNBIPGCPAEONFBOMFCCALOJJGMFOPHHOOEGNGKBHKLDFGOBKBKJAPPLNLNIKMLDEACJAAKKCKGF
HJFDNBKOKGMHBJHKMNJEPJNLOGFLEFNIEBECCMMJBOKMPDCJBOELAAJBINAECEEFPJDAMAEHFMKIOOHCFLBIHGMECFOHMMKIMHGO
DAAJPFFNNFCDBDEJJDHLHJMMGJAPLCFPAFFAJEHBJEGKFIJFHJACPCAKNEPHOJAABIGPIFJJFCLEAEIKMGIADEJDKPHHCOHBNMDM
INEDDDMDNGHKBAMBOAGMMHIAHBFOOMLMJGHJDLLNKCHONKKDNLMCMDBOJDKBLAMFLBCNPFGMAEJGFDMFGNELGDNELGKBMCBEBCFH
HEGBNJDNFEEICNPAJNCFJEFDHBLFFABNMFMKBOCHGDDAHFEOLDNJLMBFCDOABNFDAFLJJKJLHPLJJMPLPCPGDOAGDBCEKFBENOGA
GEFHOLCAPGBICDJFNLNFBEJGODFHIPIOKCODAILJNLFGAIKNJIGDGFCMEAKLJBNCOLDMNOKEHPGACMMODEMEGAKNIKAEEOJMOAEO
JGMHINKJMCLDMIOKCDGNBDKIHFIFCHBEMPDBDINIECOIDGBENFGGLLOEDJGIMFAABPLFGPFPEGIFPDCBCNFMKDFONCPGONOMHMNA
GGDPPLKAPNHGFAJLHIMCJCDHKNKKJAIFDJFEACFKIOENPPBBELIHLMHABAIBPOMKJPKIOLHFPMBAONAMBGMLDLHEGLCFLNHIMANJ
PHJMPNGPBBHNMFBFELNFKLCAIFFCBNGMCPOJCLDGGDPMPFMKPBLGDOIFMEENEKHEFOKDJPGOLIAAOCEBMNLNHDLCLBEILDBMKLCB
MDJEFHCFNGOEODBEFDHMLLGLGGCHENIOHGCAENJPBAIAPEKJJGFFKDIIHBLOGABEPMMEKMKIDIAMCHCAIICHHDPEHGGEGFNIHJLA
BCEFGIDKMNGCEMCMKEJADANEMBOIDGAKGIAMKKLBEBCPAAPOLIGIEJEBCJFFLECPPDNJEJBMHBLKDHCMIDPCCMCNAJLHCIDNAACD
MGDLANLLGIGALFMFPFOPLBBAOEKBCCMGMEIIMCPHCNOIEFJMGGJMBFIOKPIJDJOKDOKAGKIMLCKGGAJKIMEONDNMAJNBBNPNLHFJ
CDJFGDIPHJFMDKCMMKKOGHMCPGJMDCBBKJMOANMALMOGMIKLBOLDNDNKDKICJEEJPKCKEBFAOCNLNFPNKPFLMFBHDCECCMPCFMGN
PPGIMKAFNHGNHJFENMFMLOJLBNDIOCOPKLDKLCGCBONCNPIIPAHNPDEBCAIJJMEPOMHMKHMJNLAAADCAKCHIKNHIECKDAJECBEAH
GDFMLAJMOLBPJLPGBMCNANEBIDNGAHDJCPFHBKOJFHBFNOLCEOKJIHFMFIJKLCMJEEPJDILIMOLOIGHDPHIGIIAJKHNEHFIBHDJM
JPDCEEPJACMPHCHJMBJKBMBHNJOEPBGPAGOIFHHLPHFLDPNLFOAIMIMFCDJHMECEDGIPGFOCFKJEAPJILFEMAPEEJLGKDDKHJPFE
EHGCCKLKLALHPLHNPNLNGNCGMNEEOIAPNKBGCFPAAMHFFFDJFCHKOCFKDOLOBHMNKPNNHPFFNLPJNNIBHGODPMJHMHAJILAHLJIA
AGFNLDKODGGIKMBMILPAOBJDDHIILGAHCCACAMAFBCIKECFMOMIELJKOJKLJKEGBHNMJJNPJGIIEBDJPJCLOIOMGPBBCPDLLMBLA
MDHCIPBPMGFMIPOJBCOMHMNIALKOGEHPKDLKEJONABLFNNNMEGGCDDAHDIPGJBLOLOONHOLGEFAKIAEJGAKHMDJFMEMDNIFFBCFA
MJPNBNLNBDALIJJAFICFDOMNEEKFMNFDIBABOFEPBBFEPPNMNDCPFOEKHLLABOFEGAKIGMEGGGCODNJCJFPOGJAIJHCBJLPOOHBL
PDPCEAJBPHKDOKGAGMPDINHNELKIKCCOJDJBKFHPNLCAFOCGODHMPOPDGEJLOHONIKNHNLPBGLFJADKKIMIJJCIMPNPIDAKHBLJF
IKPLGPOMBCBPKAEIHIMPHHEFHGGLPPILGDHHIOGJAIAIEJNFGNGKBOGKONNLKBJKGHKEDBMLOJJCDNGDNNHOBFMAIGCBCMHLFDNK
NIHBKIKFFGGCEKGFDGKHMHDAMLLHHJODCLBIBKKBLCDNOJBOEGPMOBPLKDCNGDGHABCFHPPLCODCCAPLIMKIFLCKDBPPAGOGFOLG
IEFMEGENDIMKPJMMANAIDOCIALDNIMHNFDNLNEDLANNDABDHGOHKNBNFEKMMBHBAIBFKHMLCOBKDHJGBPBGPFICCJPFEMOJCJFDA
BDHPJBDOEDKBGIHAJFOIBHBCIJPDPNCNFKCOFKIGFDEOMHFHNMFGIFGMIHMBKKPFFCABKKJEPGOAPCFPPKHOMDNCOGADIONOLCJG
HIIKCNNACKBHGIALNDPFBEDABEPJCFMOHPHCEKGKCMEICJGBDJAKCNBMHEBHKKJDMAAKNMDHJBGOFKADIPPIIMADOAFBGBDHPPDO
BLBJLEEKHCCHOPELNADPOPDIKOGPPAFMMAHDOCKFKAFNGAHMKGLLOABPNMDHIJAEBLPBAMHGICBKLIBIFIOBDIKMBKLDGKEGICMF
EJIBCDPFFNGHCGEONKAFMLPADCCPIDCDJBEEHHLGMKADIIDEOGHIPJJIPBMLAHOMLFIODGOEBOJBKKONPCJCPIFELLIDEGOJCAKJ
NMFHBONBBHPCNBIGPGEGOEKPNNIOEDIIFNEKFFEBKIACMAFEBPODMBHJFKBAEKDPOBLLNJOJIFGFOAJEHHKNBABLAIMCPLHBKJEE
EIHDHBMDDFEAFIOOCJDFJHKHEBPJFNNMOGJPGKAOMMHDKJFGCHLGNGDLHBBLEKCLECKLOBBLGGGCLAGGKMFINNIDFIPHFHCOCBFG
INBPPOHLGKNHALMBCNPPBLOIGABNPANBDICACJAHDCPBMIIFHIJMOECIMEJDNCKNAGKFKCBPOBMMAJAMGPJPFKCHGBMGKJFFKIKF
CEIEDKONNONCOHNEMBCGBOGOBDKEIMBNACNDELOIKJMFOCCMLJHLDIGHMLEHOPGGBMGEAAOMDADCNMNJCEPOFNKDLKPMALMPNHGJ
EPHPIBAKFNMBBNCKBHFCFNPPFCAPGAPGMFLMDCNGJLLALCHJGLDHMHIHGKIFFLJMLINICFEJOCDNDGKIAIDKIDBKAMGEGKJNGNPJ
PCHLEIDJPNEOBBEMAFOCGAHLEIECLCEAKBBFPMJLIDDBMHPBHNCOAPDHIIAGBOPOBIBEDAMDEKIGLFAGPGBCDKJNOHCKLLCNGNMK
EBHINCDHDNDPKHKIAMGPHPACMABBJMGNOPLMPAJCHFIOIDBGBCFCEIOFBPJHIKMABIDLKNGFPPCEHEKAJJANNKKCKHIBAEKODMIK
LHKPHNIOMJDLHIOLALHDDOKIMCANAHIEHALMBCCCKBNDPGDAENPHLIOCIBEOCFCOBEDLNDAIICEHOMGBPAKDDBNDCKMBMDDHKDHG
PDBOKBBHINAIENEKOGMEIDNLLBELDBOKJDJEHFLKLPKPGGOMHMLAIEBHCOKFAGPFKBNEJAONIIPGBIEICBOMGFMONAOJBDMFLHAE
OMFBJKNCFDBFFCKMEOMGOCDHADLHDFBJGAAJNLLNLEFKOCEHAOCFABKGIMCHKKKCOAJNDODFMAPAMKLCCBBKEANINKHAMHPGDPIA
JEDPHOPKODAAOMIPACIKMEHJOIAJPNAHMGEFCLBPPOEBLDKFJNCLFLFJNEBKEJPLJLAODCNDKNNIBJMMLJMPIJLMFGOMOPOMIIND
HEMIPPEDDICAIHDJMBLOKALAOKDNEJMNBJJILLJNMPINNDOFOMKGBEFGFAFBOAIOLKBOOLLHMBDOFAGPNBHFEGBFIFFAAOMOIFDM
HGFLPIMJNKIDIOGKJKJOHOFCEKLDCGFJKMLAOFLPKKKKODGIHIOCCNCKBKKCGDPPBDCPEPGNBFFLFBBCKJDGJAPFBBMELMGHPEJN
FELOJNAICCHODPNNDEGGFPFDAGNEDPIDMCPDFDFLLCKMLNLCJJHFMPIAGDGHPFHCKPAKOJDAPIJEMFDGAKKCLENLLMKDOEOIPMKI
AGCHJHMGCFMMBABCFHGHFJEKKAOGDNHAGHFGDENOLBDANEHMONGBAHGDANELAJIKLBCNDJBLPDEINMFBKAHACBGHJLILDCBHHELM
GKFEDDEJFPLEOHNEIKJENLNBPCCBBKNEKKOPFLAMHPNNBIPBMKCACAOIKGFFMPAGOPKIHIPNBFKDGAJNOJINHBJDDKHNEENFALFE
NPNBICCDLBKFNKNJGIBCHDHBHEEIINLKKMLENHBIPCJEOGGKIPFPPENNAFDKCFCKFGNLJBJDLBMAJENBJHMOGAOHGMFCOBCHJPHC
PFMGGBBEHNMBJDBFLAIIGNGKGNADJBCGMGGFGIGEHGIOCKBCLNCOLDCELPFHKELJNMIJFMOABNEMJBMMMFHJABGAMHJPCGOEFJAO
IHCKMBGCKNCBEDIAEELIFKIFOOGCNLLAGMAPBAPJMBAIIEJLPKABPDNNNBDAFAFCPKOKNAKGDBCCGMECLMDEANFIIGCBJHFBDCCG
DLLELBBHBOJCLJBEIIHJKCJHNNIFLNCNDPFMDDJECKDONJLPFAONFCNBCFFJJHEBJIIBFKGBCJCEACLGGPMAJHHPHOCHKPGPMEJL
MKAJBCDECNJLBHAIGKGDNPPHMNMLPPJABHBHMGEDNLADNBMCCGFBKBFEOFIJNMFAMPNFNCKKKGLHHBGPDENHANPDJFJFAMFPFBML
IPHLHOELMKJBDIJNNNAGEKNNMOHPLCBKHPPNPGGIPCDCMLLLLFFEEFGEEEDDILEMKJPIMIGEMEHNOEHLHNPEHGIIBLDENOONHJNG
LILIILCEJLJENPLPNFNNCBKOIBHOKHFNGNFEHFLCDLNCECFKCKGLGHNIKCKDLEHEGEBEFDIKJFMMOLJHLLJFJPCPHJNLEOJKBBPP
IPOHIDGMJAGDACDACPBFJIFOIOLMOGJLBAINHFDDELIFJGEMHJJHIOINNOKAHEDGELLNBAHBJGDBDBBNLAPJPAENALCFFKDMEGMO
NBELCCMBNGGKHPHOFMNHJLCIIBGMJMOILIAPOGLNLAPGLDOCBAABFJMEJBABDBIKKFFCNFMAKEFLMIHCGBCJEPPEGEOEJMILNBNC
LNAMNFGALKCOFCFMPMOHGBBMBJGJLFLONKKMJJEOPACJBKBPFKJENJEIHILMJPHAMNEJHJAINLHFNHEGLIHFLALCGMHLIGFIJNNP
PHHDCFBLEEMEPGMGBOMFCAOJBHDMLJKEOACIAMIHIKMNHDJLEPFFMDBLODNJNCKJBKMCNLMKJPHBJHMBDEDOJNMMIMMPABAIHPHO
GIIPOFIJGBHDEMFGINGACPABLCJKBOIDIDIJFMMHJHICMODEBEFGCKFCFHMNOLAMILFDIIDOACIPGAIKOONNOKJPCEHOOHMLIGBC
BIOCBABFMHFOLAPGCPJEFFMLDMLLCELPBOCAIEMOGGDPIFGJCHHAONAGFAEKFDEBFFDLPFOAFIKPADJCIEAHKCMMJAECPPGKFDDF
KGKNPFGOIKBFGNNBMJEKNAAGICEGDJILJBEGALEAONACCLGDJMLBAHHGHHEMCBLNEJLMOIDJOPMCLCBENPDGJMCNIHNLNNPPEBHI
MDJJCLPJGMNDPCMMJHAIPCMNHGOLOPIKNEBGKOBCJBJPIOFBAENNDPBNCOIHCHNFOBMPMIHPFIMIANCDLMCHPLALGEANAPOGFJDL
AKNABGDCJLAOOJGNKLDHNGCDJMADPFFCPEHIMNGPHOHLHHKCOINPOAOKOBJOAGNDDHLJIINAODGAOMLMBJEGGDIJIDADIPLDAJAE
LKJOHEGAHEIHBENHCHDOCGOHAAMNOBKMAFDLEAMBKLLLJEAACFELPLLOEMDONBINDFONEHADLLIIKCIIBLANDGNGPOOJOGIIDDPN
FJMPIIPLOEJEFPPAGLFJGFCMGFBIDGJJGJOOEIEEJFDGNAJJJLOPBEOKBEDPAJFGLKLADECENKGKFBILDBOEOIAGNDLFLIFEJHBP
IEGJFNDIHPGEMEFHLPJMIIDDLNFFMCABDKMANALMDGIOHDOBEJKJDKMJCCIGFFFKPAFJNLJDKFGBIALIEHPFPAMJMNDDABJOIKGI
EFFLBCONJIDPJDCGCIFMOKPNGIHGMBJHBIDOGJHMKGPABNEAAHLDKPOAKLDCAMKBDCNDFPEMAEPBLGIMIKMODBIBGNFJJPKLLCPG
ANDEIJLHKFJJMCKDNPKJBMKGCOBPHEJGKNELOPNEMNPDCANMLJDKPGPDGCGMHLDCPJHPLJGHGDOKBKBJFKBOKDOGKEEFFPDJHCNH
HLEDIAPPFGODEBPNDBCDLBIKJCOIOBOOKGJDKMDMHAMCGOGDDGMJAADEGLJMFGOJDOPFMEDOJJBJBOJLLEPDNKLABLKBCMPAPBFD
KFEOOAGFBEPNNNFINCAPFNCHGOEJDHKGMFOLKBEMIJAGNGHFNIDJOIEDEDPCFCBPCFGLBPLBCOHDLHIFBHECIMIBPPPJIJKAOMOB
AFKLEEPLLNEBOPOJNABDFBMFCOAPILIFJOHIJCNANAMJGPIKMOPCEGFHBGOBIJIBEOMIIJIDJCLHJBBMMNBOKAMIIGPGMKOBFPLG
KFKACOOLBKKMLMOFHDGLJKMAHBHLKMDOPOOILAEDOENEODCPNJFKLIILFJAKFOKNOKKLFAGKKCKPFMHACJFAMIEMGNJNNDFCEFMN
JLELPPKJEIGHFHHDGHJHFHKMDBMKAKJGCAOIGNMJBKIAFNAFIDFGKJGAKIOCDOJOGHJEKOFFJLGJEKKKBLPAPDNIAILKHDKEAPCN
IPIAAMLNGKFGGPDEABBAJCOFJNOPGHIFKHFCPJDMKAOJKDBBHBLIBDBMHHHBOLIBECJPKGDAFJPIJHIMEBKEAGJMOEPEPKGKPIKP
MCLEHAHIGFGHIPNLAMBIPMOMDEFNOMJFCPPPMLHMAHBIPNOLPDIEPOPFGGMGKHNAKLMMEOHEJCMCPCGIMLLKMBJFODELHOJDFBCD
HNAHALJHGDNPFDKOFHJKPMJFMBDDLLAGPEEHBELBFFLCEFGGEBKOKLBPDHOBJDLLNLGIJGMOHKBIOCFMEHCOGJJJLGNGJAEMJEOF
FMIDLDMEINEPDLHGIPCHIOACJJLCEFGGIPKCDHBCPJJLAAJKMEKCBEEMPFJIBELMNMNHPDJKKFDFMMCJAFGGNEJBBHKCHDOCMKBJ
JNHAMNAAAELLAOPIOABMGNKPEPINOIKNDJDPFDBPLFMNECAIGPJDHBFDLAOPIOLNBKNDGAIPMDGMDHDGENNDJJGBHJNLJABNJGOI
NLPNDPBMIFINGKCOOHFHLIIINBDFOANLLAHCLOGKCKKPHEKGMFAHEKOJJIOCIMMCBOHOGPACDGHJEOOLNIBIFNPMAOFOMDAFPJHM
IDPKBFONJFLOACGINNEDABKDOHDNOBEMPEKCGDDGBDNLIKDPJONBBNGAJFDIBJEDGCGJLEKFPNNMPLHDOAJDNKOBKDGFFFNENMBK
PPBKOGGKNEKAMLBPAFPOOLFMFDIKJCFPLDMNJECOJLOFCEJMPCIIDAMBHEILIFOPMDGHMHDJBNMMAGEEIBFAPKHALPHIFFEOMJPE
BGKBPEGMKCNBEHJJDDANDBFNFKGHHPOIHEIHPKMKACLINMJHOALFLFLOKPCJNACHLJFDHDHMJABLNKPCEEMJPDBEBJEILNJCCLFM
FNFDBAJPOHGMIMFKOICOJGLFNCLHIPMBFBMGPFKDAPHHPHHALLJPICDKKEOCJACAKNIPGMMAEIBMJHFKKMLLFDJNHDKHOCAKFHJB
OIDGLPHPGKJOBFACBFJKFEAHIOMJKKLFKMKDFNDIKOINDFOIJKJHCIMHFMJNFIKDMOFMKGCMKJFOJHFHDBGGDBNCDMOGHPLDJLIL
JKEDEPMKGHDLGPLBFDJFEFIDKCNICOODHBDABDKGDFJGGBIKKGLBLENAJECOFOOJFHHKKMBFPECICFKAEOMOBNMKOABCBGPBDPLM
KFKKKMHDFMODECAAOLLBILMOMPKAKLPBAJJOIMKOEIDHMIBDLFEELFMKCIJFFFJGKCKFDFGOHGDGPPGDMONANLMPBBEGLECBDFJI
JCDAPDHALKJJPAMFLLDJAHDAIPLODELHNNGINNLKMEHHBHDFEBPKJBMNEKMEPLEALGDEIGIBAICMKNGPLGKIIJJFIHMFLFLIKJAE
PLGDFDBEFALKGAFLBFJDNMOFKGAKAJAPHBECBBIEOAJHNAMJBFAICDLINEGPDDMPFPGABLDBKGEGHHIKJDJHEDGMFGDAENGBFIEJ
NJOFNINIHCHALHNDDMLHLNKDPABIPMOPLENJJLNKDCJLHPPIPKGGBOLDLIAENJMBHIJANOGOAMJHKKFBKFLNFBKABFLOCMCEMIGH
CAKENLNNKPMEGPMDPHOPJECIEIKCFPCNDBOCDOLJDKHGMLHLLEKJNJADKANDGPCGGMDCDHGKMLPAIMFHDHOGGHLMKGPEMCGKEHPP
KMLAHPJFBJHJMGFPILEONEMKJLIANGCFLCPAFEKPDDCEONKNAKBDPBDBIBJNGFHPMAGOHHAAAOAIAFDODBOEPFLPALPDFAACLALL
NNAFOINDOJLFNBHCKAMKNPNNHIGLPKBKDKBPGHCBENGLEPCMJAFCJIPDDHDLGNCJBCNMBNNEDIBGOBHAGFNLEIGJMELLFLGOABAB
4)
    
seed = 5
D = 83
C = 14
FLMNFEIKCLEEGDKCNCMCGGDBLHFJGCIBAAJMKNCEGJJJJEFHGJNDFBNNKKEGJDNIIHFGIHEHKDFLDBNHEGA
LKGJDKKMAINICJLKGHHBCLNGBDCLAEINIMAKLMBDMFKBEKFJKIBJMCCLBHNDFGGGNMNIFDCLFIHNGFFBHIE
MANBCCABBJDFANABNJGNHBGCNMJMEJEDCKKKICBKCEIGBMCJCECIEGINHMHBIMIGGFHLIAIKHGCAGKFHFHA
CMIALDLGMABIKBMMBFDDKCCCHBFJFFCDHNLAGDEMFMBNBFBMLHLHBMFJEANHKJKHNENJEKDDKGCELKHHLKB
NBAAEEELCDCBGLMFNMCALGDHDKHLHBKCCEIJIJJNFDAJECBJJLMLLMBCDLCCNFBCDDJFNELDBBMKCEEBLMC
LIJIEANGLILGDGHMMEFDAKADALAINJJMJABCNIDKADKBGBDBNIAHLCLLLALAAMMBDKFJDADHKENDHAGMKKM
BLBLFCKBGEEJCEDDDAKBALHCEGCKAJIMIADEAIAJBGJBFMEEMMHEKIGNIMFHLBEAJEKBLKKLMLILDHBIEHK
LCMKMHANHHGAEFELMFHLECGJJHHCJFAMAKIDJDEDLFBADACNDCHCGLJILNMGKHNMKBGBNEMAEFBCGJJCHMK
KAGIDNECFDKCALHLBFBHNBIENHLENBDDKJBNNDJNMKHAMIHGAKLEHFBAAKNJBBJJJDLHCBCBFDNBMKHECLA
JDHAALDMINGEGNKEJHHIMHEFJBABNJAJCFMLJEGAFCAKFHABKKALCIKEDCFBFGGCLDEJFEJDDGIFCBECCFN
MKEEEAAECIJMCNLFNNDBGHLKMBDCAEELMNJECDKCEEDCGKKLANFNKKDBMIANEGKAFNNHIINLGFGFJEHLLCL
FLKGLBCBEGNFEKHDJIDJLJMMCNCEABBDEJMFKGHJFCANJFHNGGIEIMMEKHGLBDJKJENNEIHKDEJMIDLCIAD
FGEBKFNDICMDKJAHEJANCJHANNMGGKEEHBCJJDKHALFKJMLNABCKHMMCACEEILICADNFAKEHJHMNGANMIHK
FMKNLALAGCCJFGGBIJBHJJKEJMGHMJMDAJGKKBCHKKKIDJLLEJJHBLBDLKGBJANCJGKKHJKFLDHIBKENHNC
ENILAHNJHCDCGEBLMAGELIHBEICGEKIGFJFJBKAGBJNFHIDKADGGFMNCBNGGCMFDIJBLDHAKMJMNKDGGANA
IGJHLMNGKKBKJMMHAEEAKLKHLEMHEBNKDMIAAIBAMNJMKIJAJCEBNKLJNJKKKDNCCBCKDNIHJDJJFJIMMBK
FFHJNJKLLIDCFFEDCDJEINBCLBEIGFMIEJAGAHFKDKLGEIECHAMFMIJGKHIEMJNLJBFAEDLKGGCNECJEDLI
GMDMMCLAEFAKECBNCMDEMKIGMEFEKBMJILIEACNDMFJHNHADGGKLDHMAHGHNNFLHFKAFHMGDILHMCAHNBJJ
MEGCFEEDIBEILEJADKIDJEKMIACKBLBIGJIIGEFMLBEKAMFLMIIICBAABMGBBGAHAFFKMICKKAGKEDMAGNK
CHBKCDKJMIBGHEFIAAFANKGFIFDEJHHJLLEHEADFEBFDNJHAANCJIJGLFHLLGNFJDMALGBGKMFKLBHBHANG
KDAGNKHCCKDEHEAMADAJMHNMMCDBMADJIECEHCIHECJMHANEKIDBFGJLKDNIFDFIHLEDLHNLFJIICBDDLFD
NKAIHLAGIEDJINLMDNFFEINKECAAHIADMFCKLLMHICFFLEKGNHKKICECCJDBEEKCNKFNFJDMKHCFGBIKEKH
KCDAHIHKKMADJLACKHDGDKENGACCBNGAMGABFIMAJKBGJFLNMFDLGCCMBGKJCEKHLBBEFIJEMBAIEKIJGDG
AHBMCFFCGKHFCEFIAKBDLIMKBMKHHNBJBAKLBFICNFFIBLDHENJIECKEEDCENIDHDCCGAAIFNLIBNLHJBLJ
DBGAGNDNNJNFICGMKKJLHAILFDEKBFLCNKGHGKJBDKDINCADNMJNJMMAACDNKHAJJCIMMIALHNLEAKKNJAA
GKCCNFLJDIECENKKHEEBHLKDJMKMGKEHLNGJFDKLBCMJIFBMKJCMLLADNLCNNNEKGGLJIEBNJGHHAELKGNJ
NBJNHIDMHBLJHBIENIJAHNDCNGFMMHBNDKCIIJKMHBEMNMDKBNBHKGEKMFEHKGKFJECIKBEIAMDKNHKIHHD
BLIBLALMFBMIFHGAHENNGGDHIIKCEEFHCLBIDBEKGLFNFLHJFJGIJBFCNAHKCCGMEFDKMMNBAGNNCABNNBE
ENBFBIGGBNNDFKIFAABIKDNCLGMCECIKBLIDCCNKNECNNIGAFEKGCHEGBECMEGLCKKDFIJDMGKIFCMDDDAC
NLNDIJFCHEKEADDCDNBFEDKLIEBFCIGJNNKBFIBGCNIGNKBEJLFEJMMAAIAFHHMELGBGLIDFDDDCNNGEBGD
JMLDANFIFJBMLFAEJHECCINNMGNKELAKJJFIJKKAKNNBHEJCKIENDJEIBNGEGLMBAHKIGCCAKABGEIKFKMI
KHEKAANMLMLJLHCJCHLKJNLILFAKDEIANGFCIDIMMAKNBBJMEDDMGEBGMAHMHFDEBABHLHLJLLAELDMJMAN
LDCDHJHHGHHFEJACGMHEEHIECGLKLDIMGKFJFHGLHFMKGFHEDCHFMKIDNMMEAEBLDCDNGFDKJFAKIGDCJDE
EJKCFANHNCBKKNNACMKFJGBIKDMEHNJGMLDAGBAIADNDBCEFMFIJNGDBLJMFEBKCDNEMGLDBMBMJMMLKGAK
NALLKILFBJFFBFHEJJNLCIKNMJGFELBFBNBDHIIBGAGIJLBIJBFKADLDHDMGMCKNDIKALHFFDCCJJCIIGEL
ADIICGCNHAKGKDFAIGCMHLBDGJBHKHFGICLBAGKJLECJECIHGNCNDDIJECCJDLAJAHLDADIECJEEKKCJEFB
BFMKFKLBMGLFFBECEAKMJLKMIECBEJBEKLEMIJGIEEGCCNBAJCJKBNFCNDDNMGLHMHLGBIBLJEHBCKAIMHJ
CMMMBEDKIHGAIDKIFBMFFGCNMBKKEAIMJKEDMCGABNCBNNJMCCEMELIBIHDNHGNBBBFLBDFCAMAGFAHJELE
EJGBAINBLHLBKHALNDFGKDJINMLGCBMMBJDBHINNHCIEKJIJGLIMCFDCJIMCIAHCHICIAKFGJEILFJNLJJL
BEBJKIFMMEIFDHFKCDECJECANLHMNJFMMDICCGJFKCKEJCKDJHECBJBHAEMCLABACAIFGKKHMAFBKKBDJMF
GHJDHCCFGBBNBBMMHCHANEKEKLLGNGLGGENHFKAKDFBGGMNDJALBHFIGJDGCCEMHGMEFBFGGHGFNFNDCBHI
HGNJLBGLADDBMFBDJMKBNBDIKHCHNDBKBHGCNGHFNIBLEJIGCFEAKMABDHEEBHFKHENAIGBDIJMNIFGKDDI
EBDFBMCJLJKEIKNFLGBHADFIBCFFGHAFKEIKIKDHEKDIBFGDMLDKBCHHFIAGKCIMFKNKKMBKNCJAJJJMJCI
JHDALBCLLJEJFBJIHBICDEACAFILEDALKJLMILDFFCHFLHBCDFGGHLFGDBFIJAGMNLIIFKCFFBCALHHNCAJ
DKGAKEFEFLNBBGHDKDBIIDNMCACCEBMIJEBIDGANBCAGKHGFGCMGDIBABIBLIABHLDKJJKJGDLAKAEJGLMF
HCLGECLNKNNNJNDGLJDNKKNEGNMKJMCKHFGGCKNLNAHJBCLHMDMNIFBADHAJEGBABDGLAGKJGDDJCFCJKIF
CMEEMJDLECBLAGGKNNDILJAKJFDJLAFKGHCNHAADELFGMMGNFDJAJIFNMFHLBKFKILEDCKDHLGCFHMEMCCF
HKFLHIBLJEAIKLMMLBMFGEKJEABLHKKBDJGMJAEKFBBHDIGMLDGLGCILHAALIEFHJCDCBMEJFDEJHMELELK
EJAFGKAGMLAJLHJGLDBMCLDDNAHMALMABLGBFFFJBLCAIJKNCIKEDMKJDHIIBALIKGMAHMHMIGBEBCENGCK
KAFMMABICDFCBMMIIANKIDNIBIBFADKNIBGHBGNLECDEDFFIFIJFGGJAACCLFAIMALFJLHCCGIGAEAJBNCJ
JEENMEBHACFDAMJJHBGNBBEDBJHJFAKHEHILLFJKMMKFEKHCJKBMEDBKEAIGMKEHCDDHKHJDLCHGJENIHMH
KFLDKLJDKDDKMNCNCGKLIGMEKCEDDNBCDDMAHJNCEEEGKMLAMKCECMHBNGCAKDMFKHKNCHBNJFHAJNGEBNM
CCGFEEIHMAANNJJELFNFDEJECBKKNNDHDLMNCABMAGGFJEBAEICIGNCEHDKLCGCCFHBKGCJEFAFNHMEDCDM
HGGKIIHBKEEBEGNAICAKNIFINANGNDNEHMKDKMAECCNAEEMHHNIMILJGJLAHLFFHLICAEABLFNEJKAFHHIE
FBDGMGBGBNFABCEFMNGHCACMLHABFHMMFGBBFMMALFJNKKFIFFNHFGNNDHCMCMHDHENDJNHNHLKMDEKLIBI
FKFKNIADEFNCCKIGGBBCBJBKGDMCFBCMEHNEEMDFDAAGMGEFEMAEGAMIFBMJBMMDDCCHMINHAHMGIDFKNFC
CGFHEBKGCBGJBCGBGAICJMMDAGMFEKLBBEEMCABKACFALECMDCMIDCEEKFIDMLHJDIJBKDADKLHEKMJDGCK
KJNLEJMLFBGLFAIANIFHJHFNBGBAJBJCCCKCJEJBGGKCEGKBGBGEHMNGINFGINEGIEDKIFMAIHAHIJKFBJJ
ADKAHDDKDKNLCFCMFKJHCNJGCGBFIBLFFFAAHGMBHJKAADCHDECAIILBKHFFKHJLMAEEGLNNGGEFLEMFGBB
LGGLCCBMHJLMCIFCIBEKCGKAFLFBAFEKAFJHDEBHJNHJCDFMHMMNLKKAANIBCBBCLGGEELINLHJDDCGLBDN
JLGCAIEHAMJEHEJCFLANEDNIHIMNJLAEGLGEADJGJGCIEELAMMJMKAJGFCDMEIJIMAJKFKFBCLDFJBJBNMF
DDLLLHFHLHEGAFGCFLDBIIDGBMBFCCKLHLIJCKIMBEIEDHABGEGHCCMDFGGKDJFJAMLJABGDMDHNFMIFEMD
IEIGELLACJMNDFEDGLJCEILIFGCKDGJGAIALJCALLJLDMCNHFHLCBFJIADNHMJNIJMCJJKIDFFFDIEFKDLJ
CEAGEBIEIHLNGNAEDDELGNGCCCJMBLEGDLLKJKMANCLDEHGKKBCKMLIKJBJLLBDAMLGNCJHNJGKAAGMGMJG
DBIKMJHKIEKIMHBGDAFCAKBDHDIFHNCIIJGJJAKAHNDGACMFHBJBDCJICHINCGHKFNMBCCJGKCGHMFDKDDL
NKDAFDLDFFEJNCKDHHEFLJILMHCIGBLGBMNJBDMCCLCFCALJFMLACIABDAFINENDBJJEMEIGDEKAHAFNNEB
MIEMDLIIGMHEBGMEBEIMIIJKNKFDNJBGKDJAGBKFBNAJFAMLDBNKJDAFDMLKJFHCIDNMFEFAHBJNKGGCDDN
FEAGJFDCANILGKKHGKLIMGCLKHFBBEANGLKEGJEEJLNBDACFLAFGINNKCCKBABIAKJDGEJBBBDBBFCEBHNC
LBAKFNHHDCBBMDGDNDGIAEJBNKEDHGAJLMDBAIENKBGKDIIGBJNJAFNMIFCFDEDANBGAILANMAELKFACKHI
NKLNMAJCIIHALALDHLAJMAGHLDLMNIGKNLMMAGHLAEDJIHIINEFCMCLMAKMJFBLGIBNHLFHBDIDIAGNBLKA
ABDKNCMJBHNEJJCHMAMLKLNFDMIHLDCNDLKEMFDEEMIIENJBFIEGEBJICIGBCJFHJMJDADABGGAEKMHJCDE
MDBNHMBAIFKLEINECILGJJNCLIHLJKNBLMCHHIMDALBKHAFJINJBBDNCHCMKMBIFLENHKMMDGGLCHJIIDCG
JBAAFIFJFBLBDIAIEIFIDLLBBJGIAKDAIAFFNBINNJEAHIBNKIJDLMNNLGNLCJKADIBJGBAFLGGDBCCAEIG
LNLIAGIFCCDGKCCGKNBMKCGIHDNLDLHFBKLGBCBKHBKCDDBCHMGBNCFCADHGGNNGAENCJDCHAFKNLEIAHND
MKHHIIBCDGAMJCBCDMIEHCFGEFGAHHEAMNGFLJNINGMAKAGHKGMEGMDLNDEBBDNEMHCCCMAFMMLAKGLMIHL
ICGCFCNHCEAHGIBBJCIBGJNIEIBMKEBMANHFMLNBLKBJLEKHKBMGCFHAJFNLJIGNNENLALFFGKHFILGDFNK
DHGGMJMBHBEBNFLKLHMELKGFNHLEHJKJJLNIHDDNLKEDNMNIDINLMAIIICAJDKBLFHKCBHJCMGLFJEMJLHF
FEJAFKIGIMKFJCJGJDHCIJMFDCLJLKJMJKACNFBBNKCHGBABCGFJKNEELGELAHDCMLANNJEJKFIKIDCADMM
LCDANBEDGKLAEEIFIKBCGLDFFMBEBJLMCKEJCHKJDMHLCCJMDDILHCIIEELCDGNEFFBDAKBNHANAHEHKAND
MCJFLCCFJCNLIKNMNFAFCNIDEHKMLNEHFIABBHHCEMFMHLDLCEDEHHFBGGAHGKADFFLEFBAFBIFILCMIGHN
BEEAEJMHIDFMHNIBALELMIMEBGENKMMGHCGLKNGCHGALLDENCCFLDEIKAEALBAIDKFGEJDGBIJBGHHBNBEN
GKGCHBMIGFJLJNKIMJNBFGGFHBFFANIGMAIDKENKBNAIEDHEMHKAIHJCKGDMIEEHHLEMGJJFBFGIAJGNCCH
LIJCHHECMEIDDDFCBBDBBJAJNKCEJBMELGFMCGNCGALDELEBBAGBNLCNILKCNFNACHJCBACMBLIKKCNLADJ

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)2010, TopCoder, Inc. All rights reserved.