Školska razina 2022 / Osnovna škola (8. razred) - 3. zadatak

Ivani je dosadno. Preko Glova je naručila po dva lista papira u svakoj od N zadanih različitih boja. Listovi papira mogu biti različitih dimenzija. Kada je dostava stigla, Ivana je od svake boje uzela po jedan list te ih počela slagati jedan na drugi.

Točnije, papir neke boje postavi na podlogu. Zatim papir neke druge boje postavi na prvi ali tako da je cijeli unutar njega, da su rubovi drugog paralelni s rubovima prvog i da rubovi drugog ne dodiruju/presijecaju rubove papira neposredno ispod. I tako za svaki sljedeći papir koji još treba složiti. Vidi sliku.

Napiši program koji za zadane ulazne podatke određuje i za svaku boju ispisuje redni broj lista papira koji Ivana treba odabrati da bi ih sve mogla složiti na način na koji to želi.

Ulazni podaci

U prvom je retku prirodan broj N (2 ≤ N ≤ 5), broj iz teksta zadatka.

U sljedećih N redaka nalaze se po četiri prirodna broja D1, S1, D2 i S2 (1 ≤ Si ≤ Di ≤ 20), duljina i širina prvog lista te duljina i širina drugog lista u i-toj od N zadanih boja

Izlazni podaci

U N redaka treba za svaku boju redom kojim su zadane u ulaznim podacima ispisati oznaku (1 ili 2) papira koji Ivana treba odabrati. Rješenje će biti jedinstveno

Primjeri test podataka

Ulaz

2
3 1 2 2
3 3 3 2

Izlaz

2
1

Ulaz

3
1 1 3 3
3 2 4 3
2 2 3 1

Izlaz

1
2
1

Objašnjenje

Ako odaberemo prvi papir prve boje, drugi papir druge boje i prvi papir treće boje, možemo na papir druge boje staviti papir treće boje i potom na vrh staviti papir prve boje.

Ulaz

2
5 5 7 4
8 3 6 6

Izlaz

1
2