_Inaugurăm prin acest blogpost o serie de editoriale care, sperăm noi, îşi vor face apariţia după fiecare rundă a concursului Infoarena Monthly. Scopul lor este de a augmenta latura educativa a concursului prin explicarea detaliata a solutiilor problemelor propuse. Sperăm de-asemenea ca secţiunea de comentarii să devină o platforma potrivită pentru discuţii şi feedback despre subiecte şi despre formatul concursului în sine. Suntem conştienţi că o asemenea iniţiativă apare destul de târziu, concursul fiind deja în runda cu numărul $8$, însă am considerat că o atitudine de tip "Las' ca începem de luni, asa se face treaba" n-ar fi fost foarte inspirata. Avand in vedere ca urmatorul "Luni" al Monthly-ului este practic in $2013$. Acestea fiind zise, let s get to work._

_Inaugurăm prin acest blogpost o serie de editoriale care, sperăm noi, îşi vor face apariţia după fiecare rundă a concursului Infoarena Monthly. Scopul lor este de a augmenta latura educativă a concursului prin explicarea detaliată a soluţiilor problemelor propuse. Sperăm de-asemenea ca secţiunea de comentarii să devină o platformă potrivită pentru discuţii şi feedback despre subiecte şi despre formatul concursului în sine. Suntem conştienţi că o asemenea iniţiativă apare destul de târziu, concursul fiind deja în runda cu numărul $8$, însă am considerat că o atitudine de tip "Las' ca începem de luni, asa se face treaba" n-ar fi fost foarte inspirata. Avand in vedere ca urmatorul "Luni" al Monthly-ului este practic in $2013$. Acestea fiind zise, let s get to work._

Runda $8$ a avut $91$ de concurenţi înscrişi şi $79$ de concurenţi care au submitat cel puţin o sursă. Echipa a subestimat însă dificultatea setului ales, astfel doar $2$ concurenţi au terminat concursul având $3$ probleme rezolvate, iar una dintre probleme nu a fost rezolvată corect de nimeni. Dacă ar fi să luăm ca referinţă concursurile de tip ACM, se spune că un set de probleme este bun dacă fiecare problemă este rezolvată de către cineva, dar nimeni nu rezolvă toate problemele. We're not quite there yet, dar ne străduim :).

h2. 'Cifre3':problema/cifre3

Această problemă avea în primă fază alt enunţ, iar cele 2 surse oficiale au la baza ideea problemei iniţiale. Astfel, marea majoritate a concurenţilor a ajuns să aiba o soluţie mult mai scurtă şi mai eficientă. Soluţia noastră se folosea de faptul ca numărul produselor posibile nu este foarte mare, din 2 motiveŞ

Această problemă avea în primă fază alt enunţ, iar cele 2 surse oficiale au la baza ideea problemei iniţiale. Astfel, marea majoritate a concurenţilor a ajuns să aiba o soluţie mult mai scurtă şi mai eficientă. Soluţia noastră se folosea de faptul ca numărul produselor posibile nu este foarte mare, din 2 motive.

* Toate numerele trebuie să aibă ca factori primi doar numere din mulţimea $2 , 3 , 5 , 7$, deoarece acestea sunt singurele cifre care sunt numere prime.
* Având în vedere că numărul de cifre este limitat de $20$, puterea maxima a lui $2$ este limitată de $60$ (numărul format din $20$ de cifre de {$8$}), cea a lui $3$ de $40$ , iar cele ale lui $5$ si $7$ chiar de catre $20$.

1. Toate numerele trebuie să aibă ca factori primi doar numere din mulţimea $2 , 3 , 5 , 7$, deoarece acestea sunt singurele cifre care sunt numere prime.
2. Având în vedere că numărul de cifre este limitat de $20$, puterea maxima a lui $2$ este limitată de $60$ (numărul format din $20$ de cifre de {$8$}), cea a lui $3$ de $40$ , iar cele ale lui $5$ si $7$ chiar de catre $20$.

Deci există maxim $60 * 40 * 20 * 20 = 960 000$ de produse posibile. Observaţi că această margine superioară este o supraestimare destul de puternică, având în vedere că exponentul maxim nu poate fi atins de fiecare cifră în acelaşi timp.

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 poate î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$.

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ş, 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':infoarena.ro/user/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, a doua submisie corectă în timp de concurs

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

==code(c) |