SRM617 Div1 Easy "MyLongCake"
問題
まだ
訳
細長いケーキがある。単純にこのケーキは1次元のものと考えることができる。ケーキの長さはnである。今日は友達が何人か来ることになっている。友達が来る前に、ケーキを切り分けておくことにした。友達が来たときに、あなたは次のようにケーキを渡そうと思っている。最初の友達が来たときに、ケーキを先頭から続けて何切れか渡す。次に来た友達には残ったものの内、先頭から続けて何切れか渡す・・というように。もちろん、公平になるよう、それぞれの友達が受け取るケーキの量は同じになるようにしたい。(切り分けたケーキの個数は違っててもよいが、ケーキの長さの合計は同じにしなくてはならない)友達が来る前にケーキを切り分けておきたいのだが、実際に何人来るのかは分かっていなかった。ただ、nより小さい、nを割り切れる数だけの友達が来ることは分かっていた。
あなたはint nが与えられる。上記のようなケーキの切り分け方のうち、切り分ける数が最も少なくなるようにケーキをきったとき、その数がいくつになるかを返せ。
制約
2 <= n <= 10^6
考えたこと
12だったら{2,2,2,2,2,2} {3,3,3,3} {4,4,4} {6,6} ってなるように切るのをシミュレートしてく。
なんでこれでいいかはわからん!ちくしょー!
ソースコード
class MyLongCake { public: int cut(int n) { queue<int> que; que.push(n); for (int d = 2; d * 2 <= n; d++) { if (n % d != 0) continue; int sum = 0; int rl = 0; int rr = 0; while (sum < n) { if (rl == 0) rl = d; if (rr == 0) { rr = que.front(); que.pop(); } int o = min(rl, rr); rl -= o; rr -= o; que.push(o); sum += o; } } return que.size(); } };