POJ 3185: The Water Bowls

概要

20個のボウルが一列に並んでいて，あるボウルを選ぶとそのボウルと両側のボウルが一緒にひっくり返る．（端っこのボウルを選ぶと2個だけひっくり返る）
全てのボウルを正しい向きにするには，何回の選択が必要になるか？

解法

端っこから地道にシミュレーション．2^20通り全列挙は時間が足りない．
ただし，端の2つを反転する場合と反転しない場合に分け，中央のボウルを選択するのではなく，端のボウルを選択するようにする．

int calc(int *a){
    int cnt = 0;
    for(int i=0;i<19;++i){
        //for(int j = 0; j < 20; ++j) printf("%d", a[j]);
        //printf("\n");
        if(a[i]){
            ++cnt;
            for(int j=0;j<3;++j) a[i+j]^=1;
        }
    }
    //printf("%d\n", cnt);
    return a[19]==0 ? cnt: 32;
}

int a[32];
int b[32];
int main(){
    int s = 0;
    for(int i = 0; i < 20; ++i){
        scanf("%d", a+i);
        b[i] = a[i];
        //s = (s << 1) | a[i];
    }
    b[0] ^= 1; b[1] ^= 1;
    printf("%d\n", min(calc(a), calc(b) + 1));
    return 0;
}