Cerința

Se dă un şir x format din n numere naturale nenule. Pentru fiecare element x_i din şir să se verifice dacă există un număr k astfel încât elementul x_i să fie egal cu suma primelor k elemente din şir.

Date de intrare

Fișierul de intrare summit.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire summit.out va conține pe linia i valoarea k dacă elementul x_i este egal cu suma primelor k elemente din şir, sau 0 în caz contrar, pentru fiecare i de la 1 la n.

Restricții și precizări

2 ≤ n ≤ 1.000.000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 2.000.000.000

Exemplu

summit.in

3
1 2 3

summit.out

1
0
2

Explicație

Elementul x₁=1 este suma primelor k=1 elemente din şir, elementul x₂=2 nu poate fi scris ca suma primelor k elemente din şir oricare ar fi k, iar elementul x₃=3 este suma primelor k=2 elemente din şir.

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

#include <fstream>

using namespace std;
ifstream f("summit.in");
ofstream g("summit.out");

long long n , i, k , mij , x , s[1000001];

long long caut(long long st , long long dr)
{
    if ( st > dr ) return 0 ;
    else
     {
        mij = ( st + dr ) / 2 ;
        if ( s[mij] == x ) return mij ;
        else
         {
            if ( x < s[mij] ) caut(st,mij-1) ;
            else caut(mij+1,dr) ;
         }
     }
}

int main()
{
    f >> n ;
    f >> x ;
    s[1] = x ;
    g << 1 << "\n" ;
    for ( i=2 ; i<=n ; i++ )
    {
        f >> x ;
        s[i] = s[i-1] + x ;
        k = caut(1,i-1) ;
        g << k << "\n" ;
    }
    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 #1865 Summit

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