Problem C

Not a hard one. I submitted this one pretty long after my submission on B just because I prefer problem D instead of this 😀 After feeling no much hope in problem D, I tried to solve this problem and got it right in about fifteen minutes 😀

In my solution, I do an iteration over some steps and for each step the code performed operation(s) below:

  1. Search the adjacent pair of even numbers. If they are exist divide them by two otherwise go to 2
  2. Search the adjacent pair of odd numbers which corresponding numbers are not both one. If they are exist, add both of them by one and divide them by 2
  3. Search the adjacent odd-even pair. Increase both of them by 1 and do either operation 1 or 2.

It can be easily proven that the sum of those four numbers will always decreased by those three operations, except for some small cases which we need to prove it separately (e.g. {1,2,1,1}, {1,2,1,2}). Hence, the 4-tuple will converge to {1,1,1,1} in logarithmic time.

int a[5];

inline int next (int idx) { return (idx + 1) % 4; }

vector <pair <char, int> > ret;

int main () {
    REP (i, 4) scanf ("%d", &a[i]);

    bool finish = false;

    while (!finish) {
        if (a[0] == 1 && a[1] == 1 && a[2] == 1 && a[3] == 1) {
            finish = true;
            break;
        }
        bool found = false;
        REP (i, 4) {
            if (a[i] % 2 == 0 && a[next (i)] % 2 == 0) {
                a[i] /= 2, a[next (i)] /= 2;
                ret.PB (MP ('/', i + 1));
                found = true;
                break;
            } else if (a[i] % 2 == 1 && a[next (i)] % 2 == 1 && (a[i] != 1 || a[next (i)] != 1)) {
                a[i]++, a[next (i)]++;
                ret.PB (MP ('+', i + 1));
                a[i] /= 2, a[next (i)] /= 2;
                ret.PB (MP ('/', i + 1));
                found = true;
                break;
            }
        }
        if (!found) {
            REP (i, 4) {
                if (a[i] % 2 == 1 && a[next (i)] % 2 == 0) {
                    a[i]++, a[next (i)]++;
                    ret.PB (MP ('+', i + 1));
                    break;
                }
            }
        }
        if (SIZE (ret) > 1000) break;
    }

    if (finish) {
        REP (i, SIZE (ret)) cout << ret[i].F << ret[i].S << endl;
    } else puts ("-1");

    return 0;
}
Advertisements