問題
https://codeforces.com/contest/1353/problem/C (新しいタブで開く)
問題文
奇数 に対して、 のマス目を考える。
最初、それぞれのマスには 1 つのフィギュアがある。
以下の操作を最小で何回行えば、すべてのフィギュアを 1 マスに集められる?
ちょうど 1 つのフィギュアを選ぶ。
前後左右斜めの 8 マスのうち、どれかに移動させる。
すでにフィギュアのあるマスに移動させてもいいが、マス目の外には出せない。
制約
- の総和は を超えない
サンプル
3 1 5 499993
0 40 41664916690999888
考察
外側から内側にだんだん寄せていくのがよさそう。
あとは数学。
1 回の操作で真ん中に行けるのは 8 マス あるので 回操作が必要、2 回の操作では 16 マスで 32 回操作、...、 回の操作では マス、を足していけばいい。
一番外側で 回の操作が必要。
よって答えは、 。
コード
https://codeforces.com/contest/1353/submission/127017674 (新しいタブで開く)
void solve() { ll n; cin >> n; ll ans = 0; rep(i, n / 2 + 1) { ans += i * i * 8; } cout << ans << endl; }