Candale Silviu (silviu) SLang este o versiune a aplicației Scratch care pune la dispoziție șapte instrucțiuni de tip I1, I2, I3, I4, I5, I6, I7 prezentate în imaginea de mai jos.
Un program corect este o succesiune de instrucţiuni care respectă următoarele reguli:
1. Începe cu o instrucțiune de tip I1 şi se termină cu o instrucțiune de tip I7.
2. Între instrucţiunea de tip I1 şi instrucţiunea de tip I7 vor exista una, două sau mai multe instrucţiuni de tipurile I2, I3, I4, I5 sau I6, fără a utiliza două instrucţiuni de acelaşi tip; fiecare dintre aceste instrucţiuni poate să conţină alte instrucţiuni, conform cu regulile specificate.
3. Corpul unei instrucțiuni de tip I4 poate conține una sau două instrucțiuni de mișcare (adică de tip I2 sau I3) și nu poate conține instrucțiuni de alt tip. De exemplu:
4. Fiecare dintre cele două ramuri ale unei instrucțiuni de tip I5 (ramura daca şi ramura daca nu) poate conține una sau două instrucțiuni de tip I2 sau I3 și nu poate conține instrucțiuni de alt tip.
5. Corpul unei instrucțiuni de tip I6 poate conține una, două sau mai multe instrucţiuni de tipurile I2, I3, I4, I5 sau I6, fără a utiliza două instrucţiuni de acelaşi tip; similar, fiecare dintre aceste instrucţiuni poate să conţină alte instrucţiuni, conform cu regulile specificate.
Nivelul de imbricare al unui program corect va fi egal cu numărul de instrucţiuni de tip I6 existente în program.
Exemplu de program corect cu trei instrucțiuni de tip I6 (program cu nivelul de imbricare 3). |
Exemplu de program incorect deoarece o instrucțiune de tip I5 nu poate conține o instrucțiune de tip I6. |
 |
 |
Cerința
Dat fiind numărul natural K, reprezentând nivelul de imbricare, scrieţi un program care să rezolve următoarele cerinţe:
- determină numărul de programe corecte distincte cu nivelul de imbricare
K; - determină numărul minim de instrucțiuni și respectiv numărul maxim de instrucțiuni ce pot exista într-un program corect cu nivel de imbricare
K.
Date de intrare
Fișierul de intrare slang.in conține pe prima linie numărul c reprezentând cerinţa care trebuie să fie rezolvată (1 sau 2). Pe cea de a doua linie se află numărul natural K, reprezentând nivelul de imbricare.
Date de ieșire
Dacă c=1, atunci se va rezolva numai cerința 1, caz în care pe prima linie a fișierului slang.out va fi scris un număr natural reprezentând ultimele șase cifre ale numărului de programe corecte distincte care au nivelul de imbricare K.
Dacă c=2, atunci se va rezolva numai cerința 2. În acest caz, fișierul de ieșire slang.out va conține pe prima linie două numere naturale separate printr-un spațiu, reprezentând numărul minim de instrucțiuni, respectiv numărul maxim de instrucțiuni ale unui program corect cu nivel de imbricare K.
Restricții și precizări
0 ≤ K ≤ 1000- Două programe sunt distincte dacă în succesiunile de instrucţiuni corespunzătoare există cel puţin o poziţie pe care se află instrucţiuni de tipuri diferite.
- Se garantează că, pentru datele de test, prima dintre cele
6cifre cerute, este nenulă. - Pentru rezolvarea corectă a fiecărei cerinţe se acordă 50 de puncte.
Exemplul 1
slang.in
1 0
slang.out
8674
Explicație
Cerinţa este 1.
Există 8674 de programe corecte distincte cu nivelul de imbricare 0.
Exemplul 2
slang.in
2 0
slang.out
3 12
Explicație
Cerinţa este 2.
Numărul minim de instrucţiuni dintr-un program corect cu nivelul de imbricare 0 este 3. Un exemplu de astfel de program este:
Numărul maxim de instrucţiuni dintr-un program corect cu nivelul de imbricare 0 este 12. Un exemplu de astfel de program este:
