Problema predecesor,Campion 2009
2Consideram 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 |
6 |
Solutie
Trebuie sa privim astfel valorile.Exista vreun v[j] astfel incat v[i]
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
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 🙂
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: