- Time limit: 1.00 s
- Memory limit: 512 MB
Murtoviiva koostuu vaakasuorasta janasta ja pystysuorasta janasta. Vaakasuorat janat on numeroitu järjestyksessä , 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ä .
Toisella rivillä on kokonaislukua : vaakasuorien janojen pituudet.
Viimeisellä rivillä on merkkijono, jossa on 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 positiivista kokonaislukua: pystysuorien janojen pituudet järjestyksessä. Pituudet eivät saa olla yli .
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ä)
Osatehtävä 2 (19 pistettä)
Osatehtävä 3 (15 pistettä)
- Murtoviiva mahtuu alueelle, jonka leveys on 2.