Question

Se citește un număr n. Sa se afișeze câte zero-URI va conține produsul nr pana la n . n este de maxim 9 cifre.

Answer 1

Produsul numerelor pana la n putem sa extrapolam ca inseamna 1 * 2 * 3 * ... * n, este evident.

Acum, sa prelucram putin treaba:

prod = n!

Deci:

prod = 1 * 2 *3 * ... * (n-1) * n

Acum, stim din clasa a 6a ca orice numar poate fi scris ca produsul factorilor sai primi.

Spre exemplu 810 = 2 * 3 * 3 * 3 * 3 * 5. Asa ca putem fiecare termen din produsul ala prod sa il inlocuim cu produsul factorilor sai primi.

Spre exemplu:
1 * 2 * 3 * 4 * 5 * 6 = = (1) * (2) * (3) * (2 * 2) * (5) * (2 * 3) = = 1 * 2 * 3 * 2 * 2 * 5 * 2 * 3

Asta cu descompusul ar fi observatia nr. 1.


Observatia nr. 2: un produs de numere nu va contine 0-uri DECAT la sfarsit, si doar daca in acel produs, unii factori sunt 10.

Spre exemplu 2 * 10 * 3 * 10 va contine  2 de 0 la sfarsit. Singura alta varianta de a obtine 10 intr-un produs, e sa ai pe undeva un 2 si pe altundeva un 5, astfel incat sa ii imperechezi si sa iti dea un 10, pentru ca isngurele doua perechi de numere care inmultite iti dau 10 sunt 1 si 10 sau 2 si 5.

Deci spre ex 2 * 3 * 5 * 7 * 5 * 2 * 2 nu contine 10, dar am putea grupa primul 2 cu primul 5 si al doilea 2 cu al doilea 5 si am obtine 2 de 10 deci acel produs ar avea 2 de 0 la sfarsit. 

Ca sa rezumam:

1. Pronim cu produsul numerelor pana la n(noi l-am numit prod).

2. Il putem scrie ca produsul produselor factorilor primi ai fiecarui numar(ai exemplul mai sus).

3. In produsul de la 2. tu trebuie ori sa gasesti numere de 10, ori sa imperechezi cate un 2 si un 5 ca sa faci un 10.

4. Intr-un sir de factori primi nu vei gasi EVER un 10, 10 nu e numar prim, iar aia se numesc factori "primi" cu un motiv :)) deci ne ramane doar sa adunam perechi de 2 si

5. Acum, pentru fiecare pereche de 2 si 5, obtinem un 10, care "adauga" un 0 la sfarsitul produsului final, deci putem spune ca fiecare pereche (2,5) adauga un 0, cu alte cuvine am putea spune ca atatea perechi (2,5) cate gasim, atatia de 0 avem in produsul final.

Super, deci stim ca nu trebuie decat sa vedem cate perechi (2,5) avem, cate perechi avem atatea 0-uri avem.

Acum sa vedem cate perechi avem:

Sa fac o analogie, daca ai o camera cu baieti si fete(posibil sa fie si prea multi sau prea putini baieti sau fete, nu neaaparat sa fie perfect la fe numerele), si trebuie sa ii pui sa danseze baiat cu fata, cate perechi vei putea face? 

Pai in cel mai bun caz in care sunt tot atatia baieti cate sunt fete, or sa fie atatea perechi cati baieti sunt, simplu.

Acum in cazul in care usnt mai putini baieti, atunci unele fete or sa fie lasate fara partener si or sa fie doar atatea perechi cati baieti sunt. 

Iar daca sunt prea multi baieti, atunci or sa ramana unii pe margine si or sa fie doar atatea perechi cate fete sunt.

Cu alte cuvinte putem spune ca numarul de perechi este egal cu minimul dintre nr. de baieti si nr. de fete.

Boooon, probabil ca vezi cum se transpune asta in problema noastra cu perechi de 2 si 5: Faci lista cu numere, apoi faci lista cu factorii primi, toti pusi la gramada, pentru numere, apoi numeri cati de 2 si cati de 5 ai acolo, minimul dintre nr de 2 si nr de 5 e raspunsul tau.

Nu o sa pun codul, sau daca il pun, il pun in alt limbaj nu in C++(sunt hater C++) ca sa muncesti si tu putin, sau macar sa vezi si cam cum arata un alt limbaj.