DRŽAVNO NATJECANJE 2013. – Drugi dan natjecanja / Srednja škola, I. podskupina (1. i 2. razred) - 1. zadatak

Matija je, hodajući pustinjom, naišao na N kaktusa izraslih u dugačkom redu.

Dok je prolazio kraj njih, kaktusi su progovorili, a prvi kaktus u redu postavio mu je zanimljivu zagonetku: “Putniče!

Godinama stojimo na istom mjestu, tiho brojeći zalaske sunca i prolaske godišnjih doba.

Svake godine, nakon najhladnijih dana, među nama se nečujno pojavi točno jedna nova mladica, koja ubrzo izraste u predivan i visok kaktus.

Među nas N nalaze se kaktusi raznolikog iskustva: neki su vidjeli tek jedno ljeto, dok ih se neki prisjećaju velik broj, ali među nama ne postoje dva kaktusa koju su jednako dugo na ovom svijetu.

Ako ti kažem da sam vidio pojavu točno K mladica u ovom redu, a svi ostali kaktusi ti kažu samo jesu li vidjeli pojavu kaktusa koji im se nalazi neposredno s lijeve strane, možeš li odrediti koliko je svaki od nas zima iskusio?”

Drugim riječima starost kaktusa je niz od N različitih prirodnih brojeva od 1 do N – i-ti broj je starost i-tog po redu kaktusa u godinama redom s lijeva na desno.

Za prvi kaktus je poznat broj K – ukupan broj kaktusa koji su mlađi od njega.

Za svaki od ostalih kaktusa poznato je jesu li stariji ili mlađi od kaktusa neposredno lijevo od njih.

Napiši program koji na temelju tih informacija određuje starost svih kaktusa.

Test podaci će biti takvi da rješenje uvijek postoji iako ne mora biti jedinstveno.

Ukoliko postoji više rješenja potrebno je pronaći i ispisati bilo koje.

Ulazni podaci

U prvom retku ulaza nalaze se dva prirodna broja N i K (2 ≤ N ≤ 100, 0 ≤ K < N), broj kaktusa u redu i broj kaktusa mlađih od prvog kaktusa.

U drugom retku nalazi se niz od N-1 znakova, svaki znak je veliko slovo 'D' ili 'N'.

Ukoliko je prvi znak u retku 'D', to znači da je drugi kaktus stariji od prvog kaktusa, i tako dalje.

Točnije, i-ti po redu znak će biti 'D' ako je i+1-ti kaktus stariji od i-tog, inače 'N'.

Izlazni podaci

U prvi i jedini redak potrebno je ispisati N brojeva koji predstavljaju neki mogući raspored starosti kaktusa u godinama – i-ti po redu broj mora biti starost u godinama i-tog po redu kaktusa s lijeva.

Primjeri test podataka

Ulaz

6 5
NNDND

Izlaz

6 5
NNDND

Ulaz

8 5
NNNDNDN

Izlaz

6 5 4 1 8 2 7 3