SRM552 Div1 Easy(250) FoxPaintingBalls

TopCoder

FoxPaintingBalls

何通りに塗り方があるか、ではなく、何個の三角形が作れるか。

N=3kもしくはN=3k+2ならば、それぞれの色は同数。N=3k+1の場合、1個多い1色がある。直接計算できるのかもしれないけど、二分探索した方が簡単だと思う。オーバフローに注意。

#include <algorithm>
using namespace std;

class FoxPaintingBalls{public:
long long theMax( long long R, long long G, long long B, int N )
{
    if ( N%3==0 || N%3==2 )
        return min(R,min(G,B)) / (1LL*N*(N+1)/6);

    long long p = (1LL*N*(N+1)/2-1)/3;
    long long ans = 0;
    for ( long long b=1LL<<62; b>0; b>>=1 )
    {
        long long n = ans+b;
        //if ( R>=n*p && G>=n*p && B>=n*p && R+G+B-3*n*p>=n )
        if ( R/n>=p && G/n>=p && B/n>=p && R+G+B-n>=0 && (R+G+B-n)/n>=3*p )
            ans += b;
    }
    return ans;
}};