2014acm_icpc全球总决赛题目

Baggage

TimeLimit:1second

AnairlinehastwoflightsleavingataboutthesametimefromICPCity,onetocityBandonetocityA.Theairlinealsohasncounterswherepassengerschecktheirbaggage.Ateachcounterthereisapairofidenticalbaggagebins,oneforcityBandoneforcityA.

Justbeforetheflightsdepart,eachpairofbaggagebinsismovedbyamotorizedcarttoasortingarea.Thecartalwaysmovestwobinsatatime,oneforcityBandoneforcityA.Afterallthebinshavebeenmoved,theylineupinthesortingarealikethis:

BABABA...BA

Thatis,thereare2nbaggagebinsinarow,startingwithabinforcityB,thenoneforcityA,andsoforth.ThetasknowistoreorderthemsoallthebaggagebinsforcityAprecedethebaggagebinsforcityB.Thenthebinscanbeloadedontheappropriateaircraft.

Thereorderingisdonebymovingpairsofadjacentbaggagebins(notnecessarilyBthenA),againviathemotorizedcart.Forproperbalance,thecartmustalwayscarrytwobins,neverjustone.Apairofbinsmustalwaysbemovedtoanemptyspacethatisatleasttwobinswide.Ontheleftofthefirstbinaresomeemptyspacesthatcanbeusedasneededduringthereordering.

Whenthereorderingprocessbegins,thebinlocationsarenumberedfrom1(initiallycontainingtheleftmostBbaggagebin)to2n(initiallycontainingtherightmostAbaggagebin).Thereare2ninitiallyemptyspacestotheleftofthebins,numberedfrom0to−2n+1,asshowninFigureA.1forthecasen=4.

−7−6−5−4−3−2−10B1A2B3A4B5A6B7A8FigureA.1:Initialconfigurationofbinsandemptyspacesforn=4

Givenn,findashortestsequenceofmovesthatwillreorderthebinssothatalltheAbinsaretotheleftofalltheBbins.Attheendoftheprocess,itispossiblethattheleftmostAbinisatsomelocationotherthan1,butthebinsmustbeadjacentinasequenceof2nlocations.

Input

Theinputconsistsofasingletestcase,whichconsistsoftheintegern(3≤n≤100).

Output

Displayashortestsequenceofmovesthatwillcorrectlyreorderthebins.Eachmoveisoftheform“ftot”,wherefandtareintegersrepresentingthemovementofthebinsinlocationsfandf+1tolocationstandt+1.Ifmultiplesolutionsarepossible,displayanyoneofthem.

ACM-ICPCWorldFinals2014ProblemA:Baggage1

SampleInput15

SampleOutput183609tototototo

-18360

SampleInput28

SampleOutput210to-13to1014to37to140to711to04to1115to4

ACM-ICPCWorldFinals2014ProblemA:Baggage2

ProblemB

BuffedBuffet

TimeLimit:4seconds

Youarebuyinglunchatabuffet.Anumberofdifferentdishesareavailable,andyoucanmixandmatchthemtoyourheart’sdesire.Someofthedishes,suchasdumplingsandroastedpotatoes,consistofpiecesofroughlyequalsize,andyoucanpickanintegralnumberofsuchpieces(nosplittingisallowed).Refertotheseas“discretedishes.”Otherdishes,suchastzatzikiormashedpotatoes,arefluidandyoucanpickanarbitraryreal-valuedamountofthem.Refertothissecondtypeas“continuousdishes.”

Ofcourse,youlikesomeofthedishesmorethanothers,buthowmuchyoulikeadishalsodependsonhowmuchofityouhavealreadyeaten.Forinstance,evenifyougenerallypreferdumplingstopotatoes,youmightpreferapotatooveradumplingifyouhavealreadyeatentendumplings.Tomodelthis,eachdishihasaninitialtastinessti,andarateofdecayofthetastiness∆ti.Fordiscretedishes,thetastinessyouexperiencewheneatingthenthitemofthedishisti−(n−1)∆ti.Forcontinuousdishes,thetastinessyouexperiencewheneatinganinfinitesimalamountdxgramsofthedishafteralreadyhavingeatenxgramsis(ti−x∆ti)dx.Inotherwords,therespectivetotalamountsoftastinessyouexperiencewheneatingNitemsofadiscretedishorXgramsofacontinuousdishareasfollows:

