問題はこちら
No.71 そろばん - yukicoder
N個のうちk個を上の珠として扱うと
上の珠の状態はk+1通り
下の珠の状態は(N-k)+1通りなので
扱える最大の値は(k+1)(N-k+1)-1となる
ところでこれは、和が一定の2数の積を最大化する問題なので、2数が近くなるようにすれば良い
(∵ab=((a+b)^2-(a-b)^2)/4)
よってk=floor(N/2)としたときの値が求める答え
int main(){ int n; scanf("%d",&n); printf("%ld",1L*(n/2+1)*(n-n/2+1)-1); return 0; }
この結果は
Nが偶数の時(N/2+1)(N/2+1)-1=N*N/4+N
Nが奇数の時((N-1)/2+1)((N+1)/2+1)-1=(N*N-1)/4+N
となるので、結局 floor(N*N/4)+N とまとめられる
n;main(){n=scanf("%d",&n)>printf("%ld",1L*n*n/4+n);}
52B