Fie \( X = \overline{X_1 X_2 X_3…X_N} \) un număr natural din N cifre.

Definim secvență în numărul X orice număr format dintr-un grup de cifre situate pe poziții consecutive în X. De exemplu, pentru X=12543644 pot fi secvențe numerele: 5436, 12, 1, 364, 12543644, etc.

Definim secvență-maxim în șirul \(X\) o secvență \( \overline{X_K X_{K+1}…X_P…X_T} \) în care există o singură cifră \( X_P \) astfel încât \( X_K < X_{K+1} <…< X_P > X_{P+1} >…> X_T \) ( \(1≤K<P<T≤N\) și \(K,P,T\) sunt numere naturale). De exemplu, pentru X=12543644 secvențele-maxim sunt: 1254, 12543, 254, 2543, 364.

Cerință

Scrieți un program care citește numărul N, cele N cifre ale numărului X și care determină numărul total de secvenţe-maxim din numărul X.

Date de intrare

Fișierul de intrare secmax.in conține pe prima linie numărul natural N. Pe următoarea linie se află o succesiune de N cifre X₁X₂...X_N, reprezentând cifrele numărului X.

Date de ieșire

Fișierul de ieșire secmax.out va conține pe prima linie un număr natural, reprezentând numărul total de secvenţe-maxim din numărul X.

Restricții și precizări

8 ≤ N ≤ 25000
0 ≤ X₁, X₂ , ..., X_N ≤ 9
X₁ ≠ 0
o secvență-maxim este formată din cel puțin trei cifre

Exemplu

secmax.in

8
12543644

secmax.out

Explicație

Cifrele numărului X sunt: 1, 2, 5, 4, 3, 6, 4, 4.
Numărul conține 5 secvențe-maxim. Acestea sunt: 1254, 12543, 254, 2543, 364.

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 secmax:

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

char x[25005];
int s[25005], d[25005], n;
ifstream f("secmax.in");
ofstream g("secmax.out");

void citeste()
{
    f>>n;
    for (int i=1 ; i<=n ; i++)
        f>>x[i];
}



void solutie()
{
    int i;
    long long nrsec=0;
    s[1]=1;
    for (i=2 ; i<=n ; i++)
        if (x[i-1]<x[i])s[i]=s[i-1]+1;
        else s[i]=1;

    d[n]=1;
    for (i=n-1 ; i>=1 ; i--)
        if (x[i]>x[i+1]) d[i]=d[i+1]+1;
        else d[i]=1;

    for (i=1 ; i<=n ; i++)
        nrsec+=(s[i]-1)*(d[i]-1);
    g<<nrsec<<endl;
    cout<<nrsec<<endl;
}



int main()
{
    citeste();
    //cout<<n;
    solutie();
    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 #959 secmax

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #959 secmax 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!

Rezolvare completă PbInfo #959 secmax