N󰀁

(ti−(n−1)∆ti)

and

󰀂

0

X

(ti−x∆ti)dx

n=1

Forsimplicity,donottakeintoaccountthatdifferentdishesmayormaynotgowelltogether,sodefine

thetotaltastinessthatyouexperiencefromamealasthesumofthetotaltastinessesoftheindividualdishesinthemeal(andthesamegoesfortheweightofameal–therearenofoodantiparticlesinthebuffet!).

Youhavespentdaysofpainstakingresearchdeterminingthenumberstiand∆tiforeachofthedishesinthebuffet.Allthatremainsistocomputethemaximumpossibletotaltastinessthatcanbeachievedinamealofweightw.Betterhurryup,lunchisgoingtobeservedsoon!

Input

Theinputconsistsofasingletestcase.Thefirstlineofinputconsistsoftwointegersdandw(1≤d≤250and1≤w≤10000),wheredisthenumberofdifferentdishesatthebuffetandwisthedesiredtotalweightofyourmealingrams.

Thenfollowdlines,theithofwhichdescribestheithdish.Eachdishdescriptionisinoneofthefollowingtwoforms:

•Adescriptionoftheform“Dwiti∆ti”indicatesthatthisisadiscretedishwhereeachitemweighswigrams,withinitialtastinesstianddecayoftastiness∆ti.

•Adescriptionoftheform“Cti∆ti”indicatesthatthisisacontinuousdishwithinitialtastinesstianddecayoftastiness∆ti.

Thenumberswi,ti,and∆tiareintegerssatisfying1≤wi≤10000and0≤ti,∆ti≤10000.

ACM-ICPCWorldFinals2014ProblemB:BuffedBuffet3

Output

Displaythemaximumpossibletotaltastinessofamealofweightwbasedontheavailabledishes.Givetheanswerwitharelativeorabsoluteerrorofatmost10−6.Ifitisimpossibletomakeamealoftotalweightexactlywbasedontheavailabledishes,displayimpossible.

SampleInput1215

D4101C61

SampleOutput140.500000000

SampleInput23DCC

15

41016193

SampleOutput249.000000000

SampleInput3219D451D632

SampleOutput3impossible

ACM-ICPCWorldFinals2014ProblemB:BuffedBuffet4

ProblemC

CraneBalancing

TimeLimit:1second

Whereverthereislarge-scaleconstruction,youwillfindcranesthatdothelifting.Onehardlyeverthinksaboutwhatmarvelousexamplesofengineeringcranesare:astructureof(relatively)littleweightthatcanliftmuchheavierloads.Buteventhebest-builtcranesmayhavealimitonhowmuchweighttheycanlift.

TheAssociationofCraneManufacturers(ACM)needsaprogramtocomputetherangeofweightsthatacranecanlift.Sincecranesaresymmetric,ACMengineershavedecidedtoconsideronlyacrosssectionofeachcrane,whichcanbeviewedasapolygonrestingonthex-axis.

FigureC.1:Cranecrosssection

FigureC.1showsacrosssectionofthecraneinthefirstsampleinput.Assumethatevery1×1unitofcranecrosssectionweighs1kilogramandthattheweighttobeliftedwillbeattachedatoneofthepolygonvertices(indicatedbythearrowinFigureC.1).Writeaprogramthatdeterminestheweightrangeforwhichthecranewillnottoppletotheleftortotheright.

Input

Theinputconsistsofasingletestcase.Thetestcasestartswithasingleintegern(3≤n≤100),thenumberofpointsofthepolygonusedtodescribethecrane’sshape.Thefollowingnpairsofintegersxi,yi(−2000≤xi≤2000,0≤yi≤2000)arethecoordinatesofthepolygonpointsinorder.Theweightisattachedatthefirstpolygonpointandatleasttwopolygonpointsarelyingonthex-axis.

Output

