AtCoder Grand Contest 014: A - Cookie Exchanges

,

http://agc014.contest.atcoder.jp/tasks/agc014_a

なんだかいけそうだったので試したら当たった。計算量解析は後からだけど、すこし面白かった。

solution

愚直にやる。停止するか過去の状態に一致する(つまりloopが検出される)まで。 最終的にどれもが$\frac{A + B + C}{3}$へ近付いていき、特に差は毎回半分ぐらいになると見てよいので、$O(\log (A+B+C))$である。

implementation

#include <cstdio>
#include <algorithm>
#include <array>
#include <set>
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
int main() {
    array<int, 3> a;
    scanf("%d", &a[0]);
    scanf("%d", &a[1]);
    scanf("%d", &a[2]);
    whole(sort, a);
    set<array<int, 3> > used;
    while (     a[0] % 2 == 0
            and a[1] % 2 == 0
            and a[2] % 2 == 0) {
        used.insert(a);
        ll sum = a[0] +(ll) a[1] + a[2];
        a[0] = (sum - a[0]) / 2;
        a[1] = (sum - a[1]) / 2;
        a[2] = (sum - a[2]) / 2;
        whole(sort, a);
        if (used.count(a)) break;
    }
    if (used.count(a)) {
        printf("-1\n");
    } else {
        printf("%d\n", int(used.size()));
    }
    return 0;
}