hack

MasarykUniversity

ˇarikUniversityinKoˇPavolJozefSaf´sice

acmcz

CharlesUniversityinPragueSlovakUniversityofTechnology

ˇUniversityofZilina

CTUOpenContest2010

HackaroundtheLock

hack.c,hack.C,hack.java,hack.p

ForyourtraveltotheACM-ICPCWorldFinalsinEgypt,youhaveboughtabrandnewluggage.

TheluggagehasanumericlockcomposedofKwheelswithdigits0...9oneachofthem.EachcombinationofthevaluesonthewheelscanberepresentedasaK-digitnumber(possiblywithleadingzerosthatcountasdigits).Onlyonecombinationopenstheluggage.

Asalittlebitparanoidprogrammer,youwroteasophisticatedrandomnumbergeneratortochoosethesecretnumberandyoucanfeelsafenowbecausenobodywilleverbeabletoguessiteasily.

Unfortunately,afterarrivingtothehotel,yourealize“nobody”doesalsoincludeyou.Sadstory,isn’tit?Insteadofstartingtofreneticallyrotatethewheelstryingtofindtherightcombination,youdecidedtowriteanotherprogramthatwillhelpyou.Givenaninitialnumericcombination,theprogramshouldfindfastestwaytotryallotherpossiblecombinations—asweallknow,thecorrectcombinationwillalwaysbetheonewetryattheverylast.

Itispossibletorotateonewheelatatimeonly.Afterchangingthedigitbyone,youcancheckifthecombinationiscorrect.Youalsoknowthattheinitialcombinationisnotcorrect(otherwise,youwouldn’tneedthewholethingatall,wouldyou?).So,theoveralltimeneededtoopentheluggageisproportionaltothenumberofsteps,eachstepcorrespondingtotherotationofsomewheelbyone.Tomakethethingsworse,itisimpossibletoturnawheeldirectlyfrom0to9orviceversa—youneed9stepsinstead.

InputSpecification

Theinputcontainsseveralinstances;inputofeachinstanceisalinewithasingledecimalnumberN,whichistheinitialcombination.Thenumbermayhaveleadingzeros,whicharecountedintoitsnumberofdigitsK,1≤K≤7.Forexample,“007”isconsideredtobea3-digitnumber.Thelastinstanceisfollowedbyalinecontaining“-1”.

OutputSpecification

Foreachinstance,printtwolines:thefirstonecontainingtheminimumpossiblenumberofstepsS.ThesecondlinemustcontainasequenceofSK-digitnumbers.EverypossibleK-digitnumber(exceptfortheinitialone)mustappearatleastonceinthesequenceandeachtwoconsecutivenumbersmustdifferinexactlyonedigitbyexactlyone(inthedigitvalue).

SampleInput

500-1

OutputforSampleInput

13

678987654321099

1020304050607080909181716151413121110102122232425262728292938373635343332313041424344454647484949585756555453525150616263646566676869697877767574737271708182838485868788898998979695949392919

03050709

Thelastlineofthesampleoutputaboveiscutintoseverallinestofitintothepagewidth,butitshouldbeasinglelineintherealoutput.