CSES - Datatähti 2021 loppu - Murtoviiva
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Murtoviiva koostuu nn vaakasuorasta janasta ja n1n-1 pystysuorasta janasta. Vaakasuorat janat on numeroitu järjestyksessä 1,2,,n1,2,\dots,n, ja peräkkäisiä vaakasuoria janoja yhdistää yksi pystysuora jana. Ensimmäinen vaakasuora jana kulkee vasemmalta oikealle, ja sen jälkeen seuraavat vaakasuorat janat kulkevat vuorotellen vastakkaisiin suuntiin.

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ä nn.

Toisella rivillä on nn kokonaislukua p1,p2,,pnp_1, p_2, \ldots, p_n: vaakasuorien janojen pituudet.

Viimeisellä rivillä on merkkijono, jossa on n1n-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 n1n-1 positiivista kokonaislukua: pystysuorien janojen pituudet järjestyksessä. Pituudet eivät saa olla yli 10910^9.

Esimerkki

Syöte:

4
4 3 2 3
UDD

Tuloste:

YES
3 1 1

Selitys: Kuvaan on merkitty janojen suunnat ja pituudet.

Osatehtävä 1 (7 pistettä)

  • 2n82 \le n \le 8
  • 1pi101 \le p_i \le 10

Osatehtävä 2 (19 pistettä)

  • 2n152 \le n \le 15
  • 1pi1001 \le p_i \le 100

Osatehtävä 3 (15 pistettä)

  • 2n10002 \le n \le 1000
  • 1pi21 \le p_i \le 2
  • Murtoviiva mahtuu alueelle, jonka leveys on 2.

Osatehtävä 4 (33 pistettä)

  • 2n10002 \le n \le 1000
  • 1pi1061 \le p_i \le 10^6

Osatehtävä 5 (26 pistettä)

  • 2n1052 \leq n \leq 10^5
  • 1pi1091 \leq p_i \leq 10^9