== 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), $@$ (A rond) și $,$ (virgulă) . Acest șir are următoarele reguli de decodificare:
1) Dacă $s = "[x [~1~], x [~2~], x [~3~], ..., x ~p~]"$, atunci $s$ se transformă într-un număr întreg $t = (x [~1~]^-1^ + x [~2~]^-1^ + x [~3~]^-1^ + ...+ x [~p~]^-1^)$ **% 773**;
2) Dacă $s = "{x [~1~], x [~2~], x [~3~], ..., x [~p~]}"$, atunci $s$ se transformă într-un număr $t = cmmmc(x [~1~], x [~2~], x [~3~], ..., x [~p~])$ **% 773**;
3) Dacă $s = "@x [~1~], x [~2~], x [~3~], ..., x [~p~]@"$, atunci $s$ se transformă într-un număr $t$ care este egal cu câte numere $x$ sunt mai mici strict decât $S = (x ~1~ + x ~2~ + x ~3~ + ... + x [~p~])$ **% 773** și pentru care $cmmdc(S, x) = 1$.
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, $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.
Ajutați-l pe Gigel să decodifice șirul găsit pentru a vă răsplăti cu 100 de puncte!
h2. Date de intrare
Fișierul de intrare $gigel.in$ va conține pe prima linie șirul [$s$].
Fișierul de intrare $gigel.in$ va conține pe prima linie șirul **[$s$]**.
h2. Date de ieșire
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;$
* $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$.
* Se garantează că fiecare operație nu depășeste tipul de date $unsigned long long$;
* 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
table(example).
|_. gigel.in |_. gigel.out |
| 1,@2,{12,4},[9,{4,5,9}]@,2
|_. gigel.in |_. gigel.out |_. Explicație |
| 1,<2,{12,4},[9,{4,5,9}]>,2
| 21
|
h3. Explicație
${12,4} = 12$
${4,5,9} = 180$
Șirul se va transforma în: $1,@2,12,[9,180]@,2$.
$[9,180] = 13$
$@2,12,13@ = 18$
| ${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$.
|
== include(page="template/taskfooter" task_id="gigel") ==