Displaytheweightrange(inkilograms)thatcanbeattachedtothecranewithoutthecranetopplingover.Iftherangeis[a,b],display󰀇a󰀈..󰀉b󰀊.Forexample,iftherangeis[1.5,13.3],display1..14.Iftherangeis[a,∞),display󰀇a󰀈..inf.Ifthecranecannotcarryanyweight,displayunstableinstead.

ACM-ICPCWorldFinals2014ProblemC:CraneBalancing5

SampleInput17

505005000300303040405040

SampleOutput10..1017

SampleInput27

505005000100103020405040

SampleOutput2unstable

ACM-ICPCWorldFinals2014ProblemC:CraneBalancing6

ProblemD

GameStrategy

TimeLimit:8seconds

AliceandBobareplayingaboardgame.Theboardisdividedintopositionslabeleda,b,c,d,...andtheplayersuseagamepiecetomarkthecurrentposition.Eachroundofthegameconsistsoftwosteps:1.Alicemakesachoice.Dependingonthecurrentposition,shehasdifferentoptions,whereeachoptionisasetofpositions.AlicechoosesonesetSamongtheavailablesetsofpositions.2.Bobmakesachoice.HischoiceisonepositionpfromthesetSthatAlicechoseinstep1.Bobmovesthegamepiecetopositionp,whichisthepositionforthestartofthenextround.Priortothefirstround,eachplayerindependentlyselectsoneofthepositionsandrevealsitatthestartofthegame.Bob’spositioniswherethegamestarts.AlicewinsthegameifshecanforceBobtomovethegamepiecetothepositionshehaschosen.Tomakethingsinteresting,theyhavedecidedthatBobwillpayAliceacertainamountifheloses,butAlicemustpayBobacertainamountaftereveryround.ThegamenowendsifAlice’spositionisreachedorwhenAlicerunsoutofcash.

BothAliceandBobplayoptimally:Alicewillalwayschooseanoptionthatwillleadtoherwinningthegame,ifthisispossible,andBobwillalwaystrytopreventAlicefromwinning.

Forallpossiblestartandendpositions,Alicewouldlikeyoutodeterminewhethershecanwinthegameandifso,howmanyroundsitwilltake.

Input

Theinputconsistsofasingletestcase.Thefirstlinecontainsthenumberofpositionsn(1≤n≤25).ThenpositionsarelabeledusingthefirstnlettersoftheEnglishalphabetinlowercase.Therestofthetestcaseconsistsofnlines,oneforeachpositionp,inalphabeticalorder.ThelineforpositionpcontainstheoptionsavailabletoAliceinpositionp.Itstartswiththenumberofoptionsm(1≤m<2n),whichisfollowedbymdistinctstrings,oneforeachoption.EachstringcontainsthepositionsavailabletoBobifAlicechoosesthatoption.Thestringhasatleast1character,thecharacters(whichcorrespondtovalidboardpositions)areinalphabeticalorder,andnocharactersareduplicated.Thetotalnumberofoptionsforthetestcaseisatmost106.

Output

Foreachpositionpinalphabeticalorder,displayoneline.Inthatline,foreachpositionqinalphabeticalorderdisplaytheminimalnumberofroundsinwhichAlicecanbeguaranteedtoarriveatpositionqwhenstartingthegameinpositionp,or−1ifAlicecannotbeguaranteedtoreachqfromp.

SampleInput12

2abb1b

SampleOutput101-10

ACM-ICPCWorldFinals2014ProblemD:GameStrategy7

SampleInput2SampleOutput2301-11b10-12ba220

2abac

ACM-ICPCWorldFinals2014ProblemD:GameStrategy8

ProblemE

MazeReduction

TimeLimit:2seconds

Jayrunsasmallcarnivalthathasvariousridesandattractions.Unfortunately,timesaretough.Arecentrollercoasteraccident,floodingintherestrooms,andanunfortunateclownincidenthavegivenJay’scarnivalabadreputationwiththepublic.Withfewerpayingcustomersandreducedrevenue,hewillneedtocutsomecoststostayinbusiness.

