Državno natjecanje 2017. / Osnovna škola (5. razred) - 3. zadatak

Mali Bojan Trumpy izgradio je zid. Koliko god to bilo stereotipno, sada će ga obojiti.

Zid je podijeljen na N vertikalnih stupaca jednake širine koji su označenim brojevima od 1 do N slijeva nadesno.

U nekim stupcima se može nalaziti prozor i te stupce Bojan neće bojiti.

Bojan je zid bojio u K koraka. Svaki korak bojenja radio je na sljedeći način:

• Prvo je odabrao tri prirodna broja – A, B i X. Brojevi A i B predstavljaju lijevi i desni kraj niza uzastopnih stupaca koji će Bojan bojiti. Broj X je količina boje na kistu. Ako je količina boje na kistu jednaka X, Bojan može nanijeti X mm boje na zid.

• Nakon što je odabrao brojeve, Bojan nanosi boju između stupaca A i B povlačeći kist slijeva nadesno pa zdesna nalijevo sve dok mu ne nestane boje na kistu. Kada povlači kist slijeva nadesno, nanosi 1 mm boje redom na sve stupce od A-tog do B-tog (preskačući prozore), a kada ga povlači zdesna nalijevo, nanosi 1 mm boje redom na sve stupce od B-tog do A-tog (također preskačući prozore). Radi boljeg razumijevanja Bojanovog postupka, proučite opise test podataka.

Vaš je zadatak odrediti broj milimetara boje na svakom stupcu zida nakon što Bojan napravi svih K koraka bojenja.

ULAZNI PODATCI

U prvom retku nalazi se prirodan broj N (1 ≤ N ≤ 100), broj stupaca u koje je Bojan podijelio zid.

U drugom retku nalazi se niz od N brojeva koji opisuju stupce zida. Broj 1 predstavlja stupac koji možemo bojiti, a broj 0 predstavlja prozor.

U trećem retku nalazi se prirodan broj K (1 ≤ K ≤ 100), broj koraka bojenja koje je Bojan napravio.

U svakom od sljedećih K redaka nalaze se tri prirodna broja, A, B i X (1 ≤ A ≤ B ≤ N, 1 ≤ X ≤ 1 000 000 000) koji opisuju korak bojenja.

U nizu stupaca od A-tog do B-tog postojat će barem jedan stupac u kojem se ne nalazi prozor.

IZLAZNI PODATCI

U prvi i jedini redak izlaza ispišite N brojeva, broj milimetara boje na svakom od stupaca zida.

PRIMJERI TEST PODATAKA

Ulaz

6
1 1 1 1 1 1
4
1 3 5
2 4 6
3 6 2
1 6 11

Izlaz

2 6 7 5 2 2

Objašnjenje

Opis prvog test podatka: Osobe na poziciji 2 (11:12:59) i 3 (11:19:33) nezadovoljne su jer je osoba na poziciji 1 (12:05:01) došla kasnije, a stoji ispred njih.

Ulaz

9
1 0 1 1 1 0 1 1 0
3
1 5 7
7 8 4
1 2 3

Izlaz

4 0 2 2 2 0 2 2 0

Ulaz

7
1 1 1 1 1 1 1
3
1 5 500000000
3 7 600000000
1 7 900000000

Izlaz

228571429
228571429
348571429
348571429
348571428
248571428
248571428

Objašnjenje

Opis drugog test podatka: U prvom potezu Bojan boji stupce 1, 3, 4 i 5 (2 preskače jer je tamo prozor), zatim mijenja smjer i boji stupce 5, 4 i 3. Nakon toga mu nestaje boje na kistu i prestaje bojiti.

U drugom potezu boji stupce 7 i 8, zatim mijenja smjer pa boji stupce 8 i 7, te mu nakon toga ponestaje boje na kistu.

U trećem će potezu bojiti samo stupac broj 1 tri puta jer je on jedini u odabranom podnizu koji ne sadrži prozor.

Ulaz

8
1 0 1 0 1 0 1 0
2
1 6 10
3 6 11

Izlaz

3 0 8 0 10 0 0 0

Objašnjenje

Opis trećeg test podatka: U ovom test podatku Bojan radi mnogo poteza kistom.

Obratite pažnju na vrijeme izvršavanja vašeg programa.

Program koji simulira bojenje korak po korak možda se neće izvršiti unutar 2 sekunde.

Pazi, u ovom prikazu izlaznih podataka zbog manjka prostora ispis je prikazan u više redaka.