Forth on ohjelmointikieli, jossa tietoa käsitellään pinon avulla. Tehtäväsi on laatia Forth-ohjelma, jolle annetaan luku 1 ja joka tuottaa luvun x.

Pinon sisältö voidaan esittää listana niin, että pino kasvaa vasemmalta oikealle. Esimerkiksi [1,2,3] tarkoittaa pinoa, jonka alin luku on 1, keskimmäinen luku on 2 ja ylin luku on 3. Tässä tehtävässä pinon sisältö on aluksi [1] ja ohjelman suorituksen jälkeen sisällön tulee olla [x].

Saat käyttää ohjelmassa seuraavia Forth-komentoja:

• +: korvaa pinon kaksi ylintä lukua niiden summalla
• *: korvaa pinon kaksi ylintä lukua niiden tulolla
• SWAP: vaihda keskenään pinon kaksi ylintä lukua
• DUP: lisää pinon päälle kopio ylimmästä luvusta
• OVER: lisää pinon päälle kopio toiseksi ylimmästä luvusta
• ROT: nosta pinon kolmanneksi ylin luku ylimmäksi
• DROP: poista pinon ylin luku

Ohjelman komennot suoritetaan vasemmalta oikealle. Kaikissa komennoissa oletuksena on, että pinossa on riittävästi lukuja. Esimerkiksi komentoa SWAP voi käyttää vain silloin, kun pinossa on vähintään kaksi lukua.

Syöte

Syötteenä on positiivinen kokonaisluku x.

Tuloste

Tulosta ensimmäiselle riville luku k: ohjelman komentojen määrä. Tulosta toiselle riville ohjelman komennot välilyönnein erotettuina.

Voit tulostaa minkä tahansa ratkaisun, jossa 1 \le k \le 1000.

Esimerkki

Syöte:

13

Tuloste:

15
DUP DUP + SWAP OVER OVER + ROT DUP * * OVER + SWAP DROP

Tässä tapauksessa ohjelma käsittelee pinoa seuraavasti:

1                       
1 1             DUP
1 1 1           DUP
1 2             +
2 1             SWAP
2 1 2           OVER
2 1 2 1         OVER
2 1 3           +
1 3 2           ROT
1 3 2 2         DUP
1 3 4           *
1 12            *
1 12 1          OVER
1 13            +
13 1            SWAP
13              DROP

Arvostelu

Jokaisessa testissä 1 \le x \le 100. Saat tehtävästä 100 pistettä, jos koodisi tuottaa oikean tuloksen kaikissa testeissä.