h3. ( problema usoara )

rezolvarea $O(n^2)$:

rezolvarea $O(n^2^)$:

 - se ia fiecare pereche de pokemoni $(i,j)$ cu $i<j$ si se verifica daca este valida

 - o astfel de solutia ar fi adus $50-70%$ din punctaj in funtie de implementare

 - o astfel de solutia ar fi adus $50-70%$ din punctaj in functie de implementare

rezolvarea $O(n log n)$:

rezolvarea $O(n)$:
 - se calculeaza $v[i]$ = numarul de pokemoni cu forte mai mici sau egale cu $i$

 - pentru fiecare pokemoni se adauga la solutie numarul de pokemoni din intervalul cu care poate forma o echipa ( atentzia un pokemon nu poate forma o echipa cu el insusi

 - pentru fiecare pokemon se adauga la solutie numarul de pokemoni din intervalul cu care poate forma o echipa (atentie, un pokemon nu poate forma o echipa cu el insusi)

h2. 'Panou':problema/panou

Sa presupunem ca dorim sa aflam suma numerelor care se pot forma cu cifrele date in care ignoram conditia care impune ca prima cifra sa fie nenula. Fie $N$ numarul total de cifre ( din restrictiile problemei $N < 1001$ ). Folosind descompunerea in baza 10, rezultatul se va scrie sub forma {$c{~N-1~} * 10^N-1^ + c{~N-2~} * 10^N-2^ + ... c{~0~} * 10^0^$}. Daca stim coeficientii {$c{~0~}$}, {$c{~1~}$}, ... {$c{~N-1~}$}, atunci stim si rezultatul ( toate calculele vor fi facute modulo $M$ ). Se observa ca daca intr-un numar format cifra $x$ apare pe pozitia $i$, atunci trebuie sa adunam la coeficientul {$c{~i~}$} numarul {$x * Res$}, unde $Res$ este numarul de numere care se pot forma si in care cifra $x$ apare pe pozitia {$i$} - daca descompunem fiecare numar in baza 10 ca mai sus si dam factor comun {$10^i^$} obtine exact aceasta relatie. Coeficientii c{~0~}, c{~1~}... c{~N-1~} vor fi deci toti egali pentru ca fiecare cifra $x$ poate fi pusa pe orice pozitie.
Daca frecventele cifrelor sunt {$f{~0~}$}, {$f{~1~}$}... {$f{~9~}$}, atunci cifra $x$ poate aparea pe o pozitie in exact !junior-challenge/solutii?formula.jpg! numere, formula care rezulta din calculul numarului de anagrame pentru un cuvant dat, care este dat de factorialul lungimii cuvantului supra produsul factorialelor frecventelor fiecarei litere in parte. Pentru a calcula efectiv acest numar, vom face toate simplificarile posibile ( impartind prin cel mai mare divizor comun dintre doua numere, primul de la numarator si al doilea de la numitor ) si vom obtine in final un sir de numere care trebuie inmultite ( modulo $M$ ).

Daca prima cifra poate fi 0, rezultatul este deci !junior-challenge/solutii?formula2.jpg!.

Daca prima cifra poate fi {$0$}, rezultatul este deci:
!junior-challenge/solutii?formula2.jpg!, unde numarul de $1$ este dat de suma frecventelor cifrelor.
Desi formula pare la prima vedere complicata, ea rezulta destul de usor din formula numarului de anagrame ale unui cuvant dat si din scrierea numerelor in baza $10$.

Aceasta este una din solutii care obtinea punctajul maxim in concurs.

Daca prima cifra nu poate fi $0$ procedam in felul urmator: fixam prima cifra $C$ ( de la $1$ la $9$ ), scadem cu $1$ frecventa cifrei selectate si calculam conform rezultatului de mai sus la care mai adaugam {$C * Res * 10^N^$}. In final vom aduna ( tot modulo $M$ ) cele $9$ numere obtinute si afisam rezultatul.
 
Aceasta este una din solutii care obtinea punctajul maxim in concurs. Exista si solutii mai rapide care folosesc combinari, insa s-a considerat ca aceste cunostinte depasesc nivelul claselor 7-9.