O fficial Problem Set DO NOT OPEN UNTIL CONTEST BEGINS 2017 ACM ICPC North Central North America R egional Contest October 28, 2017 This page is intentionally left blank. 2017ACMICPCNorthCentralNorthAmericaRegionalContest Problems A Stoichiometry B PokemonGoGo C UrbanDesign D SmoothArray E Is-A?Has-A?WhoKnowz-A? F Atlantis G Sheba’sAmoebas H ZebrasandOcelots I RacingAroundtheAlphabet J LostMap NCNA2017 3 This page is intentionally left blank. 2017ACMICPCNorthCentralNorthAmericaRegionalContest Problem A Stoichiometry You have landed a lucrative contract with Amalga- mated Chemical Manufacturing (ACM), to help their chemists with stoichiometry. Stoichiometry is the cal- culationofreactantsandproductsinchemicalreactions, based on the law of conservation of mass, which states thatthetotalmassofthereactantsequalsthetotalmass oftheproducts. Therelationsamongquantitiesofreac- tantsandproductstypicallyformaratioofpositiveinte- gers. Iftheamountsoftheseparatereactantsareknown, then the amount of the product can be calculated, and vice-versa. Therelationshipofreactantstoproductscan bedescribedusingasoichiometricequationsuchas: ImagebyGerdAltmann. CH +2O →CO +2H O, (1) 4 2 2 2 whichcanbereadas:“OnemoleculeofCH andtwomoleculesofO yieldonemoleculeofCO andtwomolecules 4 2 2 ofH O.” Thetotalnumberofatomsofeachelementonthelefthandsideofthestoichiometricequationmustmatch 2 thenumberofatomsofthatelementonrighthandside. Yourtaskistowriteaprogramthat,givenanequationofthe form: _H O+_CO →_O +_C H O , (2) 2 2 2 6 12 6 willfillintheblankstoproduceabalancedequation. Forexample,theaboveequationcouldbebalancedasfollows: 6H O+6CO →6O +1C H O . (3) 2 2 2 6 12 6 Input AnequationisinputintheformofasequenceofM (1<M ≤20)lines,oneforeachmoleculeintheformula(e.g., H OorCO ). Eachlinem(1≤m≤M)hasthefollowingfields: 2 2 sign N element count ... element count m m m,1 m,1 m,Nm m,Nm wheresign iseither+1or-1, withasignof+1indicatingthatthismoleculeappearsontheleftoftheequation, m and -1 indicating that it appears on the right. N , where 0 < N < 20, is the number of element/count pairs m m following on the line. Each element , where 1 ≤ n ≤ N , is an element name consisting of one or two upper m,n m orlowercase letters, and eachcount isa positiveinteger, 1 ≤ count ≤ 12. For example, the element/count m,n m,n pair“Fe 2”indicatesthatthemoleculecontainstwoatomsoftheelementFe(iron). Therewillbenomorethan10 uniqueelementsinasingleequation. Notethatanelementmayberepeatedinagivenlineofinput,asin +1 6 C 1 H 5 C 1 O 1 O 1 H 1 whichspecifiesthatatleastonemoleculeofCH COOHappearsontheleftsideoftheequation.NotethatCH COOH 5 5 canbewrittenasC H O . 2 6 2 Inputendswithalineoftheform 0 0 NCNA2017ProblemA:Stoichiometry 5 2017ACMICPCNorthCentralNorthAmericaRegionalContest Output TheprogrammustoutputthenumbersC ,...,C (0 < C ≤ 1000),inorder,tofillintheblanksintheequation. 1 M i Eachnumber,C | 1 ≤ m ≤ M,mustbetheminimumnumberforwhichtheequationisbalanced(i.e. thereisno m commonfactorthatcouldreducealloftheC coefficients). Youmayassumethateveryinputtestcasehasexactly m onevalidsolutionmeetingthesecriteria. SampleInput1 SampleOutput1 +1 2 H 2 O 1 6 6 6 1 +1 2 C 1 O 2 -1 1 O 2 -1 3 C 6 H 12 O 6 0 0 SampleInput2 SampleOutput2 +1 5 Be 2 C 1 O 3 O 2 H 2 2 6 1 5 2 +1 3 Ac 1 O 1 H 1 -1 4 Be 4 O 1 Ac 6 O 6 -1 2 H 2 O 1 -1 2 C 1 O 2 0 0 NCNA2017ProblemA:Stoichiometry 6 2017ACMICPCNorthCentralNorthAmericaRegionalContest Problem B Pokemon Go Go Always Catch your Mon, Inc., (also know as ACM), wants to create a new product, called Pokémon Go Go. Users can purchase this application to help themplayPokémongo. Thesoftwareaccessesthepokéstoplocationsnearthe current location as well as a list of Pokémon that can be found at each stop. Theapplicationthencomputestheshortestrouteonecanfollowtocatchallthe uniquePokémon,andreturntothestartingpoint. The program assumes that the user is in a city where travel is restricted to moving only in the north–south and east–west directions. The program also assumesthatallpokéstopsareontheintersectionoftworoads. For example, consider a case where the application finds five nearby poké stops. Each stop’s location is indicated by two integers, (r,c), where r is the numberofblocksnorthofyourstartingpositionandcisthenumberofblocks westofyourstartingposition.Considerifthelocationsofthefivepokéstopsare (5,9),(20,20),(1,1),(1,8)and(2,8)whilethenamesofthePokémonfound atthesestopsareEvevee,Flareon,Flareon,Jolteon,andUmbreon,respectively. ImagebyAnaVerrusio. It is clear that one does not have to visit both the second and third stops, since the same Pokémon can be caught at eitherofthem. Thebestrouteistovisitthefirst,fifth,fourth,andthirdstops(inthatorder)foratotaldistanceof28 blocks,since: • Thedistancefrom(0,0)to(5,9)is14. • Thedistancefrom(5,9)to(2,8)is4. • Thedistancefrom(2,8)to(1,8)is1. • Thedistancefrom(1,8)to(1,1)is7. • Thedistancefrom(1,1)to(0,0)is2. Input Theinputholdsasingletestcase.Thetestcasebeginswithasingleintegern,0<n≤20,whichindicatesthenumber ofpokéstopstoconsider.EachofthenextnlinesspecifiesthelocationofapokéstopandthenameofaPokémonthat canbefoundthere. Thelocationisspecifiedbytwointegersrandcseparatedbyasinglespace,−100≤r,c≤100. The integers r and c indicate that the stop is r blocks north and c blocks east of the starting point. The location is followedbyasinglespaceandfollowedbythestringpindicatingthenameofthePokémonthatcanbecaughtthere. Nameshavebetween1and25letters(usingonlya–zandA–Z).ThenumberofuniquePokémonisalwayslessthan orequalto15. Multiplepokémoncanresideatasinglepokéstopandarelistedonseparatelines. Output Givetheshortestdistance,inblocks,requiredtocatchalltheuniquePokémon. NCNA2017ProblemB:PokemonGoGo 7 2017ACMICPCNorthCentralNorthAmericaRegionalContest SampleInput1 SampleOutput1 5 28 5 9 Eevee 20 20 Flareon 1 1 Flareon 1 8 Jolteon 2 8 Umbreon NCNA2017ProblemB:PokemonGoGo 8 2017ACMICPCNorthCentralNorthAmericaRegionalContest Problem C Urban Design A new town is being planned, and the designers have some very specificideasabouthowthingsshouldbelaidout. First,theylayout the streets. Each street is perfectly straight and passes completely fromoneendofthetowntotheother. Thesestreetsdividethetown intoregions,andeachregionistobedesignatedeither“residential” or “commercial.” The town planners require that any two regions directlyacrossthestreetfromoneanothermusthavedifferentdes- ignations. On this one particular day, all of the streets have been planned, but none of the regions have been designated. One town plannerwishestopurchasetwoproperties,anditisimportanttohim that the properties eventually have different designations. For this problem,thestreetscanbemodeledbylinesintheplanethatextend ImagebyDietmarSilber. foreverinbothdirectionsandhavenowidth,andpropertiesmaybe modeledbypoints.Giventhelinesandtwopoints,canyoudecidewhetherornottheymustgetdifferentdesignations, “commercial”or“residential?” Input Input begins with an integer S on a single line, giving the number of streets (1 ≤ S ≤ 10000). The next S lines of input each contain four integers x , y , x , and y , specifying the coordinates of two distinct points (x ,y ) and 1 1 2 2 1 1 (x ,y ). Theuniquelinethroughthesetwopointsgivesoneofthestreets. Eachcoordinateisintherange[0,10000], 2 2 andnotwolineswillbeidentical. Thatis,thetownwillhaveS distinctstreets. ThenextlinecontainsanintegerT, thenumberofpairsofpropertiestotest(1 ≤ T ≤ 1000). ThisisfollowedbyT linesofinput,eachcontainingfour integersx ,y ,x ,andy ,representingtwodistinctpoints(x ,y )and(x ,y ),whereeachpointlieswithinoneof 3 3 4 4 3 3 4 4 thetwopropertiestotest. Noneofthesepointswilllieonanyofthestreets,norwillbothpointsliewithinthesame property. Again,eachcoordinateisintherange[0,10000]. Output ForeachoftheT pairsofpropertiestobetested,outputeither“same”ifthepropertiesareguaranteedtoreceivethe samedesignationor“different”iftheyareguaranteedtoreceivedifferentdesignations. SampleInput1 SampleOutput1 2 different 1 1 2 1 same 1 1 1 2 same 3 2 0 2 2 2 0 0 3 0 0 2 2 NCNA2017ProblemC:UrbanDesign 9 2017ACMICPCNorthCentralNorthAmericaRegionalContest SampleInput2 SampleOutput2 4 same 1 3 2 4 different 1 3 2 5 1 3 3 4 7 9 8 8 2 14 7 10 13 1 4 2 3 NCNA2017ProblemC:UrbanDesign 10