Question

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 1012.

Exemplu
bomboane2.in

6
180 90 141 55 63 120
bomboane2.out

300
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.

Answer 1

#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;
}