Problema predecesor,Campion 2009

05 Decembrie, 2009 la 12:45 812 afisari

Etichete : , , , , , ,

Considerăm un şir de N numere naturale distincte a1, a2, …, aN. Pentru fiecare termen ai definim predecesorul său, dacă există, ca fiind cel mai din dreapta termen aj, cu j < i şi aj < ai. De exemplu, pentru şirul 8, 12, 2, 4, 3, 10, 9, 7, 5, 6, numărul 8 este predecesorul lui 12, 3 este predecesorul lui 5, 10 nu este predecesorul niciunui număr, la fel 4 nu este predecesor pentru alt număr, 2 nu are predecesor.

Cerinţă
Scrieţi un program care determină câte numere din şir nu sunt predecesori ai niciunui alt număr.

Date de intrare

Fişierul de intrare predecesor.in conţine pe prima linie numărul natural N reprezentând numărul de termeni ai şirului. Pe următoarea linie se găsesc, separaţi prin câte un spaţiu, termenii a1, a2, …, aN ai şirului.

Date de ieşire

Fişierul de ieşire predecesor.out va conţine o singura linie pe care va fi scris un singur număr natural reprezentând numărul de termeni ai şirului care nu sunt predecesori ai niciunui alt număr.

Restricţii

  • 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

Recomandam, pe aceeasi tema
Tutoriale WEB – Concurs pentru programatori

Despre autorul articolului :

Avădănei Andrei - Autorul a scris 591 articole (vezi lista completa).

Fondator si redactor worldit.info, ma numesc Andrei si sunt pasionat de programare , in special de algoritmica si web development. Forumul WorldIT iti sta la dispozitie daca ai nevoie de suport tehnic, informatii si sugestii privind diverse produse prezentate pe blog si nu numai. Mai multe detalii despre activitatile mele aici.

Comentarii la "Problema predecesor,Campion 2009"

  1. Andrei Misarca says:
    Decembrie 7, 2009 at 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 says:
    Decembrie 7, 2009 at 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. :)

Lasa un comentariu