Rezolvare completă PbInfo #1046 Munte

Se consideră un şir x1, x2,…, xn format din n numere naturale distincte. O secvenţă de număr maxim de elemente vecine în şir, de forma xi, xi+1,…, xk-1, xk, xk+1,…, xj (1≤i<k<j≤n) cu proprietatea că xi < xi+1 < ...< xk-1 < xk > xk+1 > ... > xj, se numeşte munte cu vârful xk. Două secvenţe munte au maxim un element comun în şir. O secvenţă munte are cel puţin 3 elemente. Un exemplu de şir format cu valorile 3 4 6 8 nu conţine nicio secvenţă munte, iar unul format cu valorile 3 4 8 1 2 5 0 conţine 2 secvenţe munte: 3 4 8 1 şi 1 2 5 0.

După determinarea tuturor secvenţelor munte şi a vârfurilor acestora, se elimină din şir vârfurile secvenţelor munte şi procedura continuă repetat cu determinarea noilor secvenţe munte şi a vârfurilor lor din şirul nou obţinut. Procedura se opreşte în momentul în care în şir nu mai există nicio secvenţă munte.

Cerința

Scrieţi un program care citeşte numerele n, x1, x2, …, xn şi apoi determină:
a) numărul de secvenţe munte din şirul iniţial;
b) numărul total de secvenţe munte obţinute pornind de la şirul iniţial până la cel care nu mai conţine nicio secvenţă munte;
c) numărul de elemente din şirul final care nu mai conţine secvenţe munte.

Date de intrare

Fișierul de intrare munte.in conține pe prima linie numărul n, iar pe următoarea linie numerele naturale x1, x2,…, xn separate două câte două prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire munte.out va conține pe prima linie un număr natural conform cerinţei a), pe a doua linie un număr natural conform cerinţei b), pe a treia linie un număr natural conform cerinţei c).

Restricții și precizări

  • 3 ≤ n ≤ 100
  • 0 ≤ xi ≤ 100000, 1 ≤ i ≤ n
  • Pentru rezolvarea corectă a cerinţei a) se obţine 20% din punctaj.
  • Pentru rezolvarea corectă a cerinţei b) se obţine 40% din punctaj.
  • Pentru rezolvarea corectă a cerinţei c) se obţine 40% din punctaj.
    Pentru testele date se asigură că şirul de numere dat iniţial conţine cel puţin o secvenţă munte.

Exemplu

munte.in

8
1 2 5 0 6 9 3 4

munte.out

2
4
4

Explicație

a) Sunt două secvenţe munte: 1 2 5 0 şi 0 6 9 3
b) După eliminarea vârfurilor secvenţelor munte, şirul nou este 1 2 0 6 3 4. Acest şir conţine 2 secvenţe munte: 1 2 0 şi 0 6 3. După eliminarea vârfurilor secvenţelor munte, şirul nou este 1 0 3 4. Noul şir nu mai conţine nicio secvenţă munte. În total sunt deci 4 secvenţe.
c) Şirul final care nu mai conţine secvenţe munte 1 0 3 4 are 4 elemente

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Munte:

//Serban Marinel
//O(nxn)
#include <fstream>

using namespace std;

#define MAX 1000000

ifstream fin("munte.in");
ofstream fout("munte.out");

int n, i, j, parcurgere, munti = 0, cati;
int x[110];
bool gasit_munte;

int main()
{
    fin >> n;
    for (i = 1; i <= n; ++i) fin >> x[i];
    parcurgere = 1;
    gasit_munte = true;
    while (gasit_munte)
    {
        gasit_munte = false; cati = 0;
        i = 1;
        while (i<n && x[i]>x[i+1]) i++; //trec peste primii descrescatori
        while (i <= n)
        {
            while (i<n && x[i]<x[i+1]) i++; //urc spre varf
            if (i<n)                        //daca mai am elemente
            {
                munti++; cati++;
                x[i] = MAX;         //asta e un varf - il voi elimina
                gasit_munte = true;
            }
            while (i<n && x[i]>x[i+1]) i++; //cobor muntele
            if (i<n && x[i]>x[i-1])
                i--;
            else
                if (i == n)
                    break;
        }
        if (parcurgere == 1)
        {
            fout << munti << '\n';
            parcurgere++;
        }
        //elimin varfurile
        i = 1;
        while (i < n)
        {
            while (x[i] != MAX && i<n) i++;
            for (j = i; j<n; ++j) x[j] = x[j+1];
        }
        if (gasit_munte) n -= cati;
    }
    fout << munti << '\n';
    fout << n << '\n';
    fout.close();

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1046 Munte

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1046 Munte de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!