Se consideră un șir de N numere ce reprezintă numărul de bomboane din N punguțe așezate în linie. Georgel pornește din dreptul primei punguțe și ia din ea o bomboană, apoi trece la următoarea și ia din ea două bomboane și continuă în acest fel luând de fiecare data cu o bomboană mai mult decât a luat din punga precedentă. Dacă au mai rămas bomboane în punguțe astfel încât el să mai poată face o tură completă, continuă să ia bomboane, câte una în plus față de punguța din care a luat anterior. Dacă nu mai sunt bomboane, se oprește și își numără bomboanele adunate în total.

Cerința

Cunoscându-se numărul N de punguțe și numărul de bomboane din fiecare punguță, să se stabilească numărul de bomboane pe care le va aduna Georgel.

Date de intrare

Din fișierul bomboane2.in se citesc, de pe prima linie numărul N de punguțe, iar de pe linia a doua, N numere naturale reprezentând numărul de bomboane din fiecare punguță, în ordinea în care se află. Numerele sunt despărțite între ele prin spații.

Date de ieșire

În fișierul bomboane2.out se afișează valoarea M, reprezentând numărul de bomboane pe care le poate aduna Georgel.

Restricții și precizări

1 ≤ N ≤ 100000
Numărul bomboane din fiecare punguță este un număr natural nenul mai mic decât 10¹².

Exemplu

bomboane2.in

6
180 90 141 55 63 120

bomboane2.out

Explicație

Georgel pornește de la punguța numărul 1 şi ia o bomboană, din a doua ia două bomboane, din a treia 3 bomboane, din a patra 4, din a cincea 5, din a șasea 6; la următoarea tură ia din prima 7 bomboane, din a doua 8, din a treia 9, din a patra 10 și în continuare 11, 12; la următoarea tura ia 13, 14, 15, 16 17, 18, iar la a patra tură ia 19, 20, 21, 22, 23, 24 bomboane. La a cincea tură se oprește deoarece în unele punguțe nu se mai află numărul de bomboane necesar pentru a termina o nouă tură completă. Astfel adună în total 300 de bomboane.

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

// Implementare: Cristi Dospra
// Punctaj: 100p
// Complexitate: ( N * log Ture )

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

#define Nmax 1000002

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

long long v[Nmax];

int main(){

    long long N, MaxVal = -1;

    fin >> N;

    for ( int i = 1; i <= N; ++i ){
        fin >> v[i];
        MaxVal = max ( MaxVal, v[i] );
    }

    long long Ture, st = 0, dr = sqrt ( double ( MaxVal ) ) * sqrt(double(2)) ;

    while ( st <= dr ){
        long long mid = ( st + dr ) >> 1;

        bool ok = 1;
        for ( int i = 1; i <= N; ++i ){
            if ( v[i] < mid * i + ( N * mid * (mid-1) ) / 2 ){
                ok = 0;
                break;
            }
        }

        if ( ok ){
            Ture = mid;
            st = mid + 1;
        }
        else
            dr = mid - 1;
    }

    N *= Ture;

    fout << ( N * (N+1) / 2 );

    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 #1764 Bomboane2

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