Problema Carti

Vasile se joaca un joc foarte interesant. El are un pachet de N carti de joc (numerotate distinct de la 1 la N). Cartile din pachet sunt amestecate.
Vasile se uita la fiecare carte din pachet incepand cu prima, pana ajunge la cartea cu numarul 1, pe care o scoate din pachet. Apoi cauta cartea cu numarul 2, cartea cu numarul 3, s.a.m.d. De fiecare data incepe cautarea de unde a ramas (de la cartea care urmeaza dupa ultima carte scoasa din pachet). De fiecare data cand ajunge la sfarsitul pachetului, Vasile bate din palme si continua cautarea de la inceputul pachetului. Cand ultima carte din pachet este eliminata, jocul se termina.

Cerinta

Scrieti un program care sa determine de cate ori bate din palme Vasile in timpul unui joc.

Date de intrare

Prima linie a fisierului de intrare carti1.in contine un numar natural N, reprezentand numarul de carti din pachet. Urmatoarele N linii contin numerele cartilor de joc, in ordinea in care acestea se afla in pachet.

Date de iesire

Fisierul de iesire carti1.out contine o singura linie pe care se afla numarul cerut.

Restrictii

• 1<=N <= 100000

Exemplu

carti1.in

3
2
1
3

carti1.out
2

carti1.in
7
3
6
7
1
5
4
2

carti1.out
3

Descrierea solutiei

Problema se poate rezolva in cel mai defavorabil caz in complexitatea O(n^2), ceea ce nu ne convine. O rezolvare pe baza acestei idiei s-ar referi la memorarea numerelor de la 1 la n intr-un vector si imitarea jocului lui Vasile.

O idee care ne-ar duce la o solutie optima este aceea de a tine un vector poz, pozitia initiala a fiecarei carti. Totul se reduce la numarul elemente care indeplinesc conditia poz[i]>poz[i+1].

Solutia problemei:

#include <iostream>
#include <fstream>
using namespace std;

#define MAX 20000

int n,i,palme,poz[MAX],x;
int main()
{
 ifstream f("carti1.in");
 ofstream g("carti1.out");
 f>>n;
 for (i=0;i<n;++i)
 {
 f>>x;
 poz[x-1]=i;
 }
 f.close();
 for (i=0;i<n-1;++i)
 if (poz[i]>poz[i+1]) palme++;
 g<<palme<<"\n";
 g.close();
 return 0;
}

P.S: Zilele urmatoare voi fi plecata, asa ca nu voi fi prea activa.

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!