Rezolvare completă PbInfo #2301 secv

Se consideră două numerele naturale K și S și un șir de N numere naturale a[1], a[2],…, a[N]. O secvenţă de lungime K este un subşir format din K elemente aflate pe poziţii consecutive în şir: a[i], a[i+1],.., a[i+k-1]. Parcurgând șirul de la stânga la dreapta, începând cu primul element, se elimină prima secvență de lungime K, cu suma elementelor strict mai mare decât numărul S. În urma ștergerii șirul va avea N-K elemente: a[1], a[2],…, a[N-K]. Operația de ștergere continuă după aceleași reguli până când nu mai există secvențe care pot fi eliminate.

Cerința

Să se scrie un program care citind numerele N, K, S și cele N elemente din șir rezolvă cerințele:
1) Determină numărul secvențelor care se vor elimina respectând condiția din enunț.
2) Considerând că în șirul citit nu sunt posibile eliminări de secvențe conform condiției din enunț, programul determină numărul de elemente ai din șir cu proprietatea următoare: ștergerea lui a[i] conduce la obținerea unui șir în care se mai poate elimina cel puțin o secvență de K elemente cu sumă strict mai mare ca S.

Date de intrare

Fișierul de intrare secv.in conține pe prima linie un număr natural P; numărul P poate avea doar valoarea 1 sau valoarea 2. A doua linie conține, în această ordine, separate prin câte un spațiu, numerele N, K și S. A treia linie conține, în ordine elementele șirului, despărțite prin câte un spațiu.

Date de ieșire

Dacă valoarea lui P este 1, se va rezolva numai cerinta 1). În acest caz, fişierul de ieşire secv.out va conține pe prima linie un număr natural reprezentând numărul secvențelor eliminate.
Dacă valoarea lui P este 2, se va rezolva numai cerinta 2). În acest caz, fişierul de ieşire secv.out va conține pe prima linie un număr natural reprezentând numărul elementelor din șir care au proprietatea că ștergerea fiecăruia în parte ar genera un șir în care se mai pot elimina cel puțin o secvență de K elemente cu sumă strict mai mare ca S.

Restricții și precizări

  • 0 < N ≤ 1 000 000 și K ≤ N
  • 0 < S ≤ 1 000 000 000
  • 0 ≤ a[1], a[2],...,a[N] ≤ 1 000

Exemplul 1:

secv.in

1
14 3 7
1 2 1 3 1 4 5 2 1 4 1 8 2 3

secv.out

3

Explicație

Prima secvență de sumă strict mai mare decât 7 începe de pe poziția 4 și este formată din elementele 3 1 4; după eliminarea ei șirul devine: 1 2 1 5 2 1 4 1 8 2 3.
A doua secvență ce va fi ștearsă începe de pe poziția 2 și este formată din 2 1 5; după eliminarea ei șirul devine: 1 2 1 4 1 8 2 3.
A treia secvență ce va fi ștearsă începe de pe poziția 4 și este formată din elementele 4 1 8; după eliminarea ei șirul devine: 1 2 1 2 3 și nu mai conține nici o secvență de 3 elemente alăturate de sumă mai mare decât 7.

Exemplul 2:

secv.in

2
9 7 18
3 3 2 1 3 3 3 3 1

secv.out

2

Explicație

Două elemente au această proprietate. Dacă eliminăm elementul al treilea, de valoare 2, se poate obține șirul 3 3 1 3 3 3 3 1 care conține o secvență de 7 elemente de sumă strict mai mare ca 18, începând cu elementul de pe poziția 1.
Dacă eliminăm elementul al patrulea, de valoare 1, se poate obține șirul 3 3 2 3 3 3 3 1 care conține o secvență de 7 elemente de sumă strict mai mare ca 18, începând cu elementul de pe poziția 1.

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

#include <cstdio>
#define MAXN 1000001

using namespace std;

int A[MAXN], B[MAXN], N, K, S, P, i;

void solve1() {
    int ul = 0, Nr = 0, i;

    for (i = 1; i <= N; ++i) {
        B[ul + 1] = B[ul] + A[i]; //sume partiale
        ++ul;
        if (ul >= K && B[ul] - B[ul - K] > S) {
            ++Nr;
            ul -= K;
        }
    }
    printf("%d\n", Nr);
}

void solve2() {
    int ul = 0, i;

    for (i = 1; i <= N; ++i) {
        B[ul + 1] = B[ul] + A[i];
        ++ul;
        if (ul >= K && B[ul] - B[ul - K] > S) {
            printf("%d ", ul - K + 1);
            ul -= K;
        }
    }
}

void solve3() {
    int pr = 1, ul = 0, Nr = 0, i;

    for (i = 1; i <= N; ++i)
        A[i] += A[i - 1];

    for (i = 1; i <= N; ++i) {
        if (i + K <= N) {
            while (pr <= ul && A[i + K] - A[i - 1] >= A[B[ul] + K] - A[B[ul] - 1])
                --ul;
            B[++ul] = i;
        }
        if (A[B[pr] + K] - A[B[pr] - 1] - (A[i] - A[i - 1]) > S)
            ++Nr;
        if (B[pr] == i - K)
            ++pr;
    }
    printf("%d", Nr);
}

int main()
{
    freopen("secv.in", "r", stdin);
    freopen("secv.out", "w", stdout);

    scanf("%d", &P);
    scanf("%d %d %d", &N, &K, &S);
    for (i = 1; i <= N; ++i)
        scanf("%d", &A[i]);

    if (P == 1) solve1();
    if (P == 2) solve3();

    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 #2301 secv

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