CSES - Datatähti 2016 alku - Bittipeli
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Bittipelissä annettuna on bittijono, jossa on n bittiä. Bittijono jakautuu jaksoihin, joissa jokainen bitti on sama. Esimerkiksi bittijono 1110100011 jakautuu jaksoihin 111, 0, 1, 000 ja 11.

Joka siirrolla saat poistaa bittijonosta minkä tahansa jakson, jossa on vähintään kaksi bittiä. Jos onnistut lopulta poistamaan kaikki bitit, olet voittanut pelin. Jos et voi poistaa mitään jaksoa, olet hävinnyt pelin.

Sinulle on annettu bittipelin aloitustilanne, ja tehtäväsi on selvittää, onko pelin voittaminen mahdollista. Jos voittaminen on mahdollista, sinun täytyy lisäksi esittää yksi voittoon johtava siirtosarja.

Syöte

Syötteen ainoalla rivillä on merkkijono, joka muodostuu merkeistä 0 ja 1.

Tuloste

Jos voit poistaa kaikki bitit, sinun tulee tulostaa yksi esimerkki ratkaisusta. Ensimmäisellä rivillä tulee olla kokonaisluku k: siirtojen määrä. Seuraavalla rivillä tulee olla k lukua, jotka kuvaavat siirron. Jokainen luku kertoo, monesko vähintään kahden bitin jakso poistetaan.

Jos mitään ratkaisua ei ole olemassa, sinun tulee tulostaa QAQ.

Esimerkki 1

Syöte:

10011101

Tuloste:

3
2 1 1

Selitys: Poistat ensin jakson 111, jolloin jäljelle jää 10001. Tämän jälkeen poistat jakson 000, jolloin jäljelle jää 11. Lopuksi poistat jakson 11 ja olet voittanut pelin.

Esimerkki 2

Syöte:

10010101

Tuloste:

QAQ

Osatehtävä 1 (11 pistettä)

  • 1 \le n \le 10

Osatehtävä 2 (27 pistettä)

  • 1 \le n \le 100

Osatehtävä 3 (28 pistettä)

  • 1 \le n \le 5000

Osatehtävä 4 (34 pistettä)

  • 1 \le n \le 10^5