ACM程序题目Word文件下载.docx

ACM程序题目Word文件下载.docx

《ACM程序题目Word文件下载.docx》由会员分享，可在线阅读，更多相关《ACM程序题目Word文件下载.docx（41页珍藏版）》请在冰点文库上搜索。

99.999）andnisanintegersuchthat0<

n<

=25.

Input

TheinputwillconsistofasetofpairsofvaluesforRandn.TheRvaluewilloccupycolumns1through6,andthenvaluewillbeincolumns8and9.

Output

TheoutputwillconsistofonelineforeachlineofinputgivingtheexactvalueofR^n.Leadingzerosshouldbesuppressedintheoutput.Insignificanttrailingzerosmustnotbeprinted.Don'

tprintthedecimalpointiftheresultisaninteger.

SampleInput

95.12312

0.432120

5.123415

6.75929

98.99910

1.010012

SampleOutput

548815*********830194541.899025343415715973535967221869852721

.00000005148554641076956121994511276767154838481760200726351203835429763013462401

43992025569.928573701266488041146654993318703707511666295476720493953024

29448126.764121021618164430206909037173276672

90429072743629540498.107596019456651774561044010001

1.126825*********720661201

Hint

Ifyoudon'

tknowhowtodeterminewheatherencountedtheendofinput:

s 

isastringand 

n 

isaninteger 

C++

while（cin>

>

s>

n）

{

...

}

c

while（scanf（"

%s%d"

s,&

n）==2）//toseeifthescanfreadinasmanyitemsasyouwant

/*while（scanf（%s%d"

n）!

=EOF）//thisalsowork*/

1002（17%）

487-3279

2000MS

65536K

166172

28392

Businessesliketohavememorabletelephonenumbers.Onewaytomakeatelephonenumbermemorableistohaveitspellamemorablewordorphrase.Forexample,youcancalltheUniversityofWaterloobydialingthememorableTUT-GLOP.Sometimesonlypartofthenumberisusedtospellaword.WhenyougetbacktoyourhoteltonightyoucanorderapizzafromGino'

sbydialing310-GINO.Anotherwaytomakeatelephonenumbermemorableistogroupthedigitsinamemorableway.YoucouldorderyourpizzafromPizzaHutbycallingtheir``threetens'

'

number3-10-10-10. 

Thestandardformofatelephonenumberissevendecimaldigitswithahyphenbetweenthethirdandfourthdigits（e.g.888-1200）.Thekeypadofaphonesuppliesthemappingofletterstonumbers,asfollows:

A,B,andCmapto2 

D,E,andFmapto3 

G,H,andImapto4 

J,K,andLmapto5 

M,N,andOmapto6 

P,R,andSmapto7 

T,U,andVmapto8 

W,X,andYmapto9 

ThereisnomappingforQorZ.Hyphensarenotdialed,andcanbeaddedandremovedasnecessary.ThestandardformofTUT-GLOPis888-4567,thestandardformof310-GINOis310-4466,andthestandardformof3-10-10-10is310-1010. 

Twotelephonenumbersareequivalentiftheyhavethesamestandardform.（Theydialthesamenumber.） 

Yourcompanyiscompilingadirectoryoftelephonenumbersfromlocalbusinesses.Aspartofthequalitycontrolprocessyouwanttocheckthatnotwo（ormore）businessesinthedirectoryhavethesametelephonenumber. 

Theinputwillconsistofonecase.Thefirstlineoftheinputspecifiesthenumberoftelephonenumbersinthedirectory（upto100,000）asapositiveintegeraloneontheline.Theremaininglineslistthetelephonenumbersinthedirectory,witheachnumberaloneonaline.Eachtelephonenumberconsistsofastringcomposedofdecimaldigits,uppercaseletters（excludingQandZ）andhyphens.Exactlysevenofthecharactersinthestringwillbedigitsorletters. 

Generatealineofoutputforeachtelephonenumberthatappearsmorethanonceinanyform.Thelineshouldgivethetelephonenumberinstandardform,followedbyaspace,followedbythenumberoftimesthetelephonenumberappearsinthedirectory.Arrangetheoutputlinesbytelephonenumberinascendinglexicographicalorder.Iftherearenoduplicatesintheinputprinttheline:

Noduplicates. 

12

4873279

ITS-EASY

888-4567

3-10-10-10

888-GLOP

TUT-GLOP

967-11-11

310-GINO

F101010

888-1200

-4-8-7-3-2-7-9-

310-10102

487-32794

888-45673

1006（30%）

Biorhythms

1000MS

81827

24704

Somepeoplebelievethattherearethreecyclesinaperson'

slifethatstartthedayheorsheisborn.Thesethreecyclesarethephysical,emotional,andintellectualcycles,andtheyhaveperiodsoflengths23,28,and33days,respectively.Thereisonepeakineachperiodofacycle.Atthepeakofacycle,apersonperformsathisorherbestinthecorrespondingfield（physical,emotionalormental）.Forexample,ifitisthementalcurve,thoughtprocesseswillbesharperandconcentrationwillbeeasier. 