Oneofthebiggestcarnivalattractionsisalarge,confusingmaze.Itconsistsofavarietyofcircularroomsconnectedbynarrow,twistingcorridors.Visitorslovegettinglostinitandtryingtomapitout.IthascometoJay’sattentionthatsomeoftheroomsmightbeeffectivelyidenticaltoeachother.Ifthat’sthecase,hewillbeabletoreduceitssizewithoutanyonenoticing.

TworoomsAandBareeffectivelyidenticalif,whenyouaredroppedintoeitherroomAorB(andyouknowthemapofthemaze),youcannottellwhetheryoubeganinAorBjustbyexploringthemaze.Thecorridorexitsareevenlyspacedaroundeachroom,andyoucannotmarkorleaveanythinginaroom(inparticular,youcannottellwhetheryouhavepreviouslyvisitedit).Theonlyidentifyingfeaturethatroomshaveistheirnumberofexits.Corridorsarealsotwistyenoughtobeindistinguishablefromeachother,butwhenyouenteraroomyouknowwhichcorridoryoucamefrom,soyoucannavigatealittlebyusingtheordertheyappeararoundtheroom.

JayhasappealedtotheAssociationforCarnivalMazeryforhelp.That’syou!Writeaprogramtodetermineallthesetsofeffectivelyidenticalroomsinthemaze.

Input

Theinputconsistsofasingletestcase.Thefirstlinecontainsanintegern,thenumberofroomsinthemaze(1≤n≤100).Roomsarenumberedfrom1ton.Followingthisarenlines,describingeachroominorder.Eachlineconsistsofanintegerk,indicatingthatthisroomhaskcorridors(0≤k<100),andthenkdistinctintegerslistingtheroomseachcorridorconnectsto(inclockwiseorder,fromanarbitrarystartingpoint).Roomsdonotconnecttothemselves.

Output

Displayonelineforeachmaximalsetofeffectivelyidenticalrooms(ignoringsetsofsize1)containingtheroomnumbersinthesetinincreasingorder.Orderthesetsbytheirsmallestroomnumbers.Iftherearenosuchsets,displaynoneinstead.

ACM-ICPCWorldFinals2014ProblemE:MazeReduction9

SampleInput11322431352243136226245227927821113210122111321012

SampleOutput12456

710111213

SampleInput2630112134511165

SampleOutput2none

ACM-ICPCWorldFinals2014ProblemE:MazeReduction10

ProblemF

Messenger

TimeLimit:4seconds

MishaneedstosendpackagestohisfriendNadia.BothofthemoftentravelacrossRussia,whichisverylarge.Sotheydecidetohireamessenger.Sincethecostofthemessengerservicedependsonthetimeittakestodeliverthepackage,theyneedyourhelptooptimizealittlebit.

AssumeMishaandNadiamoveonatwo-dimensionalplane,eachvisitingasequenceofplacesandmovingalongstraightlinesegmentsfromplacetoplace.Yourtaskistofindtheshortestpossibledeliverytimegiventheirtwopaths.

Mishahandsthepackagetothemessengeratsomepointalonghispath.Themessengermoveswithoutdelayalongastraightlinefromthepick-uptointerceptNadia,whoistravelingalongherpath.Misha,Nadiaandthemessengermovewithaconstantspeedof1distanceunitpertimeunit.ThedeliverytimeisthetimebetweenMishahandingoverthepackageandNadiareceivingit.

Input

Theinputconsistsofasingletestcase.Thetestcasecontainstwopathdescriptions,thefirstforMishaandthesecondforNadia.Eachpathdescriptionstartswithalinecontaininganintegern,thenumberofplacesvisited(2≤n≤50000).Thisisfollowedbynlines,eachwithtwointegersxiandyispecifyingthecoordinatesofaplace(0≤xi,yi≤30000).Coordinatesoftheplacesarelistedintheorderinwhichtheyaretobevisited,andsuccessiveplacesdonothavethesamecoordinates.

MishaandNadiastarttheirjourneysatthesametime,visitingtheplacesalongtheirpathswithoutstopping.Thelengthofeachpathisatmost106.ThepackagemustbepickedupatthelatestwhenMishareacheshisfinalplaceanditmustbedeliveredatthelatestwhenNadiareachesherfinalplace.

