Državno natjecanje iz informatike 2021. / Druga podskupina (3. i 4. razred) – prvi dan natjecanja - 3. zadatak

Gluho je doba noći, u daljini se čuje lagani šum mora, prava idila...

„Tu tu turu tu turu tu turu tu tu”, idiličnu atmosferu prekida zvonjava telefona, oblijeva vas hladan znoj, zove gospodin Malnar:

„Čuj, treba mi niz cijelih brojeva u kojem je suma svakog intervala od a1 elemenata manja ili jednaka b1, suma svakog intervala od a2 elemenata veća ili jednaka b2,... Imaš jedan takav?

Pošalji mi najduži mogući što prije. Hvala, bok!”

Gospodin Malanar bio je jasan, napišite program koji pronalazi najduži mogući niz koji zadovoljava njegova ograničenja ili utvrdite da postoji takav beskonačan niz.

Napomena: Ograničenje određeno parametrom ai (koji označava duljinu intervala) po definiciji je zadovoljeno za svaki niz koji ima strogo manje od ai elemenata.

Shodno tome, prazan niz zadovoljava bilo kakav skup ograničenja.

Ulazni podaci

U prvom je retku prirodan broj n (2 ≤ n ≤ 100), broj ograničenja gospodina Malnara.

Svaki od sljedećih n redaka opisuje jedno ograničenje gospodina Malnara.

Svako je ograničenje oblika "ai bi <=" ili "ai bi >=" , pri čemu vrijedi 1 ≤ ai ≤ 500 i 0 ≤ |bi | ≤ 105.

Izlazni podaci

Ako postoji beskonačan niz koji zadovoljava sve uvjete gospodina Malnara, u jedini je redak potrebno ispisati −1.

U protivnom, u prvi je redak potrebno ispisati broj k, duljinu najduljeg mogućeg niza koji zadovoljava sve uvjete.

Također, u drugi je redak potrebno ispisati taj niz pri čemu njegovi elementi ne smiju po apsolutnoj vrijednosti biti veći od 109.

Ako postoji više različitih rješenja, dovoljno je ispisati bilo koje.

Moguće je dokazati da, za dana ograničenja, ako postoji neki niz duljine k koji zadovoljava sve uvjete, onda postoji i takav niz čiji elementi po apsolutnoj vrijednosti ne prelaze 109.

Primjer zadatka

Ulaz

2
5 3 >=
7 10 <=

Izlaz

-1

Ulaz

2
3 5 >=
5 -1 <=

Izlaz

6
11 -17 11 11 -17 11

Objašnjenje

Pojašnjenje drugog probnog primjera: Intervali duljine 3 su: (3, −5, 3), (−5, 3, 3), (3, 3, −5), (3, −5, 3). Sume svih ovih intervala iznose 1, stoga je prvo ograničenje zadovoljeno.

Intervali duljine 5 su: (3, −5, 3, 3, −5) i (−5, 3, 3, −5, 3), a njihove sume iznose −1. Stoga je i drugo ograničenje zadovoljeno.

Ulaz

4
7 -3 >=
4 -2 <=
7 8 <=
9 3 >=

Izlaz

8
-1 1 0 -2 -1 1 0 -2