== include(page="template/taskheader" task_id="slang") ==
Poveste și cerință...
!>problema/slang?slang1.jpg!
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 alăturată.
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:
!problema/slang?slang2.jpg!
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.
!problema/slang?slang3.jpg!
h2. Cerință
Dat fiind numărul natural [$K$], reprezentând nivelul de imbricare, scrieți un program care să rezolve următoarele cerințe:
1. determină numărul de programe corecte distincte cu nivelul de imbricare [$K$];
2. 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$].
h2. Date de intrare
Fișierul de intrare $slang.in$ ...
Fișierul de intrare $slang.in$ conține pe prima linie un număr natural $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.
h2. Date de ieșire
În fișierul de ieșire $slang.out$ ...
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$].
h2. Restricții
* $... ≤ ... ≤ ...$
* $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 6 cifre cerute, este nenulă.
* Pentru rezolvarea corectă a fiecărei cerințe se acordă 50 de puncte.
h2. Exemplu
table(example).
|_. slang.in |_. slang.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. slang.in |_. slang.out |_. Explicații |
| 1
0
| 8674
| Cerința este 1.
Există 8674 de programe corecte distincte cu nivelul de imbricare 0. |
| 2
0
| 3 12
| 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:
!problema/slang?slang4.jpg!
Numărul maxim de instrucțiuni dintr-un program corect cu nivelul de imbricare 0 este 12. Un exemplu de astfel de program este:
!problema/slang?slang5.jpg! |
== include(page="template/taskfooter" task_id="slang") ==
