Paul dorește să învețe cum să programeze un robot. Pentru început s-a gândit să construiască un robot format dintr-un mâner, 10 butoane aranjate circular şi un ecran. Pe butoane sunt scrise, în ordine crescătoare, cifrele de la 0 la 9, ca în figură.
Un roboprogram va fi format dintr-o secvenţă de instrucţiuni. Instrucțiunile pot fi:
Dp
Mânerul robotului se deplasează spre dreapta cu p poziţii (p este o cifră)
Sp
Mânerul robotului se deplasează spre stânga cu p poziţii (p este o cifră)
A
Este apăsat butonul în dreptul căruia se află mânerul robotului şi pe ecran apare cifra scrisă pe buton
T
Terminarea programului (se utilizează o singură dată la final şi este precedată de cel puţin o instrucțiune A)
Iniţial mânerul robotului este plasat în dreptul butonului 0, iar ecranul este gol.
De exemplu, în urma executării roboprogramului D4AS1AAD6AT robotul apasă butoanele pe care sunt scrise cifrele 4, 3, 3, 9, iar pe ecran va apărea 4339.
Cerinţă
Să se scrie un program care rezolvă următoarele cerinţe:
1. citeşte un roboprogram şi determină numărul de cifre afişate pe ecran după executarea roboprogramului;
2. citeşte un roboprogram şi determină cifrele afişate pe ecran după executarea roboprogramului;
3. citeşte un număr natural N şi construieşte un roboprogram de lungime minimă prin executarea căruia pe ecran se va obţine numărul N; dacă există mai multe roboprograme de lungime minimă, se va construi unul pentru care suma deplasărilor mânerului robotului este minimă; dacă şi în acest caz există mai multe soluţii, deoarece robotului îi place să se deplaseze în special spre dreapta, se va afişa roboprogramul cu număr maxim de instrucţiuni D.
Date de intrare
Fişierul de intrare
robot6.in conţine pe prima linie un număr natural C, reprezentând cerinţa care urmează să fie rezolvată (1, 2 sau 3). Dacă C=1 sau C=2, pe a doua linie a fişierului se află un roboprogram. Dacă C=3, pe a doua linie a fişierului de intrare se află numărul natural N.
Date de ieşire
Fişierul de ieşire
robot6.out va conţine o singură linie. Dacă C=1, pe prima linie se va scrie un număr natural reprezentând numărul de cifre afişate pe ecran după executarea roboprogramului din fişierul de intrare.
Dacă C=2, pe prima linie vor fi scrise cifrele afișate pe ecran în urma executării roboprogramului din fişierul de intrare. Dacă C=3, pe prima linie va fi scris roboprogramul solicitat de cerinţa 3.
Restricţii
• 0 ≤ N ≤ 1000000000
• Lungimea roboprogramului citit din fişierul de intrare sau scris în fişierul de ieşire este cel mult 1000 de caractere.
• Dacă mânerul este plasat în dreptul butonului 0 şi se deplasează spre dreapta, se va îndrepta către butonul 1; dacă deplasarea este spre stânga, se va îndrepta către butonul 9.
Exemple
robot6.in | robot6.out | Explicaţii |
1
D1AD2AS1AT
| 3
| C=1, pentru acest test se rezolvă cerința 1.
Se afişează pe ecran 3 cifre (132)
|
2
S0AD2AS1AT
| 021
| C=2, pentru acest test se rezolvă cerința 2.
Mânerul robotului se deplasează cu 0 unități la stânga, deci rămâne în dreptul butonului 0 și apasă, apoi se deplasează 2 unități spre dreapta şi ajunge în dreptul butonului 2, apasă, apoi se deplasează 1 unitate la stânga și ajunge în dreptul butonului 1 și apasă acest buton 021.
|
3
19332
| D1AS2AD4AAS1AT
| C=3, pentru acest test se rezolvă cerința 3. Pentru a afișa cifra 1, mânerul robotului se deplasează 1 unitate la dreapta după care apasă (D1A). Pentru a afișa cifra 9, din poziția curentă mânerul robotului se deplasează 2 unități la stânga şi apasă (S2A). Pentru a afișa cifra 3, din poziția curentă mânerul robotului se deplasează 4 unități la dreapta după care apasă (D4A). Pentru a afișa a doua cifra 3, mânerul robotului rămâne în poziția curentă și apasă butonul. Pentru a afișa cifra 2, din poziția curentă mânerul robotului se deplasează 1 unitate la stânga după care apasă (S1A). Programul se termină cu instrucțiunea T D1AS2AD4AAS1AT |