Državno natjecanje 2014. / Osnovna škola (7. razred) - 3. zadatak

Paula i Marin igraju novu igru. Prvo je Marin zamislio N brojeva između 1 i K, a zatim Paula daje niz izjava o tim brojevima.

Marin svaku izjavu potvrđuje s "DA" ako je točna, odnosno negira s "NE" ako je netočna.

Svaka Paulina izjava odnosi se na neki broj u Marinovom nizu.

Pravila su sljedeća:

• Njezina prva izjava odnosi se na prvi broj u Marinovom nizu.

• Kad je neka izjava točna, iduća izjava odnosi se na sljedeći broj u Marinovom nizu (ako se radilo o zadnjem broju u nizu, iduća izjava odnosi se na prvi broj).

• Kad je neka izjava netočna, iduća izjava odnosi se na prvi broj u Marinovom nizu.

Oblici izjava i njihova objašnjenja dani su u tablici:

Paula ne zna koji je niz brojeva Marin zamislio, ali je na temelju svojih izjava i njegovih odgovora odredila minimalni i maksimalni mogući niz.

Minimalni mogući niz je onaj kojem je ukupan zbroj elemenata minimalan, a koji odgovara svim izjavama i odgovorima.

Maksimalni mogući niz također odgovara svim izjavama i odgovorima, ali ukupan zbroj elemenata mu je maksimalan.

Paula želi provjeriti je li točno odredila minimalni i maksimalni niz pa je zamolila tebe da napišeš program koji će ih ispisati.

ULAZNI PODATCI

U prvom redu nalaze se tri prirodna broja: N (1 ≤ N ≤ 20), broj elemenata Marinovog niza, K (1 ≤ K ≤ 300 000), maksimalna vrijednost elemenata niza i Q (1 ≤ Q ≤ 300 000), broj Paulinih izjava.

U svakom od sljedećih Q redaka nalazi se po jedna izjava i odgovor, oblika: "operator broj odgovor" gdje je:

• operator - jedan od sljedećih stringova: ">", ">=", "<", "<=", "=";
• broj - prirodan broj manji ili jednak K;
• odgovor - jedan od sljedećih stringova: "DA", "NE".

IZLAZNI PODATCI

U prvi redak ispiši traženi minimalni mogući niz brojeva odvojenih razmacima.

U drugi redak ispiši traženi maksimalni mogući niz brojeva odvojenih razmacima.

Uvijek će postojati minimalni i maksimalni mogući niz brojeva.

PRIMJERI TEST PODATAKA

Ulaz

2 10 4
> 3 DA
<= 6 DA
< 9 DA
>= 2 DA

Izlaz

4 2
8 6

Ulaz

3 20 5
<= 7 DA
> 4 NE
= 6 DA
> 1 DA
>= 5 NE

Izlaz

6 2 1
6 4 4

Ulaz

3 15 7
= 5 NE
> 2 DA
<= 8 NE
= 15 NE
> 4 DA
< 13 DA
= 5 DA

Izlaz

6 9 5
14 12 5

Objašnjenje

Pokažimo da niz 6 9 5 odgovara izjavama i odgovorima.

6 = 5: NE, pa se iduća izjava odnosi ponovno na 6,

6 > 2: DA, pa se iduća izjava odnosi na sljedeći broj 9,

9 <= 8: NE, pa se iduća izjava odnosi na prvi broj 6,

6 = 15: NE,

6 > 4: DA,

9 < 13: DA,

5 = 5: DA.

Lako se vidi da isto vrijedi i za niz 14 12 5. Minimalnost i maksimalnost provjerite sami.