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.

Feladat

Adott N intervallum. Válasszunk ki közülük egy olyat, amely a többi intervallum közül a lehető legtöbbet tartalmaz. (Részhalmazaként, tehát [1,2] tartalmazza [1,2]-t.)

input

Az első sor egy egész szám, 1<=N<=1 000 000, a következő N sor mindegyike pedig két egész számot tartalmaz az i+1-edik sorban A B azt jelenti, hogy az i-edik intervallum [A,B].

output

Egy sorba két egész szám: a kiírandó intervallum sorszáma és az általa tartalmazott intervallumok száma.

Olimpiai Válogatóverseny, 2007/7

A bejegyzés trackback címe:

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.