Output

Displaytheminimaltimeneededfordelivery.Givetheanswerwithanabsoluteerrorofatmost10−3orarelativeerrorofatmost10−5.Ifthepackagecannotbedelivered,displayimpossibleinstead.

SampleInput1200244010100

SampleOutput14.00000

ACM-ICPCWorldFinals2014ProblemF:Messenger11

SampleInput2SampleOutput225.00000

001032030310

ACM-ICPCWorldFinals2014ProblemF:Messenger12

ProblemG

MetalProcessingPlant

TimeLimit:4seconds

YuliaworksforametalprocessingplantinEka-terinburg.ThisplantprocessesoresminedintheUralmountains,extractingpreciousmetalssuchaschalcopyrite,platinumandgoldfromtheores.Everymonththeplantreceivesnshipmentsofun-processedore.Yulianeedstopartitiontheseship-mentsintotwogroupsbasedontheirsimilarity.Then,eachgroupissenttooneoftwoorepro-cessingbuildingsoftheplant.

Toperformthispartitioning,Yuliafirstcalculatesanumericdistanced(i,j)foreachpairofship-PicturefromWikimediaCommonsments1≤i≤nand1≤j≤n,wherethe

smallerthedistance,themoresimilartheship-mentsiandjare.ForasubsetS⊆{1,...,n}ofshipments,shethendefinesthedisparityDofSasthemaximumdistancebetweenapairofshipmentsinthesubset,thatis,

D(S)=maxd(i,j).

i,j∈S

YuliathenpartitionstheshipmentsintotwosubsetsAandBinsuchawaythatthesumoftheirdispar-itiesD(A)+D(B)isminimized.Yourtaskistohelpherfindthispartitioning.

Input

Theinputconsistsofasingletestcase.Thefirstlinecontainsanintegern(1≤n≤200)indicatingthenumberofshipments.Thefollowingn−1linescontainthedistancesd(i,j).Theithoftheselinescontainsn−iintegersandthejthintegerofthatlinegivesthevalueofd(i,i+j).Thedistancesaresymmetric,sod(j,i)=d(i,j),andthedistanceofashipmenttoitselfis0.Alldistancesareintegersbetween0and109(inclusive).

Output

Displaytheminimumpossiblesumofdisparitiesforpartitioningtheshipmentsintotwogroups.

SampleInput15

4502137204

SampleOutput14

ACM-ICPCWorldFinals2014ProblemG:MetalProcessingPlant13

SampleInput2SampleOutput27

15

1105555510555100100551055993

ACM-ICPCWorldFinals2014ProblemG:MetalProcessingPlant14

ProblemH

Pachinko

TimeLimit:6seconds

YouhavebeenhiredbyAddictiveCoinMachinestohelpdesignthenexthitintheirlineofeye-catching,coin-guzzling,just-one-more-tryPachinkomachinesforcasinosaroundtheworld.

PlayingaPachinkomachineinvolveslaunchingballsintoarectangulargridfilledwithpegs,obstacles,andtargets.Theballbouncesaroundthegriduntiliteventuallyhitsoneofthetargets.Theplayerearnsacertainnumberofpointsdependingonwhichtargetishit.

ThegridpatternforthenextPachinkomachinehasalreadybeendesigned,butpointvaluesforthetargetshavenotbeenassigned.Thesemustbesetsothatlikeallcasinomachines,themachineisprofitablebutnottooprofitable.Thusitisimportanttofigureouttheprobabilityofaballhittinganyparticulartarget.That’syourjob!

Forsimplicity,thegridismodeledasatallrectanglefilledwithmostly-openspaces(eachrepresentedby‘.’),impassableobstacles(eachrepresentedby‘X’),andtargets(eachrepresentedby‘T’).Aballislaunchedrandomlywithuniformprobabilityintooneofthemostly-openspacesonthetoprowofthegrid.Fromthatpointon,collisionswithpegscausetheballtorandomlybounceup,down,left,orright,withvariousgivenprobabilities.Forsimplicity,assumetheseprobabilitiesarethesameforeveryspaceinthegrid.Iftheballbouncesintoanobstacleorattemptstomoveoffthegrid,itwon’tactuallymovefromitscurrentspace.Whentheballmovesintoatargetitisremovedfromplay.

