Astfel, am putea să variem exponentii pentru fiecare dintre cele 4 cifre prime şi apoi să hotărâm pentru fiecare configuraţie daca se poate obţine dintr-un număr cu lungime între $A$ şi $B$. Pentru a simplifica problema, observăm că dacă $Lmin$ ar fi numărul minim de cifre necesar pentru a obţine numărul $X$, atunci pentru orice lungime $L$ mai mare sau egală decât $Lmin$ există un număr de lungime $L$ care îl poate produce pe $X$. Adăugăm $L - Lmin$ 1-uri in coadă. Pretty simple huh?. Numărul $A$ devine astfel irelevant. Tot ce trebuie sa verificăm pentru un anumit număr $X$ este dacă $Lmin(X)$ este mai mic sau egal cu $B$.

Acest lucru se poate face printr-o abordare de tip greedy, ilustrată în fragmentul de cod de mai jos, extras din sursa lui 'Rareş Buhai':infoarena.ro/user/darren, primul concurent care a rezolvat problema în timp de concurs.

Acest lucru se poate face printr-o abordare de tip greedy, ilustrată în fragmentul de cod de mai jos, extras din sursa lui 'Rareş Buhai':utilizator/darren, primul concurent care a rezolvat problema în timp de concurs.

==code(c) |
int getNum(int x)

}
==

Acestea fiind zise, vă prezentăm soluţia lui Mihai Popa:infoarena.ro/user/mihaipopa12, a doua submisie corectă în timp de concurs.

Acestea fiind zise, vă prezentăm soluţia lui 'Mihai Popa':utilizator/mihaipopa12, a doua submisie corectă în timp de concurs.

==code(c) |

bq. Deci contribuţia problemei ăsteia la concurs a fost o coloană de $0$ adaugată în clasament?

Deşi problema pare să ceară fie o dinamică, fie un back optimizat până ajungi să dispreţuiesti autorul ca entitate prezentă pe Pământ, soluţia e de fapt destul de mişto. În general, problemele de colorare în sine sunt NP-complete, i.e se 'presupune':http://en.wikipedia.org/wiki/P_%3D_NP_problem ca nu admit soluţie în timp polinomial. Nu prea bag mâna în foc că acest caz particular este de asemenea NP, însă presupun că cel puţin problema de numărare a colorărilor este. (Dacă mă contraziceţi, aş fi chiar entuziasmat *:D*).

Deşi problema pare să ceară fie o dinamică, fie un back optimizat până ajungi să dispreţuiesti autorul ca entitate prezentă pe Pământ, soluţia e de fapt destul de mişto. În general, problemele de colorare în sine sunt NP-complete, i.e se 'presupune':http://en.wikipedia.org/wiki/P_%3D_NP_problem ca nu admit soluţie în timp polinomial. Nu prea bag mâna în foc că acest caz particular este de asemenea NP-Complete^*^, însă presupun că cel puţin problema de numărare a colorărilor este. (Dacă mă contraziceţi, aş fi chiar entuziasmat *:D*).

Să rezolvăm o variantă mai simplă a problemei. Să presupunem că nu există două caractere $?$ alăturate. Astfel, culoarea unui anumit semn de întrebare nu afecteaza colorarea altui semn de întrebare. Putem deci răspunde cu o formula.
$ANS = p1 * p2 * p3 * ... pk$ unde $pi$ este numărul de posibilităţi de a colora al $i-lea$ semn de întrebare.

Dacă ar fi să privim matricea ca o tablă de şah, facem observaţia critică conform căreia celulele albe sunt independente complet de cele negre. Mai precis, toate căsuţele albe au doar vecini negri iar căsuţele negre au doar vecini albi. Aşa că presupunând că toate celulele albe sunt fixate (pentru fiecare $?$ de casuţă albă am ales deja culoarea) putem doar să trecem prin cele negre şi să înmulţim pentru fiecare $?$ numărul de valori pe care le poate lua semnul de întrebare respectiv, conform formulei precedente. Având în vedere că $K$, numărul de $?$, este mai mic sau egal cu $18$, atunci fie numărul de semne de întrebare albe este mai mic sau egal decât $9$, fie cel de semne de întrebare negre este mai mic sau egal decat $9$. Obţinem astfel o complexitate de timp $O(5 ^ (K / 2) * K)$.

Dacă ar fi să privim matricea ca o tablă de şah, facem observaţia critică conform căreia celulele albe sunt independente complet de cele negre. Mai precis, toate celulele albe au doar vecini negri iar celulele negre au doar vecini albi. Aşa că presupunând că toate celulele albe sunt fixate (pentru fiecare $?$ de casuţă albă am ales deja culoarea) putem doar să trecem prin cele negre şi să înmulţim pentru fiecare $?$ numărul de valori pe care le poate lua semnul de întrebare respectiv, conform formulei precedente. Având în vedere că $K$, numărul de $?$, este mai mic sau egal cu $18$, atunci fie numărul de semne de întrebare albe este mai mic sau egal decât $9$, fie cel de semne de întrebare negre este mai mic sau egal decat $9$. Obţinem astfel o complexitate de timp $O(5 ^ (K / 2) * K)$.

h2. 'Triangles':problema/triangles

==code(c) |
n = min(n , 150 * 1000);

==
 

==

private

protected

8308