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.

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