Youcansafelyassumethattheaveragenumberofspacesvisitedbyaballbeforehittingatargetwillnotexceed109.Itwouldnotmakeforaveryenjoyablegameiftheballjustbouncesforever!Foreachtarget,calculatetheprobabilitythatitistheonehitbyalaunchedball.

Input

Theinputconsistsofasingletestcase.Thefirstlinecontainsintegerswandh,whicharethewidthandheightofthePachinkogrid(1≤w≤20and2≤h≤10000).Thenextlinecontainsfournon-negativeintegersu,d,l,andr,whichsumto100andarethepercentageprobabilitiesoftheballbouncingup,down,left,orrightfromanyopenspace.

Eachofthenexthlinescontainswcharacters,eachofwhichis‘.’,‘X’,or‘T’.TheselinesdescribethePachinkogrid.Thefirstline,whichdescribesthetoprowofthegrid,containsatleastone‘.’andno‘T’s.

Output

Displayonelineforeach‘T’inthegrid,inorderfromtoptobottom,breakingtieslefttoright.Foreachtarget,displaytheprobabilitythatalaunchedballwillhitit.Givetheanswerwithanabsoluteerrorofatmost10−6.

ACM-ICPCWorldFinals2014ProblemH:Pachinko15

SampleInput132

20202040X.XT.T

SampleOutput10.3333333330.666666667

SampleInput245

12332827.....XX.....T..TXTTX

SampleOutput20.43585380.4037532210.0812025020.079190387

ACM-ICPCWorldFinals2014ProblemH:Pachinko16

ProblemI

SensorNetwork

TimeLimit:2seconds

Awirelesssensornetworkconsistsofau-tonomoussensorsscatteredinanenvironmentwheretheymonitorconditionssuchastemper-ature,sound,andpressure.

SamanthaisaresearcherworkingontheAmazonCarbon-dioxideMeasurement(ACM)project.Inthisproject,awirelesssensornet-workintheAmazonrainforestgathersenvi-PicturefromWikimediaCommons

ronmentalinformation.TheAmazonrainfor-eststoresanamountofcarbonequivalenttoa

decadeofglobalfossilfuelemissions,anditplaysacrucialroleintheworld’soxygen-transferpro-cesses.Becauseofthehugesizeofthisforest,changesintheforestaffectnotonlythelocalenvironmentbutalsoglobalclimatebyalteringwindandoceancurrentpatterns.ThegoaloftheACMprojectistohelpscientistsbetterunderstandearth’scomplexecosystemsandtheimpactofhumanactivities.Samanthahasanimportanthypothesisandtotestherhypothesis,sheneedstofindasubsetofsensorsinwhicheachpairofsensorscancommunicatedirectlywitheachother.Asensorcancommunicatedirectlywithanyothersensorhavingdistanceatmostdfromit.Inorderforherexperimentstobeasaccurateaspossible,Samanthawantstochooseasmanysensorsaspossible.

AsonedoesnotsimplywalkintotheAmazon,Samanthacannotaddnewsensorsormovethosethatarecurrentlyinplace.Sogiventhecurrentlocationsofthesensors,sheneedsyourhelptofindthelargestsubsetsatisfyinghercriteria.Forsimplicity,representthelocationofeachsensorasapointinatwo-dimensionalplanewiththedistancebetweentwopointsbeingtheusualEuclideandistance.

Input

Theinputconsistsofasingletestcase.Thefirstlinecontainstwointegersnandd(1≤n≤100and1≤d≤10000),wherenisthenumberofsensorsavailableanddisthemaximumdistancebetweensensorsthatcancommunicatedirectly.Sensorsarenumbered1ton.Eachofthenextnlinescontainstwointegersxandy(−10000≤x,y≤10000)indicatingthesensorcoordinates,startingwiththefirstsensor.

Output

