Lista de probleme 3

Se consideră modelul unui sistem solar format din N planete care se rotesc în jurul unei stele S, în sens trigonometric. Traiectoriile planetelor se consideră circulare și de raze diferite, iar vitezele de rotație ale planetelor în jurul stelei sunt numere naturale și sunt exprimate în grade pe zi (⁰/zi).

Cunoscând numărul de planete N și vitezele lor de rotație Vi, 1≤i≤N precum și două numere naturale P și Z, să se determine numărul A de alinieri a câte minimum P planete, pe o dreaptă ce trece prin centrul stelei S, după trecerea celor Z zile. Evoluția sistemului solar începe cu toate planetele așezate orizontal, în dreapta stelei S.

În clasa lui Dexter sunt N elevi de înălțimi distincte. La ora de sport, ei sunt așezați în linie, de la stânga la dreapta. Profesorul lor, Johnny, va selecta pentru un exercițiu elevi aflați pe poziții consecutive în linie, astfel încât cel mai înalt elev dintre cei selectați să se afle în prima jumătate a acestora.

De exemplu, dacă elevii au, în ordine, înălțimile 1, 5, 4, atunci profesorul poate să îi selecteze pe cei cu înălțimile 5 și 4, dar nu poate să îi selecteze pe cei cu înălțimile 1 și 5. Desigur, există mai multe moduri de a selecta elevii astfel încât să fie satisfăcută condiția de mai sus. Profesorul Johnny ar vrea să afle în câte moduri se poate face acest lucru.

Dându-se N și înălțimile elevilor din clasă, aflați în câte moduri pot fi selectați oricâți elevi aflați pe poziții consecutive, astfel încât să fie îndeplinită condiția din enunț.

Dexter și-a definit propriul algoritm de arhivare a șirului favorit T, șir format numai din litere mici ale alfabetului englez. Șirul arhivat, notat cu S, poate fi format din cifre, litere mici ale alfabetului englez, parantezele drepte '[' și ']' și parantezele rotunde '(' și ')', precum și caractere '*'.

Fixi, curios din fire, descoperă algoritmul și încearcă să dezarhiveze șirul S, prin efectuarea unor transformări repetate. O transformare poate fi de unul dintre cele 3 tipuri de mai jos, unde s-a notat cu C o secvență din S formată numai din litere.

1. O secvență a lui S de forma n(C), unde n este numărul natural poziționat imediat înaintea parantezei rotunde, se transformă într-o secvență D obținută prin scrierea concatenată, de n ori, a șirului C. Exemplu: pentru secvența 10(ab) avem n=10 și se obține secvența D=abababababababababab.
2. O secvență a lui S de forma [*C] se transformă într-o secvență palindromică de lungime pară, obținută prin concatenarea secvenței C cu oglinditul lui C. Exemplu: din secvența [*abc] se obține secvența palindromică de lungime pară abccba
3. O secvență a lui S de forma [C*] se transformă într-o secvență palindromică de lungime impară, obținută prin concatenarea secvenței C cu oglinditul lui C din care s-a eliminat primul caracter. Exemplu: din secvența [abc*] se obține secvența palindromică de lungime impară abcba.

Un șir se consideră dezarhivat dacă este format numai din litere mici ale alfabetului englez.

Fiind dat șirul arhivat S să se determine numărul de transformări, de cele 3 tipuri de mai sus, realizate de Fixi în cadrul algoritmului de dezarhivare, precum și forma finală dezarhivată T a șirului S.