CSES - Datatähti 2018 loppu - Pinopeli
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Justiina ja Kotivalo pelaavat peliä, jonka alkutilanteessa on n pinoa kolikkoja ja valittu parametri a. Justiina aloittaa pelin, ja pelaajat tekevät siirtoja vuorotellen. Pelin voittaja on se, joka tekee viimeisen siirron.

Jokaisella siirrolla pelaaja valitsee yhden pinoista ja poistaa siitä haluamansa määrän kolikkoja. Tämän jälkeen hän ottaa poistetuista itselleen 1 \ldots a kolikkoa ja jakaa loput poistetut kolikot takaisin peliin. Jokaisen kolikon voi laittaa joko mihin tahansa olemassa olevaan pinoon tai uuden pinon ensimmäiseksi kolikoksi.

Voiko Justiina voittaa pelin, jos hän pelaa optimaalisesti? Entä mikä on mahdollinen optimaalinen aloitussiirto?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja a: pinojen määrä ja parametri a.

Seuraavalla rivillä on n kokonaislukua p_1,p_2,\ldots,p_n: kolikkojen määrä kussakin pinossa.

Tuloste

Tulosta ensin "YES", jos Justiina voittaa varmasti, ja "NO" muuten.

Jos Justiina voittaa, tulosta sitten esimerkki, miten hän voi tehdä aloitussiirtonsa. Tulosta ensin kaksi riviä, joista ensimmäinen on muotoa "TAKE x y" ja toinen on muotoa "KEEP z". Tämä tarkoittaa, että Justiina ottaa y kolikkoa pinosta, jossa on x kolikkoa, ja pitää niistä itsellään z kolikkoa. Tulosta sitten haluamasi määrä rivejä muotoa "ADD x y". Tämä tarkoittaa, että Justiina laittaa y kolikkoa pinoon, jossa on valmiina x kolikkoa. On sallittua, että x=0, jolloin syntyy uusi pino. Tulosta lopuksi rivi "END", joka lopettaa siirron kuvauksen.

Esimerkki 1

Syöte:

3 2
1 3 2

Tuloste:

YES
TAKE 3 3
KEEP 2
ADD 1 1
END

Selitys: Justiina poistaa kaikki kolikot pinosta, jossa on kolme kolikkoa. Sitten hän pitää kaksi kolikkoa itsellään ja lisää yhden kolikon pinoon, jossa on valmiina yksi kolikko. Siirron jälkeen pelissä on kaksi pinoa, joissa kummassakin on kaksi kolikkoa.

Esimerkki 2

Syöte:

3 1
1 3 2

Tuloste:

NO

Osatehtävä 1 (17 pistettä)

  • 1 \le n \le 5
  • 1 \le a \le 2
  • 1 \le \sum p_i \le 5

Osatehtävä 2 (22 pistettä)

  • 1 \le n \le 20
  • 1 \le a \le 5
  • 1 \le \sum p_i \le 20

Osatehtävä 3 (61 pistettä)

  • 1 \le n \le 500
  • 1 \le a \le 500
  • 1 \le p_i \le 500