Displayamaximumsubsetofsensorsinwhicheachpairofsensorscancommunicatedirectly.Thefirstlineofoutputshouldbethesizeofthesubset.Thesecondlineofoutputshouldbethe(one-based)indicesofthesensorsinthesubset.Iftherearemultiplesuchsubsets,anyoneofthemwillbeaccepted.

ACM-ICPCWorldFinals2014ProblemI:SensorNetwork17

SampleInput14001110101

SampleOutput1212

SampleInput25200002

100100100110100120

SampleOutput23

435

ACM-ICPCWorldFinals2014ProblemI:SensorNetwork18

ProblemJ

Skiing

TimeLimit:2seconds

Asyouknow,theACMICPCisnottheonlymajorsportingeventtakingplaceinRussiathisyear.Severalmonthsago,the2014WinterOlympicswereheldinSochi,whichisabout3000kmfromEkaterinburg.

Inanincreasingnumberofsports,itisnotonlytheabilityoftheathletesthatdetermineswhowinsacompetitionbutalsotheirequipment.Forexampleindownhillskiing,havingthelatestskitechnologyenablesathletestoincreasetheirspeedsandimprovetheirturningability.

Youhavebeenhiredtodeterminetheeffectofthelatestskitechnologyontheabilityofskierstonavigateadownhillcourse.Thecoursecontainsseveraltargetlocations,andtheskierwantstopassoverasmanyofthemaspossible.Naturally,thebettertheskitechnology,theeasieritwillbetodothis.

Forsimplicity,useatwo-dimensionalcoordinatesystemwheretheskierstartsatposition(0,0)andwhere“downhill”correspondstothedirectionofthepositivey-axis.

Assumethey-componentoftheathlete’svelocityisaconstantvy.Theathletecanchangespeedlaterally(inthex-direction),buttheskiingequipmentlimitsthistoamaximallateralaccelerationamax.Theskierstartswithalateralvelocityof0.

y

Skier’s path(0,0)x

FigureJ.1:Downhillskipathpassingoverthreetargets

InFigureJ.1(whichcorrespondstothefirstsampleinput),theoptimalpathpassesoverthreeoutoffourpossibletargets.Ifamaxweresmaller,thentheskiermightbeabletopassoveronlytwoorfewerofthetargets.

ACM-ICPCWorldFinals2014ProblemJ:Skiing19

Input

Theinputcontainsasingletestcase.Thefirstlinecontainsthreeintegersn,vy,andamax(0≤n≤250,0≤vy≤105and0≤amax≤107),wherenisthenumberoftargets,vyisthey-componentoftheskier’svelocity,andamaxisthemaximumlateralacceleration.Herevyisgiveninmetersperhourandamaxinmetersperhoursquared.

Followingthisarenlines,eachcontainingtwointegersxiandyi(−105≤xi,yi≤105).Thesegivethecoordinatesofeachtargettobevisitedonthecourse.Allcoordinatesaregiveninmeters.Targetsarenumbered1,2,...,nintheordertheyaregiven.

Output

Displaythemaximal-lengthsequenceoftargetsthattheathletecouldpassoveronthecourseinasinglerun.Displaythetargetsintheordertheyarevisited.Iftherearemultiplemaximal-lengthsequences,displayonlythelexicographicallyfirstone.(Sothesequence215wouldcomebeforethesequence1015.)Iftheathletecannotpassoveranytargets,printCannotvisitanytargetsinstead.Toensurefloating-pointstability,youmayassumetheanswerwillnotchangeifamaxisperturbedbyupto0.1.

SampleInput14100400-10010050200-100300150300

SampleOutput1124

SampleInput21100100100010

SampleOutput2

Cannotvisitanytargets

ACM-ICPCWorldFinals2014ProblemJ:Skiing20

ProblemK

Surveillance

TimeLimit:4seconds

TheInternationalCorporationforProtectionandControl(ICPC)developsefficienttechnologyfor,well,protectionandcontrol.Naturally,theyarekeentohavetheirownheadquartersprotectedandcontrolled.Viewedfromabove,theheadquartersbuildinghastheshapeofaconvexpolygon.Thereareseveralsuitableplacesarounditwherecamerascanbeinstalledtomonitorthebuilding.Eachcameracoversacertainrangeofthepolygonsides(buildingwalls),dependingonitsposition.ICPCwantstominimizethenumberofcamerasneededtocoverthewholebuilding.

