CSES - Datatähti 2017 loppu - Ohjelma
  • Time limit: 0.50 s
  • Memory limit: 512 MB

Uolevi on kehittänyt uuden ohjelmointikielen, jossa ohjelmassa on vain yksi muuttuja XX. Ohjelman suorituksen alussa XX:n arvo on 11. Kielessä on kolme komentoa:

  • ADD: lisää XX:n arvoon 3
  • MUL: kerro XX:n arvo 2:lla
  • END: tulosta XX:n arvo ja lopeta ohjelma

Tehtäväsi on etsiä lyhin ohjelma, joka tulostaa luvun nn, tai todeta, että mitään tällaista ohjelmaa ei ole olemassa.

Syöte

Syötteen ainoalla rivillä on kokonaisluku nn.

Tuloste

Jos ohjelma on olemassa, tulosta ensin sen komentojen määrä ja sen jälkeen jokainen komento omalle rivilleen. Jos mahdollisia ohjelmia on useita, voit tulostaa niistä minkä tahansa.

Jos ohjelmaa ei ole olemassa, tulosta vain luku 00.

Esimerkki 1

Syöte:

10

Tuloste:

4
MUL
ADD
MUL
END

Esimerkki 2

Syöte:

12

Tuloste:

0

Osatehtävä 1 (21 pistettä)

  • 1n1001 \le n \le 100

Osatehtävä 2 (37 pistettä)

  • 1n1061 \le n \le 10^6

Osatehtävä 3 (42 pistettä)

  • 1n10181 \le n \le 10^{18}