NézetNyomtat

Színház (Megoldás)
Címkék > Feladat
Címkék > Hiányzó algoritmus

Színház

Egy színházi előadást olyan teremben tartanak, ahol $M$ db ülőhely van. Az ülőhelyek 1-től $M$-ig sorszámozottak. A szervezők megrendeléseket fogadnak. Minden megrendelés egy $A, B$ számpárt tartalmaz, ami azt jelenti, hogy a megrendelő olyan ülőhelyet szeretne kapni, amelynek $S$ sorszáma $A$ és $B$ közé esik $(A\le S\le B)$.

Feladat

Készíts programot, amely kiszámítja, hogy a szervezők a megrendelések alapján a legjobb esetben hány megrendelést tudnak kielégíteni és meg is ad egy olyan jegykiosztást, amely kielégíti a megrendeléseket!

Bemenet

Az input (szinhaz.be) állomány első sorában két egész szám van, $M$ és $N$. $M$ az ülőhelyek száma $(1\le M\le 1000)$, $N$ $(1\le N\le 1000)$ pedig a megrendelések száma. A következő $N$ sor mindegyike két egész számot $A, B$ $(1\le A\le B\le M)$ tartalmaz egy szóközzel elválasztva. Az állomány $i+1$-edik sorában lévő megrendelés sorszáma $i$.

Kimenet

A kimenet (szinhaz.ki) első sorába a legtöbb kielégíthető megrendelés $K$ számát kell írni! A további $K$ sor tartalmazza a jegykiosztást, minden sor két egész számot tartalmazzon egy szóközzel elválasztva. Az első szám egy megrendelés sorszáma, a második pedig azon ülőhely sorszáma, amelyet a megrendelő kap. A kiosztás kiírása tetszőleges sorrendben lehet. Ha több megoldás van, akkor egy tetszőlegeset ki lehet írni.

Példa

szinhaz.beszinhaz.ki
10 6 3 3 2 2 2 3 1 3 1 2 2 4 4 5 1 2 2 1 3 6 4

Tesztadatok