問題
http://community.topcoder.com/stat?c=problem_statement&pm=12146&rd=15174
解き方
法則を導き出しても解けるが、少し複雑なことに気づけば
2分探索するのが確実。
N=1のときは必要なボールの数の計算が例外値となるので別に判定するのに注意。
コード
class FoxPaintingBalls {
public: long long theMax(long long R, long long G, long long B, int N) {
if(N==1)return R+G+B;
long long sum=(long long)N*(N+1)/2LL;
long long one=(long long)N*(N+1)/6LL;
if((N%3)!=1){
return min(R,min(G,B))/one;
}
long long low=0,high=max(R,max(G,B));
while(high-low>1){
long long mid=(low+high)/2LL;
if( min(R,min(G,B))/one>=mid && (R+G+B)/sum>=mid)low=mid;
else high=mid;
}
return low;
/*if(N==1)return R+G+B;
long long num=(long long)N*(N+1)/6;
if(N%3==1)return min(min(R,min(G,B))/num,(R+G+B)/((long long)N*(N+1)/2) );
return min(R,min(G,B))/num ;*/
}
};
public: long long theMax(long long R, long long G, long long B, int N) {
if(N==1)return R+G+B;
long long sum=(long long)N*(N+1)/2LL;
long long one=(long long)N*(N+1)/6LL;
if((N%3)!=1){
return min(R,min(G,B))/one;
}
long long low=0,high=max(R,max(G,B));
while(high-low>1){
long long mid=(low+high)/2LL;
if( min(R,min(G,B))/one>=mid && (R+G+B)/sum>=mid)low=mid;
else high=mid;
}
return low;
/*if(N==1)return R+G+B;
long long num=(long long)N*(N+1)/6;
if(N%3==1)return min(min(R,min(G,B))/num,(R+G+B)/((long long)N*(N+1)/2) );
return min(R,min(G,B))/num ;*/
}
};