ACM试题Word格式.docx

ACM试题Word格式.docx

《ACM试题Word格式.docx》由会员分享，可在线阅读，更多相关《ACM试题Word格式.docx（12页珍藏版）》请在冰点文库上搜索。

167

ProblemDescription

Anentropyencoderisadataencodingmethodthatachieveslosslessdatacompressionbyencodingamessagewith“wasted”or“extra”informationremoved.Inotherwords,entropyencodingremovesinformationthatwasnotnecessaryinthefirstplacetoaccuratelyencodethemessage.Ahighdegreeofentropyimpliesamessagewithagreatdealofwastedinformation;

englishtextencodedinASCIIisanexampleofamessagetypethathasveryhighentropy.Alreadycompressedmessages,suchasJPEGgraphicsorZIParchives,haveverylittleentropyanddonotbenefitfromfurtherattemptsatentropyencoding.

EnglishtextencodedinASCIIhasahighdegreeofentropybecauseallcharactersareencodedusingthesamenumberofbits,eight.ItisaknownfactthatthelettersE,L,N,R,SandToccurataconsiderablyhigherfrequencythandomostotherlettersinenglishtext.Ifawaycouldbefoundtoencodejusttheseletterswithfourbits,thenthenewencodingwouldbesmaller,wouldcontainalltheoriginalinformation,andwouldhavelessentropy.ASCIIusesafixednumberofbitsforareason,however:

it’seasy,sinceoneisalwaysdealingwithafixednumberofbitstorepresenteachpossibleglyphorcharacter.Howwouldanencodingschemethatusedfourbitsfortheabovelettersbeabletodistinguishbetweenthefour-bitcodesandeight-bitcodes?

Thisseeminglydifficultproblemissolvedusingwhatisknownasa“prefix-freevariable-length”encoding.

Insuchanencoding,anynumberofbitscanbeusedtorepresentanyglyph,andglyphsnotpresentinthemessagearesimplynotencoded.However,inordertobeabletorecovertheinformation,nobitpatternthatencodesaglyphisallowedtobetheprefixofanyotherencodingbitpattern.Thisallowstheencodedbitstreamtobereadbitbybit,andwheneverasetofbitsisencounteredthatrepresentsaglyph,thatglyphcanbedecoded.Iftheprefix-freeconstraintwasnotenforced,thensuchadecodingwouldbeimpossible.

Considerthetext“AAAAABCD”.UsingASCII,encodingthiswouldrequire64bits.If,instead,weencode“A”withthebitpattern“00”,“B”with“01”,“C”with“10”,and“D”with“11”thenwecanencodethistextinonly16bits;

theresultingbitpatternwouldbe“0000000000011011”.Thisisstillafixed-lengthencoding,however;

we’reusingtwobitsperglyphinsteadofeight.Sincetheglyph“A”occurswithgreaterfrequency,couldwedobetterbyencodingitwithfewerbits?

Infactwecan,butinordertomaintainaprefix-freeencoding,someoftheotherbitpatternswillbecomelongerthantwobits.Anoptimalencodingistoencode“A”with“0”,“B”with“10”,“C”with“110”,and“D”with“111”.（Thisisclearlynottheonlyoptimalencoding,asitisobviousthattheencodingsforB,CandDcouldbeinterchangedfreelyforanygivenencodingwithoutincreasingthesizeofthefinalencodedmessage.）Usingthisencoding,themessageencodesinonly13bitsto“0000010110111”,acompressionratioof4.9to1（thatis,eachbitinthefinalencodedmessagerepresentsasmuchinformationasdid4.9bitsintheoriginalencoding）.Readthroughthisbitpatternfromlefttorightandyou’llseethattheprefix-freeencodingmakesitsimpletodecodethisintotheoriginaltexteventhoughthecodeshavevaryingbitlengths.

Asasecondexample,considerthetext“THECATINTHEHAT”.Inthistext,theletter“T”andthespacecharacterbothoccurwiththehighestfrequency,sotheywillclearlyhavetheshortestencodingbitpatternsinanoptimalencoding.Theletters“C”,“I’and“N”onlyoccuronce,however,sotheywillhavethelongestcodes.

Therearemanypossiblesetsofprefix-freevariable-lengthbitpatternsthatwouldyieldtheoptimalencoding,thatis,thatwouldallowthetexttobeencodedinthefewestnumberofbits.Onesuchoptimalencodingistoencodespaceswith“00”,“A”with“100”,“C”with“1110”,“E”with“1111”,“H”with“110”,“I”with“1010”,“N”with“1011”and“T”with“01”.Theoptimalencodingthereforerequiresonly51bitscomparedtothe144thatwouldbenecessarytoencodethemessagewith8-bitASCIIencoding,acompressionratioof2.8to1.

Input

Theinputfilewillcontainalistoftextstrings,oneperline.Thetextstringswillconsistonlyofuppercasealphanumericcharactersandunderscores（whichareusedinplaceofspaces）.Theendoftheinputwillbesignalledbyalinecontainingonlytheword“END”asthetextstring.Thislineshouldnotbeprocessed.

