• Acasă
  • Despre noi
  • Autori
  • Mărturii
  • Arhivă
  • Trimite Articol
  • Contact

WORLDIT

Lumea în 1 și 0.

  • Știri
    • Tehnologie
    • Tehnologie mobilă
    • Securitate
    • Developers
    • Știință
    • Benzi desenate
    • Jocuri
    • Intern
  • Tehnic
    • Browser
    • C#
    • C/C++
    • Challenge
    • HTML/CSS
    • Javascript, Ajax, jQuery
    • Open Source
    • PHP
    • Python
    • Securitate IT
    • Socializare
    • WordPress
    • Altele
  • Recenzii
  • Interviuri
  • Evenimente

Problema Ucif

20
  • Publicat de Coss
  • în Probleme algoritmică
  • — 12 sept., 2009 at 8:15 pm

Fie 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;
}

Etichete: C++ONIprobleme informaticasolutii problemetimp de rulare

— Albulescu Cosmina a scris 223 articole

Nu există o descriere a autorului.

  • Articolul anterior Apple ia masuri de criza
  • Articolul următor Rezultate GrepIT (locul 1)

20 Comentarii

  1. dranaxum spune:
    septembrie 12, 2009 la 8:46 pm

    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.

  2. dranaxum spune:
    septembrie 12, 2009 la 8:52 pm

    Pune-o si pe hackpedia la Algoritmica ca sa fie dezbatuta si acolo ca e interesanta solutia in O(1).

  3. Andrei Misarca spune:
    septembrie 12, 2009 la 11:19 pm

    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). 🙂

  4. miculprogramator spune:
    septembrie 13, 2009 la 9:06 am

    Hmmmm…Si iese mai repede asa?

  5. Andrei Misarca spune:
    septembrie 13, 2009 la 11:16 am

    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)).

  6. miculprogramator spune:
    septembrie 13, 2009 la 12:22 pm

    Da, probabil ca ar fi mers si un pow. Eu am gandit in perspectiva 😀 .

  7. Andrei Misarca spune:
    septembrie 13, 2009 la 12:31 pm

    Ideea e ca poÈ›i determina ultima cifra a lui x^y in O(1), fara a mai ridica efectiv la putere. 🙂

  8. dranaxum spune:
    septembrie 13, 2009 la 12:42 pm

    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).

  9. Andrei Misarca spune:
    septembrie 13, 2009 la 12:49 pm

    Dar pentru 10^100? Nu mai prea merge 🙂

  10. dranaxum spune:
    septembrie 13, 2009 la 12:57 pm

    Bagi numere mari, ideea matematica e aceiasi. Daca ai gasit o regula, o aplici pe aia normal.

  11. Andrei Misarca spune:
    septembrie 13, 2009 la 1:05 pm

    Cam greu sa bagi numerele mari in cazul de fața. Implementarea e foarte nasoala, iar complexitatea este mai mare decat O(1).

  12. dranaxum spune:
    septembrie 13, 2009 la 1:06 pm

    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.

  13. miculprogramator spune:
    septembrie 13, 2009 la 1:07 pm

    Nu va mai busiti pe-aici cu nr mari sau nu. M-am uitat pe solutia oficiala si era un pow. =))

  14. Andrei Misarca spune:
    septembrie 13, 2009 la 1:12 pm

    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. 😀

  15. dranaxum spune:
    septembrie 13, 2009 la 1:19 pm

    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?

  16. Andrei Misarca spune:
    septembrie 14, 2009 la 11:19 pm

    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) 🙂

  17. Ridicarea la putere in timp logaritmic | WorldIT spune:
    noiembrie 19, 2009 la 9:05 pm

    […] 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 […]

  18. alina spune:
    martie 3, 2011 la 4:44 pm

    Imi puteti arata o rezolvare in c++ a acestei probleme? va rog:D…sunt incepatoare si nu ma prea descurc. VA multumesc anticipat

    • Andrei Avădănei spune:
      martie 3, 2011 la 4:46 pm

      Buna Alina. Si cu ce rezolvare ai dori sa te ajutam avand in vedere ca problema e rezolvata?

  19. dranov spune:
    februarie 18, 2012 la 8:41 pm

    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ă”.


  • Facebook

    WorldIT.info
  • Ultimele Atacuri Cibernetice din Romania – RO Hacked

    [wp_rss_retriever url="https://rohacked.bit-sentinel.com/feed/" excerpt="none" items="5" read_more="false" new_window="true" thumbnail="false" cache="0"] RO Hacked este registrul atacurilor cibernetice din România.
  • Caută

  • Articole Recomandate

    • Recent Posts
    • Tags
    • Număr record de participanți la DefCamp 2015, cel mai important eveniment dedicat securității cibernetice din Europe Centrala si de Estdecembrie 2, 2015
    • La DefCamp 2015 vei afla prin ce tehnici pot fi evitate măsurile de securitate ale sistemelor informatice criticeoctombrie 16, 2015
    • Ultima sansa sa rezervi bilete de tip Early Bird la DefCamp 2015septembrie 1, 2015
    • 15 sfaturi despre cum poti deveni un programator bun venite de la specialisti romaniaugust 4, 2015
    • algoritmica Android antivirus Apple Avadanei Andrei benzi desenate BitDefender blog browser C++ Chrome concurs eveniment Facebook Firefox Google google chrome hacking html5 infografic informatica internet Internet Explorer IT javascript linux Microsoft Mozilla Firefox online PHP programare retea sociala review Romania securitate Tehnologie Twitter web Windows Windows 7 Wordpress WorldIT worldit.info Yahoo! YouTube
  • aprilie 2021
    L Ma Mi J V S D
     1234
    567891011
    12131415161718
    19202122232425
    2627282930  
    « dec.    
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Tehnic
  • C/C++
  • Probleme algoritmică
  • Problema Ucif
  • Important

    • Bit Sentinel
    • Centrul de Cercetare în Securitate Informatică din România
    • DefCamp
  • Prieteni

    • BetiT.ro
    • bijuterii handmade
    • Computerica | Resurse gratuite PC
    • Descopera.org
    • Gadgeturi si IT – Giz.ro
  • Prieteni

    • PC – Config
    • RO Hacked
    • Stiri IT

Copyright © 2009-2014 WORLDIT. Toate drepturile Rezervate.
Termeni și condiții | Contact | Licența Creative Commons