Input

Theinputconsistsofasingletestcase.Itsfirstlinecontainstwointegersnandk(3≤n≤106and1≤k≤106),wherenisthenumberofwallsandkisthenumberofpossibleplacesforinstallingcameras.Eachoftheremainingklinescontainstwointegersaiandbi(1≤ai,bi≤n).Theseintegersspecifywhichwallsacameraattheithplacewouldcover.Ifai≤bithenthecameracoverseachwalljsuchthatai≤j≤bi.Ifai>bithenthecameracoverseachwalljsuchthatai≤j≤nor1≤j≤bi.

Output

Displaytheminimalnumberofcamerasthatsufficetocovereachwallofthebuilding.Therangescoveredbytwocamerasmayoverlap.Ifthebuildingcannotbecovered,displayimpossibleinstead.

SampleInput11007150507070909040206060808020

SampleOutput13

SampleInput2828357

SampleOutput2impossible

SampleInput3828457

SampleOutput32

ACM-ICPCWorldFinals2014ProblemK:Surveillance21

Thispageisintentionallyleftblank.

ProblemL

WireCrossing

TimeLimit:2seconds

Moore’sLawstatesthatthenumberoftransistorsonachipwilldoubleeverytwoyears.Amazingly,thislawhasheldtrueforoverhalfacentury.Whenevercurrenttechnologynolongerallowedmoregrowth,researchershavecomeupwithnewmanufacturingtechnologiestopackcircuitsevendenser.Inthenearfuture,thismightmeanthatchipsareconstructedinthreedimensionsinsteadtwo.Butforthisproblem,twodimensionswillbeenough.

Aproblemcommontoalltwo-dimensionalhardwaredesign(forexamplechips,graphicscards,moth-erboards,andsoon)iswireplacement.Wheneverwiresareroutedonthehardware,itisproblematiciftheyhavetocrosseachother.Whenacrossingoccursspecialgadgetshavetobeusedtoallowtwoelectricalwirestopassovereachother,andthismakesmanufacturingmoreexpensive.

Ourproblemisthefollowing:youaregivenahardwaredesignwithseveralwiresalreadyinplace(allofthemstraightlinesegments).Youarealsogiventhestartandendpointsforanewwireconnectiontobeadded.Youwillhavetodeterminetheminimumnumberofexistingwiresthathavetobecrossedinordertoconnectthestartandendpoints.Thisconnectionneednotbeastraightline.Theonlyrequirementisthatitcannotcrossatapointwheretwoormorewiresalreadymeetorintersect.

FigureL.1:Firstsampleinput

FigureL.1showsthefirstsampleinput.Eightexistingwiresformfivesquares.Thestartandendpointsofthenewconnectionareintheleftmostandrightmostsquares,respectively.Theblackdashedlineshowsthatadirectconnectionwouldcrossfourwires,whereastheoptimalsolutioncrossesonlytwowires(thecurvedblueline).

Input

Theinputconsistsofasingletestcase.Thefirstlinecontainsfiveintegersm,x0,y0,x1,y1,whicharethenumberofpre-existingwires(m≤100)andthestartandendpointsthatneedtobeconnected.Thisisfollowedbymlines,eachcontainingfourintegersxa,ya,xb,ybdescribinganexistingwireofnon-zerolengthfrom(xa,ya)to(xb,yb).Theabsolutevalueofeachinputcoordinateislessthan105.Eachpairofwireshasatmostonepointincommon,thatis,wiresdonotoverlap.Thestartandendpointsforthenewwiredonotlieonapre-existingwire.ACM-ICPCWorldFinals2014ProblemL:WireCrossing

23

Output

Displaytheminimumnumberofwiresthathavetobecrossedtoconnectthestartandendpoints.

SampleInput18331930122105225101650569096130136170176210216

SampleOutput12

SampleInput2105105001010

SampleOutput20

ACM-ICPCWorldFinals2014ProblemL:WireCrossing24