# CFR 795 A. Amusement Park ( Greedy, Ternary Search )

Problem - A - Codeforces

The first line contains three integers n, c1 and c2 (1 ≤ n ≤ 200 000, 1 ≤ c1, c2 ≤ 1e7) — the number of visitors and parameters for determining the ticket prices for a group. The second line contains the string of length n, which consists of zeros and ones. If the i-th symbol of the string is zero, then the i-th visitor is a pupil, otherwise the i-th person is an adult. It is guaranteed that there is at least one adult. It is possible that there are no pupils.

O( lg N ) / O( N )

```#include <stdio.h>
#include <assert.h>

int N, C1, C2;
char seq[ ( int ) 2e5 ];

long long sqr( int x ) {
return 1LL * x * x;
}

long long calc( int g ) {
int ln = N / g; // number of people in less group
int lc = g - N % g; // number of groups of less people
int gn = ln + 1;
int gc = N % g;
return ( sqr( ln - 1 ) * C2 + C1 ) * lc + ( sqr( gn - 1 ) * C2 + C1 ) * gc;
}

signed main() {
scanf( "%d %d %d", &N, &C1, &C2 );
scanf( "%s", seq );
for( int i = 0; i < N; ++i ) {
if( seq[ i ] == '1' ) {
} else {
++child;
}
}
int lb = 1, ub = adult;
while( ub - lb > 10 ) {
int x = lb + ( ub - lb ) / 3;
int y = lb + ( ub - lb ) * 2 / 3;
long long a = calc( lb ), b = calc( x ), c = calc( y ), d = calc( ub );
if( a <= b && b <= c && c <= d ) {
ub = x;
} else if( a >= b && b <= c && c <= d ) {
ub = y;
} else if( a >= b && b >= c && c <= d ) {
lb = x;
} else if( a >= b && b >= c && c >= d ) {
lb = y;
} else {
assert( 0 );
}
}
long long ans = 1LL << 60;
for( int i = lb; i <= ub; ++i ) {
long long t = calc( i );
if( ans > t ) {
ans = t;
}
}
printf( "%lld\n", ans );
return 0;
}
```