Sincethethreecycleshavedifferentperiods,thepeaksofthethreecyclesgenerallyoccuratdifferenttimes.Wewouldliketodeterminewhenatriplepeakoccurs（thepeaksofallthreecyclesoccurinthesameday）foranyperson.Foreachcycle,youwillbegiventhenumberofdaysfromthebeginningofthecurrentyearatwhichoneofitspeaks（notnecessarilythefirst）occurs.Youwillalsobegivenadateexpressedasthenumberofdaysfromthebeginningofthecurrentyear.Youtaskistodeterminethenumberofdaysfromthegivendatetothenexttriplepeak.Thegivendateisnotcounted.Forexample,ifthegivendateis10andthenexttriplepeakoccursonday12,theansweris2,not3.Ifatriplepeakoccursonthegivendate,youshouldgivethenumberofdaystothenextoccurrenceofatriplepeak. 

Youwillbegivenanumberofcases.Theinputforeachcaseconsistsofonelineoffourintegersp,e,i,andd.Thevaluesp,e,andiarethenumberofdaysfromthebeginningofthecurrentyearatwhichthephysical,emotional,andintellectualcyclespeak,respectively.Thevaluedisthegivendateandmaybesmallerthananyofp,e,ori.Allvaluesarenon-negativeandatmost365,andyoumayassumethatatriplepeakwilloccurwithin21252daysofthegivendate.Theendofinputisindicatedbyalineinwhichp=e=i=d=-1.

Foreachtestcase,printthecasenumberfollowedbyamessageindicatingthenumberofdaystothenexttriplepeak,intheform:

Case1:

thenexttriplepeakoccursin1234days. 

Usethepluralform``days'

eveniftheansweris1.

0000

000100

52034325

4567

28310223320

20330120340

-1-1-1-1

thenexttriplepeakoccursin21252days.

Case2:

thenexttriplepeakoccursin21152days.

Case3:

thenexttriplepeakoccursin19575days.

Case4:

thenexttriplepeakoccursin16994days.

Case5:

thenexttriplepeakoccursin8910days.

Case6:

thenexttriplepeakoccursin10789days.

1009（21%）

EdgeDetection

11467

2445

IONUSatelliteImaging,Inc.recordsandstoresverylargeimagesusingrunlengthencoding.Youaretowriteaprogramthatreadsacompressedimage,findstheedgesintheimage,asdescribedbelow,andoutputsanothercompressedimageofthedetectededges. 

Asimpleedgedetectionalgorithmsetsanoutputpixel'

svaluetobethemaximumabsolutevalueofthedifferencesbetweenitandallitssurroundingpixelsintheinputimage.Considertheinputimagebelow:

Theupperleftpixelintheoutputimageisthemaximumofthevalues|15-15|,|15-100|,and|15-100|,whichis85.Thepixelinthe4throw,2ndcolumniscomputedasthemaximumof|175-100|,|175-100|,|175-100|,|175-175|,|175-25|,|175-175|,|175-175|,and|175-25|,whichis150. 

Imagescontain2to1,000,000,000（109）pixels.Allimagesareencodedusingrunlengthencoding（RLE）.Thisisasequenceofpairs,containingpixelvalue（0-255）andrunlength（1-109）.Inputimageshaveatmost1,000ofthesepairs.Successivepairshavedifferentpixelvalues.Alllinesinanimagecontainthesamenumberofpixels. 

Inputconsistsofinformationforoneormoreimages.Eachimagestartswiththewidth,inpixels,ofeachimageline.ThisisfollowedbytheRLEpairs,onepairperline.Alinewith00indicatestheendofthedataforthatimage.Animagewidthof0indicatestherearenomoreimagestoprocess.Thefirstimageintheexampleinputencodesthe5x7inputimageabove. 

Outputisaseriesofedge-detectedimages,inthesameformatastheinputimages,exceptthattheremaybemorethan1,000RLEpairs. 

7

154

10015

252

1752

255

00

10

35500000000

200500000000

3

2551

101

2552

855

02

7510

1502

753

04

0499999990

16520

2459

Abruteforcesolutionthatattemptstocomputeanoutputvalueforeveryindividualpixelwilllikelyfailduetospaceortimeconstraints. 

1007（39%）

DNASorting

57392

22516

Onemeasureof``unsortedness'

inasequenceisthenumberofpairsofentriesthatareoutoforderwithrespecttoeachother.Forinstance,inthelettersequence``DAABEC'

thismeasureis5,sinceDisgreaterthanfourletterstoitsrightandEisgreaterthanonelettertoitsright.Thismeasureiscalledthenumberofinversionsinthesequence.Thesequence``AACEDGG'

hasonlyoneinversion（EandD）---itisnearlysorte