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

Mirko je Slavku pokazao svojih N tornjeva koje je izgradio od lego kocaka.

Svaki toranj sastavljen je od nekog broja kocaka posloženih jedna na drugu, a svaka kocka na sebi ima napisan jedan broj.

Odjednom je Mirko rekao Slavku da će napraviti M operacija nad tim tornjevima.

U i-toj od tih operacija će uzeti gornjih xi kocaka s ai-tog tornja te ih staviti na vrh bi-tog tornja.

Brojevi ai i bi mogu biti isti te će Mirko tada kocke staviti na isti toranj s kojeg ih je i uzeo.

Također, nakon operacije toranj može ostati prazan, ali on još uvijek postoji i na njega se mogu stavljati kocke.

Primijetivši da Slavko i nije nešto zainteresiran, Mirko mu je odlučio zadati posao.

Dogovorili su se da će Slavko za svaku operaciju odrediti na koji način će Mirko uzetih xi kocaka s ai-tog tornja postaviti na bi-ti toranj.

Može izabrati da ih sve odjednom uzme s ai-tog te ih zajedno prenese na bi-ti ili može izabrati da prenosi jednu po jednu kocku. Ilustracija prikazuje prebacivanje četiri kocke na oba načina.

U gornjem načinu su sve kocke prenesene zajedno, a u donjem je prvo prenesena narančasta (2), zatim plava (5), onda zelena (1) i na kraju žuta kocka (7).

Budući da Slavko još uvijek nije dobio interes, Mirko mu je zadao Q upita da ga zabavi.

U j-tom upitu ga je Mirko upitao može li izabrati načine obavljanja prijenosa kocaka za svaku operaciju tako da se na kraju na uj-toj kocki odozgo u tj-tom tornju nalazi broj vj.

Upiti su nezavisni, odnosno početni izgled tornjeva u svakom upitu je jednak.

Ulazni podaci

U prvom su retku tri prirodna broja N, M i Q (1 ≤ N ≤ 10, 1 ≤ M ≤ 100, 1 ≤ Q ≤ 10), brojevi iz teksta zadatka. U drugom je retku N prirodnih brojeva hi (1 ≤ hi ≤ 100), gdje i-ti broj označava početni broj kocaka u itom tornju.

U i-tom od sljedećih N redaka je po hi prirodnih brojeva oj (1 ≤ oj ≤ 109) koji označavaju početno stanje i-tog tornja.

Prvi broj u i-tom retku označava broj na prvoj kocki odozgo u i-tom tornju, drugi broj označava broj na drugoj kocki odozgo u i-tom tornju itd.

U j-tom od sljedećih M redaka su po tri prirodna broja aj, bj i xj (1 ≤ aj ≤ N, 1 ≤ bj ≤ N, 1 ≤ xj ≤ 109), brojevi iz teksta zadatka.

Garantirano je da će se u tornju aj nakon svih prijašnjih operacija nalaziti barem xj kocaka.

U k-tom od sljedećih Q redaka su po tri prirodna broja tk, uk i vk (1 ≤ tk ≤ N, 1 ≤ uk ≤ 1000, 1 ≤ vk ≤109), brojevi iz teksta zadatka.

Garantirano je da će se na kraju svih operacija u tornju tk nalaziti barem uk kocaka.

Izlazni podaci

Ispiši Q redaka gdje je u k-tom od njih riječ “DA” ako je odgovor na k-ti upit pozitivan, odnosno riječ “NE” ako je negativan.

Primjer zadatka

Ulaz

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

Izlaz

NE
DA
DA

Objašnjenje

Opis prvog probnog primjera: Pomoću dvije operacije koje imamo ne možemo dovesti broj 3 na prvo mjesto jedinog tornja pa je prvi odgovor NE. Ako u obje operacije kocke preslagujemo jednu po jednu, tada će konačan izgled tornja biti 4 5 3 2 1 pa je odgovor na drugo pitanje DA. Ako samo u prvoj operaciji kocke preslagujemo jednu po jednu, tada ćemo na prvom mjestu dobiti broj 5 te je zato odgovor na treće pitanje DA.

Ulaz

3 2 2
1 1 1
3
2
3
1 2 1
3 2 1
2 1 3
2 2 2

Izlaz

DA
NE

Objašnjenje

Opis drugog probnog primjera: Postoji samo jedna mogućnost za izgled tornjeva na kraju, a to je da su

prvi i treći prazni, a drugi 3 1 2.

Ulaz

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

Izlaz

DA
DA
NE