Problema Ucif
20Fie n
un numar natural si s
suma urmatoare:
s = 11+ 22 + 33 + … + nn
Cerinta
Scrieti un program care sa afiseze ultima cifra a lui s
.
Date de intrare
De pe prima linie a fisierului de intrare ucif
.in
se citeste numarul n
.
Date de iesire
Pe prima linie a fisierului de iesire ucif
.out
se va afisa numai ultima cifra a lui s
.
Restrictii
0 < n < 101
Exemplu:
ucif.in
3
ucif.out
2
Descrierea solutiei
Am abordat problema incercand sa fac ridicarea la putere in timp logaritmic, lucru care a fost foarte bun. Pentru solutia de mai joc, timpii sunt mai buni decat solutia oficiala, iar rezolvarea zic eu, daca nu mai simpla, cel putin mai eficienta. Timpul este peste tot 0 . 😀
Solutie
#include <iostream> #include <fstream> using namespace std; long long n,p,i,S; long long tip; long long put(long n, long p) { if(p==0) return 1; if(p%2==1) return (n*put(n,p-1))%10; tip=put(n,p/2)%10; return tip*tip%10; } int main() { ifstream f("ucif.in"); ofstream g("ucif.out"); f>>n; f.close(); for(i=1;i<=n;++i) { p=i; S+=put(i,p); } g<<S%10; g.close(); return 0; }
Daca acest articol contine o greseala, selecteaza cuvintele sau fraza gresita si tasteaza combinatia de taste Shift + Enter sau apasa click aici pentru a o raporta. Multumim!
Se poate rezolva in O(1) deoarece n^n MOD 10=(n MOD 10)^n.
Deci vom avea pentru 2: 2^2, 2^12, 2^22,…
Se observa ca 2^p, unde p este de forma x*10+2, x numar natural, are ultima cifra 4 sau 6 (se demonstreaza usor).
La fel pentru 3 (se termina in 7 sau 3).
Analog pentru restul numerelor.
Deci practic va trebui sa numaram de cate ori apare 4 in dezvoltarea asta (pentru 2^p) de cate ori 6 etc. Asta se face printr-un calcul simplu avand data forma lui p.
Pune-o si pe hackpedia la Algoritmica ca sa fie dezbatuta si acolo ca e interesanta solutia in O(1).
Rezolvarea in O(1), se bazeaza pe o chestie relativ mai greu de observat si demonstrat matematic (eu am remarcat din bulan), si anume ca valorile astea se repeta din 100 in 100, deci practic cu 100 de valori calculate se rezolva problema. Deci rezolvarea are complxitatea O(100) = O(1). 🙂
Hmmmm…Si iese mai repede asa?
In cazul problemei de fața, unde n <= 100, nu ajuta cu foarte mult, insa exista o rezolvare destul de simpla in O(N) a problemei (chiar mai simpla decat cea in O(N logN)).
Da, probabil ca ar fi mers si un pow. Eu am gandit in perspectiva 😀 .
Ideea e ca poÈ›i determina ultima cifra a lui x^y in O(1), fara a mai ridica efectiv la putere. 🙂
http://hackpedia.info/viewtopic.php?f=121&t=12280&p=93874#p93874 Aici aveti rezolvarea in O(1). Andrei M. (ca sa nu te confund cu celalalt Andrei) nu se pune problema unui O(100).
Dar pentru 10^100? Nu mai prea merge 🙂
Bagi numere mari, ideea matematica e aceiasi. Daca ai gasit o regula, o aplici pe aia normal.
Cam greu sa bagi numerele mari in cazul de fața. Implementarea e foarte nasoala, iar complexitatea este mai mare decat O(1).
Pe numere mari ar iesi un O(log N). Pentru 10^100 si la varianta ta tot O(log N) iese fiindca trebuie sa citesti N-ul tau.
Nu va mai busiti pe-aici cu nr mari sau nu. M-am uitat pe solutia oficiala si era un pow. =))
Uff, discuÈ›ia devenea chiar amuzanta. Oricum, cred ca trebuie sa admiÈ›i ca este mai simplu de implementat calculul primelor 100 de valori si citirea unui numar mare, iar apoi o afisare, decat citirea unui numar mare si crearea funcÈ›iilor respective pe numere mari. 😀
Din punct de vedere al implementarii clar. 🙂
Totusi trebuie si tu sa admiti ca e mult mai usor sa faci rationamentul meu fiindca observatia ta, ai zis-o si tu, e una norocoasa. 😀
Si ca veni vorba, sunt curios daca exista regula la:
N^(N-K)+(N-1)^(N-K-1)+…(K+1)^1.
Ar fi o generalizare a problemei ucif. La ucif K=0, ce ar fi daca K e variabil?
App, cred ca si io si dramaxum meritam cate un suc(eu prefer de hamei daca se poate) , intrucat rezolvarea gasita este mai rapida decat a ta (dupa cum scrie la prezentare) 🙂
[…] WP Greet BoxProbabil au fost cateva persoane ce nu au inteles la un moment dat rezolvarea problemei Ucif in O(1) explicata de Alex si Andrei Misarca si au dorit sa inteleaga ce a facut Cosmina in […]
Imi puteti arata o rezolvare in c++ a acestei probleme? va rog:D…sunt incepatoare si nu ma prea descurc. VA multumesc anticipat
Buna Alina. Si cu ce rezolvare ai dori sa te ajutam avand in vedere ca problema e rezolvata?
Defapt, ultima cifră se repetă chiar din 20 în 20 , nu din 100 în 100 cum este specificat mai sus. Asta înseamnă că problema poate fi facută și „manual” fără prea multă trudă.
Nu dau cifrele aici pentru a nu strica distracția nimănui. 😛
Click pe nume pentru „dovadă”.