Az eredeti feladat itt.

Feladat

Adott egy város a négyzetrácson. Az utcák a tengelypárhuzamos, rácspontokon keresztül húzott egyenesek, közülük a főút az x-tengely. A polgármester tűzijátékot szeretne rendezni a főút valamelyik rácspontjában, azonban azt csak a rácsponton keresztül haladó utcákról lehet látni. Tehát ha a (p,0) pontban rendezi, akkor azt a főútról, valamint az x=p egyenesről látni. A helyszínt úgy akarja kiválasztani, hogy a (fontosabb) városlakóknak minél kevesebbet kelljen sétálni ahhoz, hogy megnézhessék a tűzijátékot. A sétatáv Manhattan-távolságban értendő, azaz csak utcákon sétálhatnak, és szomszédos utcák közt egy egységnyi utat kell megtenni.

Van néhány magyar versenyről származó feladat is, amely érdekes, nem triviális, sőt fontos. Ugyanakkor ezekkel nagyobb eséllyel is találkozhattatok, úgyhogy igyekszem mellettük máshonnan származó, és talán valamivel nehezebb feladatokat is kitűzni, hogy ne unatkozzatok. Ez az intervallumos is egy ilyen példa: a 2007-es válogatóversenyen szerepelt, és ahhoz képest viszonylag nehéznek mondható (nemzetközi szinten inkább könnyű), viszont hallatlanul fontos módszert gyakoroltat.

Még azt itt megjegyezném, hogy példabemenetet és ábrákat a legritkább esetben fogok a posztba beleírni, viszont mindig linkelem az eredeti feladatleírást, ahol ezek megtalálhatóak.