Diferențe pentru problema/gigel între reviziile #32 si #43

== include(page="template/taskheader" task_id="gigel") ==

Gigel a găsit prin sertarul bunicii un bilețel pe care scria o formulă de decodificare a unui șir de caractere **[$s$]** de lungime cel mult $1.000.000$ ce conține numere naturale nenule (le vom nota cu $x[~k~]$), $[ ]$ (paranteze pătrate), ${ }$ (acolade), $< >$ (paranteze unghiulare) și $,$ (virgulă) . Acest șir are următoarele reguli de decodificare pentru fiecare subșir **s[~k~]** care începe cu $[$, ${$ sau $<$ și se termină cu $]$, $}$ sau $>$:
1) Dacă $**s[~k~]** = "[x[~1~], x[~2~], x[~3~], ..., x[~p~]]"$, atunci **$s[~k~]$** se transformă într-un număr întreg $t = (x[~1~]^-1^ + x[~2~]^-1^ + x[~3~]^-1^ + ... + x[~p~]^-1^)$% 773; (suma inverselor modulare ale numerelor $x[~1~], x[~2~], x[~3~], ..., x[~p~]$ față de 773)

Gigel a găsit prin sertarul bunicii un bilețel pe care scria o formulă de decodificare a unui șir de caractere **[$s$]** de lungime cel mult $1.000.000$ ce conține numere naturale nenule (le vom nota cu $x[~k~]$), $[&nbsp;]$ (paranteze pătrate), ${&nbsp;}$ (acolade), $<&nbsp;>$ (paranteze unghiulare) și $,$ (virgulă) . Acest șir are următoarele reguli de decodificare pentru fiecare subșir **s[~k~]** care începe cu $[$, ${$ sau $<$ și se termină cu $]$, $}$ sau $>$:
1) Dacă $**s[~k~]** = "[x[~1~], x[~2~], x[~3~], ..., x[~p~]]"$, atunci **$s[~k~]$** se transformă într-un număr întreg $t = (x[~1~]^-1^ + x[~2~]^-1^ + x[~3~]^-1^ + ... + x[~p~]^-1^)$% 773; (suma inverselor modulare ale numerelor $x[~1~], x[~2~], x[~3~], ..., x[~p~]$ față de 773, $modulo 773$)

2) Dacă $**s[~k~]** = "{x[~1~], x[~2~], x[~3~], ..., x[~p~]}"$, atunci **$s[~k~]$** se transformă într-un număr $t = cmmmc(x[~1~], x[~2~], x[~3~], ..., x[~p~])$% 773;
3) Dacă $**s[~k~]** = "<x[~1~], x[~2~], x[~3~], ..., x[~p~]>"$, atunci **$s[~k~]$** se transformă într-un număr $t$ care este egal cu câte numere $q$ sunt mai mici strict decât $S = (x[~1~] + x[~2~] + x[~3~] + ... + x[~p~])$% 773 și pentru care $cmmdc(S, q) = 1$.
La final Gigel însumează numerele rămase.

Fișierul de ieșire $gigel.out$ va conține suma numerelor rămase după decodificarea șirului [$s$].

h2. Restricții

h2. Restricții și precizări

* $1 ≤ x[~k~] ≤ 20$, pentru orice $x[~k~]$;
* $1 ≤ lungimea șirului **s** ≤ 1.000.000$;
* Notăm cu $cmmdc(a, b)$ cel mai mare divizor comun al numerelor $a$ și [$b$], iar cu $cmmmc(a, b)$ cel mai mic multiplu comun al numerelor $a$ și [$b$];
* Se garantează că fiecare operație nu depășeste tipul de date $unsigned long long$;

* Inversul modular al unui număr $x$ față de un număr M este un număr $a$ pentru care a * x este congruent cu 1 (modulo M);

* Inversul modular al unui număr $x$ se notează cu $x^-1^$ și este egal cu numărul $a$ cu proprietatea că $x * a mod M = 1$.

* Se garantează că expresia este corectă.
h2. Exemplu

| 1,<2,{12,4},[9,{4,5,9}]>,2
| 21
| ${12,4} = 12$ (operația 2)

  ${4,5,9} = 180$ (operația 2)
  Șirul se va transforma în: $1,<2,12,[9,180]>,2$
  $[9,180] = 13$, deoarece inversul modular al lui 9 față de 773 este 86, iar inversul modular al lui 180 față de 773 este 700,
  deci (86 + 700) % 773 = 13 (operația 1)
  $<2,12,13> = 18$ (operația 3)
  Șirul se va transforma în: 1,18,2
  Deci, rezultatul va fi: $1 + 18 + 2 = 21$.

${4,5,9} = 180$ (operația 2)
Șirul se va transforma în: $1,<2,12,[9,180]>,2$
$[9,180] = 13$, deoarece inversul modular al lui 9 față de 773 este 86,
iar inversul modular al lui 180 față de 773 este 700,
deci (86 + 700) % 773 = 13 (operația 1)
$<2,12,13> = 18$ (operația 3)
Șirul se va transforma în: 1,18,2
Deci, rezultatul va fi: $1 + 18 + 2 = 21$.

|
== include(page="template/taskfooter" task_id="gigel") ==