- Time limit: 1.00 s
- Memory limit: 512 MB
Tiedossa on vaakasuorien janojen pituudet sekä pystysuorien janojen suunnat, mutta ei pystysuorien janojen pituuksia. Voidaanko pystysuorien janojen pituudet valita niin, että murtoviiva ei leikkaa itseään?
Syöte
Ensimmäisellä rivillä on yksi kokonaisluku: vaakasuorien janojen määrä $n$.
Toisella rivillä on $n$ kokonaislukua $p_1, p_2, \ldots, p_n$: vaakasuorien janojen pituudet.
Viimeisellä rivillä on merkkijono, jossa on $n-1$ merkkiä. Jokainen merkki ilmaisee pystysuoran janan suunnan: U (ylöspäin) tai D (alaspäin).
Tuloste
Tulosta ensimmäiselle riville YES, jos ratkaisu on olemassa, ja muuten NO.
Jos ratkaisu on olemassa, tulosta seuraavalle riville $n-1$ positiivista kokonaislukua: pystysuorien janojen pituudet järjestyksessä. Pituudet eivät saa olla yli $10^9$.
Esimerkki
Syöte:
4
4 3 2 3
UDD
Tuloste:
YES
3 1 1
Selitys: Kuvaan on merkitty janojen suunnat ja pituudet.
- $2 \le n \le 8$
- $1 \le p_i \le 10$
- $2 \le n \le 15$
- $1 \le p_i \le 100$
- $2 \le n \le 1000$
- $1 \le p_i \le 2$
- Murtoviiva mahtuu alueelle, jonka leveys on 2.
- $2 \le n \le 1000$
- $1 \le p_i \le 10^6$
- $2 \leq n \leq 10^5$
- $1 \leq p_i \leq 10^9$