h2. 'Melodii':problema/melodii

Solutii prezentate de catre ==user(user="maritim" type="tiny")==.

Solutii prezentate de ==user(user="maritim" type="tiny")==.

Problema se poate reformula matematic in modul urmator:

h2. 'Camionas':problema/camionas

Solutii prezentate de ==user(user="Teodor94" type="tiny")==.
 

h4. $Solutia 1: O(M * log N) - 100 puncte$
Basmul poate fi privit ca un graf orientat cu $N$ noduri si $M$ muchii, in care fiecare muchie are o rezistenta si se garanteaza ca exista cel putin un drum intre nodul $1$ si nodul $N$.

Complexitatea preprocesarii numerelor prime este $O(M * log(log M))$, unde $M$ este $sqrt(MAX_VAL)$, iar complexitatea efectiva a problemei este $O(N * NR_MAX_DIV)$, unde $NR_MAX_DIV$ este numarul maxim de divizori al unui numar.

h4. $Solutia 3.1: 80 puncte$

h4. $Solutia 3.1: 80 puncte$ ==user(user="Vman" type="tiny")==

Adaugam toate numerele intr-un hash, retinand pentru fiecare numar pozitia pe care se afla in vector. Vom considera din nou cele $N$ numere ca fiind nodurile grafului. Parcurgem cele $N$ noduri, iar pentru fiecare valoare, ii vom cauta multiplii in hash folosind un algoritm asemanator cu Ciurul lui Eratosthenes, si vom trage muchie intre nodul curent si nodul gasit in hash. Astfel, ajungem din nou la determinarea numarului de componente conexe ale grafului.