ACM 省赛题 求算法

图片 1

(1)MagicSequenceIvankevinlovessequences.Asequenceofn+melementsiscalledaMAGICSEQUENCEit.1.Eachelementsai(1=i=n+m)is+1or-1.2.Therearetotaln“+1”sandm“-1”s.3.Foreveryj(1=j=n+m),wehavethesumofai(1=i=j)isnonnegative.Nowgivennandm,Ivankevinwantstoknowthenumberofmagicsequencesconsistsofn“+1”sandm“-1”s.InputThefirstlineisanintegerT,thenumberoftestcases.Eachcaseisalineoftwointegersnandm,1=n,m=100.OutputForeachcase,printanintegerx,whichisthenumberofmagicsequencesmodulo100000007.SampleInput22133SampleOutput25(2)ThelargestArrowThreepointsA(x1,y1),B(x2,y2),andC(x3,y3)formanarrowifandonlyifthefollowingconditionsarefulfilled:x1=x3x2y1y2y3Thelengthofthearrow(x2-x1)mustnotshorterthanthewidthofthearrowy3-y1.Figure3.1showsanexampleofanarrow.Wedefinethesizeofanarrowasitslengthplusitswidth.GivenNpointsintheplane,what’sthelargestpossiblearrowcanbeformedfromthreeofthegivenpoints?Input:ThefirstlineoftheinputcontainsapositiveintegerTspecifyingthenumberoftestcasestofollow.ThefistlineeachtestcasecontainsapositiveintegerN(1=N=2000).ThenfollowsNlines,eachdescribesapointwithcoordinates(xi,yi).(0=xi,yi=107)It’sassumedthatnotwopointsareatthesamelocation.Output:Foreachtestcaseyoushouldoutputasinglelinecontaining“CaseX:Y”(quotesforclarity)whereXisthenumberofthetestcase(startingat1).Yisthesizeofthelargestarrowintheplane.Ifthere’snotanyarrowintheplan,Yshouldbeequalto-1.SampleInput:1522256424210SampleOutputCase1:7

相关文章