Županijska razina / Primjena algoritama OŠ 2021. / Osnovna škola (6. razred) - 3. zadatak Županijska razina / Primjena algoritama OŠ 2021. / Osnovna škola (7. razred) - 2. zadatak

Anja je pripremila N drvenih štapića raznih duljina za sutrašnju dodatnu nastavu iz matematike i određivanje vrijednosti broja Pi Buffonom metodom.

Do tada, Anja provodi nedjeljno poslijepodne igrajući s tim štapićima mikado, drevnu društvenu igru.

Na početku je iz bilježnice s kvadratićima istrgnula jedan list papira kao podlogu na koju postavlja N štapića.

Rednim brojevima je označila crte na papiru kao na slici počevši od nule iz donjeg lijevog ruba papira.

Postavljeni štapić je uvijek paralelan s jednim rubom papira.

Štapić se može postaviti tako da bude i preko nekih drugih koji su već postavljeni.

Prvi postavljeni štapić označimo s 1, drugi s 2, a zadnji postavljeni s N.

Anja sada pita starijeg brata Marina koje sve štapiće može ukloniti, a da pritom ne pomakne neki drugi štapić.

Podizanjem nekog štapića s podloge pomaknut će se svi oni štapići koji su postavljeni preko njega.

Preciznije, kažemo da je štapić s oznakom A postavljen preko štapića s oznakom B, ako je štapić s oznakom A postavljen kasnije (A > B) te pritom siječe, dodiruje ili preklapa štapić B.

Marin se ne želi osramotiti pred sestrom pa te moli da napišeš program koji za dani raspored štapića ispisuje oznake onih koji se mogu ukloniti bez pomicanja nekog drugog štapića.

Ulazni podaci

U prvom je retku prirodan broj N (1 ≤ N ≤ 100), broj iz teksta zadatka.

U sljedećih N redaka nalaze se po četiri cijela broja r1, s1, r2, s2 (0 ≤ r1, s1, r2, s2 ≤ 100), (r1, s1) i (r2, s2) predstavljaju sjecišta crta na kojima se nalaze krajevi štapića u obliku (redak, stupac).

Uvijek će vrijediti s1=s2 (za okomite postavljene štapove) ili r1=r2 (za vodoravne postavljene štapove). Štapići su zadani redom kojim ih je Anja postavljala na podlogu.

Izlazni podaci

U prvi redak ispiši koliko štapića se može ukloniti.

U drugi redak ispiši njihove oznake odvojene razmakom (u sortiranom poretku).

Primjer zadatka

Ulaz

4
5 1 5 5
7 2 2 2
2 1 2 5
4 3 6 3

Izlaz

2
3 4

Objašnjenje

Opis prvog probnog primjera: Ovo je primjer sa slike u tekstu zadatka. Štapić s oznakom 1 ne možemo ukloniti jer su štapići s oznakama 2 i 4 postavljeni preko njega. Štapić s oznakom 2 ne možemo ukloniti jer

je štapić s oznakom 3 preko njega (makar se samo dodiruju).

Ulaz

3
3 5 3 3
5 1 5 4
5 3 5 4

Izlaz

2
1 3

Ulaz

3
5 3 1 3
5 2 1 2
1 2 3 2

Izlaz

2
1 3