Az I/S. 42. feladat (2020. február)

I/S. 42. Egy út mindkét oldalán kilométerenként található egy-egy kilométerkő. \(\displaystyle N\) csirke szeretne átkelni az út egyik (ugyanazon) oldaláról a másikra. Mindegyikről tudjuk, hogy melyik kilométerkőtől indul és melyik kilométerkőhöz érkezik. Minden kilométerkőtől legfeljebb egy csirke indul és minden kilométerkőhöz legfeljebb egy csirke érkezik. Ha két csirke útvonala keresztezi egymást, akkor találkozhatnak, összezavarodnak és esetleg nem érnek célba. Adjuk meg, hány csirke útja biztonságos, tehát hányat nem fenyeget a keresztezésből adódó veszély.

Bemenet: az első sor tartalmazza a csirkék \(\displaystyle N\) számát. A következő \(\displaystyle N\) sor mindegyike két számot tartalmaz, mely azt jelenti, hogy az \(\displaystyle i\)-edik csirke az \(\displaystyle A_{i}\) kilométerkőtől indul és a \(\displaystyle B_{i}\) kilométerkőhöz érkezik.

Kimenet: az első sor tartalmazza azon csirkék számát, amelyek biztonságosan át tudnak kelni az úton.

Példa:

Korlátok: \(\displaystyle 1\le N\le {10}^{5}\), \(\displaystyle 1\le A_{i}, B_{i}\le {10}^{9}\). Időkorlát: 0,3 mp.

Értékelés: a pontok 50%-a kapható, ha \(\displaystyle N\le 10\,000\).

Beküldendő egy is42.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2020. március 10-én LEJÁRT.

Statisztika:

7 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Mócsy Mátyás, Varga 256 Péter.
9 pontot kapott:	Szente Péter.
5 pontot kapott:	1 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2020. februári informatika feladatai