Output

Foreachtextstringintheinput,outputthelengthinbitsofthe8-bitASCIIencoding,thelengthinbitsofanoptimalprefix-freevariable-lengthencoding,andthecompressionratioaccuratetoonedecimalpoint.

SampleInput

AAAAABCD

THE_CAT_IN_THE_HAT

END

SampleOutput

64134.9

144512.8

Source

GreaterNewYork2000

FireNet

744 

427

Supposethatwehaveasquarecitywithstraightstreets.Amapofacityisasquareboardwithnrowsandncolumns,eachrepresentingastreetorapieceofwall.

Ablockhouseisasmallcastlethathasfouropeningsthroughwhichtoshoot.ThefouropeningsarefacingNorth,East,South,andWest,respectively.Therewillbeonemachinegunshootingthrougheachopening.

Hereweassumethatabulletissopowerfulthatitcanrunacrossanydistanceanddestroyablockhouseonitsway.Ontheotherhand,awallissostronglybuiltthatcanstopthebullets.

Thegoalistoplaceasmanyblockhousesinacityaspossiblesothatnotwocandestroyeachother.Aconfigurationofblockhousesislegalprovidedthatnotwoblockhousesareonthesamehorizontalroworverticalcolumninamapunlessthereisatleastonewallseparatingthem.Inthisproblemwewillconsidersmallsquarecities（atmost4x4）thatcontainwallsthroughwhichbulletscannotrunthrough.

Thefollowingimageshowsfivepicturesofthesameboard.Thefirstpictureistheemptyboard,thesecondandthirdpicturesshowlegalconfigurations,andthefourthandfifthpicturesshowillegalconfigurations.Forthisboard,themaximumnumberofblockhousesinalegalconfigurationis5;

thesecondpictureshowsonewaytodoit,butthereareseveralotherways.

Yourtaskistowriteaprogramthat,givenadescriptionofamap,calculatesthemaximumnumberofblockhousesthatcanbeplacedinthecityinalegalconfiguration.

Theinputfilecontainsoneormoremapdescriptions,followedbyalinecontainingthenumber0thatsignalstheendofthefile.Eachmapdescriptionbeginswithalinecontainingapositiveintegernthatisthesizeofthecity;

nwillbeatmost4.Thenextnlineseachdescribeonerowofthemap,witha'

.'

indicatinganopenspaceandanuppercase'

X'

indicatingawall.Therearenospacesintheinputfile.

Foreachtestcase,outputonelinecontainingthemaximumnumberofblockhousesthatcanbeplacedinthecityinalegalconfiguration.

4

.X..

....

XX..

2

XX

.X

3

.X.

X.X

...

.XX

5

1

ZhejiangUniversityLocalContest2001

MovingTables

2321 

883

ThefamousACM（AdvancedComputerMaker）Companyhasrentedafloorofabuildingwhoseshapeisinthefollowingfigure.

Thefloorhas200roomseachonthenorthsideandsouthsidealongthecorridor.RecentlytheCompanymadeaplantoreformitssystem.Thereformincludesmovingalotoftablesbetweenrooms.Becausethecorridorisnarrowandallthetablesarebig,onlyonetablecanpassthroughthecorridor.Someplanisneededtomakethemovingefficient.Themanagerfiguredoutthefollowingplan:

Movingatablefromaroomtoanotherroomcanbedonewithin10minutes.Whenmovingatablefromroomitoroomj,thepartofthecorridorbetweenthefrontofroomiandthefrontofroomjisused.So,duringeach10minutes,severalmovingbetweentworoomsnotsharingthesamepartofthecorridorwillbedonesimultaneously.Tomakeitclearthemanagerillustratedthepossiblecasesandimpossiblecasesofsimultaneousmoving.

Foreachroom,atmostonetablewillbeeithermovedinormovedout.Now,themanagerseeksoutamethodtominimizethetimetomoveallthetables.Yourjobistowriteaprogramtosolvethemanager’sproblem.

TheinputconsistsofTtestcases.Thenumberoftestcases）（Tisgiveninthefirstlineoftheinput.EachtestcasebeginswithalinecontaininganintegerN,1<

=N<

=200,thatrepresentsthenumberoftablestomove.EachofthefollowingNlinescontainstwopositiveintegerssandt,representingthatatableistomovefromroomnumberstoroomnumbert（eachroomnumberappearsatmostonceintheNlines）.FromtheN+3-rdline,theremainingtestcasesarelistedinthesamemannerasabove.

Theoutputshouldcontaintheminimumtimeinminutestocompletethemoving,oneperline.

3

4

1020

3040

5060

7080

2

13

2200

10100

2080

3050

10

20

30

Asia2001,Taejon（SouthKorea）

StrategicGame

20000/10000MS（Java/Others） 

568 

203

ProblemD