IOI '94 P4 - The Clocks

#include <iostream>

using namespace std;

const int N = 9, M = 9; // N is number of clocks, M is number of types of move

int moves[M] {
    0b110110000, // ABDE
    0b111000000, // ABC
    0b011011000, // BCEF
    0b100100100, // ADG
    0b010111010, // BDEFH
    0b001001001, // CFI
    0b000110110, // DEGH
    0b000000111, // GHI
    0b000011011, // EFHI
};

int main() {
    int need = 0;
    for (int i = 0; i < N; ++i) {
        int x; cin >> x;
        need <<= 2;
        need += (4-x)%4;
    }
    int bestMask = 0, minSteps = 4*M;
    for (int bitmask = 0; bitmask < (1 << (2*M)); ++bitmask) {
        int result = 0, steps = 0;
        for (int i = 0; i < M; ++i) {
            int cnt = (bitmask >> (2*i)) & 3;
            steps += cnt;
            for (int j = 0; j < N; ++j) {
                if (moves[i] & (1 << j)) {
                    int cur = (result >> (2*j)) & 3;
                    result += cnt * (1 << (2*j));
                    if (cur + cnt >= 4) result -= (1 << (2*j+2));
                }
            }
        }
        if (result == need && steps < minSteps) {
            minSteps = steps;
            bestMask = bitmask;
        }
    }
    for (int i = 0; i < M; ++i) {
        int cnt = (bestMask >> (2*i)) & 3;
        for (int j = 0; j < cnt; ++j) cout << i+1 << ' ';
    }
    cout << endl;
    return 0;
}