Ответ 1
Насколько я понимаю, основное замечание состоит в том, что нам никогда не нужно выполнять более одного переключателя в любой позиции. Это связано с тем, что переключение в два раза такое же, как и неключение вообще, поэтому все четные переключатели эквивалентны 0 переключателям, и все нечетные переключатели не хуже 1 коммутатора.
Другое дело, что порядок переключателей не имеет значения. переключение i-го и я + 1-го элементов совпадает с переключением я + 1-го, а затем i-го. Образец, полученный в конце, тот же.
Используя эти два наблюдения, мы можем просто попробовать все возможные способы применения коммутатора к массиву n длины. Это можно сделать рекурсивно (т.е. Сделать переключатель с индексом i/не делать переключатель с индексом i, а затем попробовать я + 1) или перечислить всю битовую маску 2 ** nn бит и использовать их для применения переключателей до тех пор, пока один из них не создаст целевое значение.
Ниже мой хак в решении. Я собрал массивы в ints и использовал их как битмаски для упрощения операций. Это отображает индексы, которые необходимо переключить, чтобы получить целевой массив, и печатает "Невозможно", если цель недоступна.
#include <cstdio>
int flip(int mask, int bit){
return mask^(1<<bit);
}
int switch_(int mask, int index, int n){
for(int i=-1;i<=+1;i++){
if ((index+i)>=0 && (index+i)<n) mask=flip(mask,index+i);
}
return mask;
}
int apply(int source, int flips, int n){
int result=source;
for(int i=0;i<n;i++){
if (flips&(1<<i)) result=switch_(result,i,n);
}
return result;
}
void solve(int source, int target, int n){
bool found=false;
int current=0;
int flips=0;
for(flips=0;flips<(1<<n) && !found;flips++){
current=apply(source,flips,n);
found=(current==target);
}
if (found){
flips--;
for(int i=0;i<n;i++){
if (flips&(1<<i)) printf("%d ",n-i-1); //prints the indices in descending order
}
printf("\n");
}
else{
printf("Impossible\n");
}
}
int array2int(int* arr, int n){
int ret=0;
for(int i=0;i<n;i++){
ret<<=1;
if (arr[i]==1) ret++;
}
return ret;
}
int main(){
int source[]={0,0,0,0};
int target[]={1,1,1,1};
int n=4;
solve(array2int(source,n),array2int(target,n),n);
return 0;
}