• 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 predecesor,Campion 2009

2
  • Publicat de Andrei Avădănei
  • în Fără categorie
  • — 5 dec., 2009 at 12:45 pm

Consideram un sir de N numere naturale distincte a1, a2, …, aN. Pentru fiecare termen ai definim predecesorul sau, daca exista, ca fiind cel mai din dreapta termen aj, cu j < i si aj < ai. De exemplu, pentru sirul 8, 12, 2, 4, 3, 10, 9, 7, 5, 6, numarul 8 este predecesorul lui 12, 3 este predecesorul lui 5, 10 nu este predecesorul niciunui numar, la fel 4 nu este predecesor pentru alt numar, 2 nu are predecesor.

Cerinta
Scrieti un program care determina cate numere din sir nu sunt predecesori ai niciunui alt numar.

Date de intrare

Fisierul de intrare predecesor.in contine pe prima linie numarul natural N reprezentand numarul de termeni ai sirului. Pe urmatoarea linie se gasesc, separati prin cate un spatiu, termenii a1, a2, …, aN ai sirului.

Date de iesire

Fisierul de iesire predecesor.out va contine o singura linie pe care va fi scris un singur numar natural reprezentand numarul de termeni ai sirului care nu sunt predecesori ai niciunui alt numar.

Restrictii

  • 3 < = N <= 500 000
  • 1 < = ai <= 1 000 000 000, pentru orice 1 <= i <= N

Exemplu

predecesor.in predecesor.out

10
8 12 2 4 3 10 9 7 5 6

6

Solutie

Trebuie sa privim astfel valorile.Exista vreun v[j] astfel incat v[i]=i+1? Dezvoltand putem afirma ca cea mai apropiata valoare mai mare ca v[i] va avea ca predecesor pe v[i].Daca vom gasi una mai mica inseamna ca de acum aceasta va „prelua puterea” de acum incolo.

Practic daca gasim o valoare v[j] > v[i] inseamna ca v[i] este predecesor al lui v[j].Daca vom gasi o valoare v[j] < v[i] inseamna ca de acum v[j] va trebuie comparat cu urmatoarele valori pentru a vedea daca este predecesorul uneia dintre ele. Descarcati solutia problemei Predecesor,Campion 2009 – runda 4

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!

— Andrei Avădănei a scris 1246 articole

Andrei scrie pe worldit.info din vara lui 2011. Este fondatorul Asociatiei Centrul de Cercetare in Securitate Informatica din Romania - CCSIR si coordoneaza DefCamp, cea mai importanta conferinta de securitate informatica & hacking din Europa Centrala si de Est. Andrei ofera in cadrul Bit Sentinel servicii de securitate informatica, penetration testing, security management, recuperarea de pe urma unui atac cibernetic, training-uri si workshop-uri.

  • Articolul anterior CopyScape – Cum urmarim si reactionam impotriva plagiatorilor de articole?
  • Articolul următor Problema prod3, Campion 2009

2 Comentarii

  1. Andrei Misarca spune:
    decembrie 7, 2009 la 9:20 pm

    Solutia prezentata de tine ia 100 de puncte? Intreb asta pentru ca daca am vazut bine, tu ai complexitatea O(N^2), iar dupa dimensiunea datelor de intrare nu ar trebui sa ia maxim 🙂

  2. Avadanei Andrei spune:
    decembrie 7, 2009 la 9:24 pm

    Ia 100 de puncte pentru ca solutia e defapt O(n) PUR.
    Exprimarea mea atunci nu a fost corecta atunci, nu mi-am dat seama ca defapt ideea mea se bazeaza doar pe urmatorul pas si nu pe toti pana la capat.

    Acel while inaintaza doar un pas daca te uiti cu atentie. 🙂

    While-ul intern s-ar traduce astfel:

    if(v[i+1]>v[i])
    {
    	if(u[i]) u[i]=0,t--;
    	break;
    }
    else if(v[i+1]
    

    Am uitat sa fac aceasta schimbare dupa ce am publicat solutia. 🙂


  • Facebook

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

    • imacoolat-curat.ro
      | Published: februarie 3, 2020 - 2:00 am
    • hotel-palace.ro
      | Published: februarie 2, 2020 - 2:00 am
    • www.tahometru.ro
      | Published: februarie 1, 2020 - 2:00 am
    • alexisart.ro
      | Published: ianuarie 30, 2020 - 2:00 am
    • justshop.ro
      | Published: ianuarie 29, 2020 - 2:00 am
    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
  • ianuarie 2021
    L Ma Mi J V S D
    « dec.    
     123
    45678910
    11121314151617
    18192021222324
    25262728293031
  • Link-uri Sponsorizate

    • laptop second hand

    • Calculatoare Second Hand

    • cod voucher pc garage

  • Home
  • Problema predecesor,Campion 2009
  • 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

Multumim foarte mult ca ne-ai raportat greseala! O vom remedia in cel mai scurt timp posibil.