WARush

SRMの結果とか、解けた問題のコードを書いていきます

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();
    }
};