IEE极限编程预赛题目

《IEE极限编程预赛题目》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Language:1246HilbertCurveIntersectionsTimeLimit: 1000MSMemoryLimit: 10000KTotalSubmissions: 171Accepted: 58DescriptionDavidHilbertprovedtheexistenceofaverycounter-intuitivecurvethatfillsspace.TheconstructionoftheHilbertcurveisbasedonasequenceofcurves,H1,H2,H3,H4,...composedofhor

2、izontalandverticalsegments.Eachcurveliesintheunitsquare[0,1]*[0,1].H1containsjustthreesegments,connectingthepoints(1/4,3/4)to(1/4,1/4)to(3/4,1/4)to(3/4,3/4).Hn isdefinedrecursivelyintermsofHn-1,forn=2,3,...byfourtransformations: 1.HalveallcoordinatesinHn-1. 2.Addacopyrotated90de

3、greescounterclockwiseaboutthepoint(0,1/2). 3.Addthereflectionacrossthelinex=1/2. 4.Letm=1/2n+1.Addsegmentsconnectingendpoints(1/2-m,1/2-m)to(1/2+m,1/2-m),(m,1/2-m)to(m,1/2+m),and(1-m,1/2-m)to(1-m,1/2+m). Yourjobistocountthenumberofintersectionsofhorizontallinesegmentswiththesecu

4、rves.Forexample,considerFigures1and2,whichillustratethefirsttwoexampleinputdatasetsbelow. ThecoordinatesofverticesofHnareoddmultiplesof1/2n+1.Thecoordinatesofhorizontalsegmentendpointswillalwaysbemultiplesof1/2n.HencethespecifiedhorizontalsegmentcanonlycrossverticalsegmentsinHn.

5、 InputInputconsistsofoneto100datasets,oneperline,followedbyafinallinecontainingonly0.Eachdatasetconsistsoffourintegersseparatedbyblanksintheform nx1x2y whichrepresentsHn andthesegmentfrom(x1/2n,y/2n)to(x2/2n,y/2n),where0

6、. OutputTheoutputisoneintegerperlineforeachdataset:thenumberofintersectionsofHn withthesegment.Caution:Abruteforcesolutionthatcomputeseachintersectionindividuallywillnotfinishwithintheoneminutetimelimit.Asyoucanseebelow,theremaybemorethanonebillionintersectionsforanydataset. Sam

7、pleInput3277 40161 30110737418231 0SampleOutput3 16 1073741822SourceMid-CentralUSA20023766HexagonCoinTossTimeLimit: 1000MSMemoryLimit: 65536KTotalSubmissions: 378Accepted: 113DescriptionHexagonCoinTossisasimplegameplayedonaHexagonchessboard.Playerstossacoinonthechessboardandseeh

8、owmanyhexagonsintersectwiththecoin.Nowyouaregiv