#include #ifdef DEBUG #include #endif #include using namespace std; const int MAX_N = 1000000; int n; int field[2][MAX_N]; int stomp[2][3]; int stompCost(int index) { int cost = 0; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 3; ++j) { if (stomp[i][j] == 1) { if (field[i][j + index] == 1) { cost -= 1; } else { cost += 1; } } } } return cost; } void doStomp(int index) { for (int i = 0; i < 2; ++i) { for (int j = 0; j < 3; ++j) { if (stomp[i][j] == 1) { if (field[i][j + index] == 1) { field[i][j + index] = 0; } else { field[i][j + index] = 1; } } } } } int main() { ifstream fin("input.txt"); assert( fin ); fin >> n; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 3; ++j) { fin >> stomp[i][j]; } } for (int i = 0; i < 2; ++i) { for (int j = 0; j < n; ++j) { fin >> field[i][j]; } } #ifdef DEBUG for (int i = 0; i < 2; ++i) { for (int j = 0; j < 3; ++j) { cout << " " << stomp[i][j]; } cout << endl; } for (int i = 0; i < 2; ++i) { for (int j = 0; j < n; ++j) { cout << " " << field[i][j]; } cout << endl; } #endif // Approccio greedy: calcola il miglior stomp possibile e usa quello. // Non è computazionalmente ottimo. Si potrebbe anche fare un'altra // considerazione: finiti gli stomp a sinistra non posso più cambiare // (se posso) le due caselle più a sinistra. Il fatto di cercare il // minimo a sinistra e di ragionare ricorsivamente (pensando: minimo // totale = minimo a sx + minimo nella parte rimanente) non conduce a // una soluzione accettabile perché gli ulteriori stomp a sinistra // potrebbero aumentare il numero di 1 a destra. int bestIndex; int best_so_far; do { bestIndex = 0; best_so_far = 0; for (int i = 0; i < n - 2; ++i) { int stC = stompCost(i); #ifdef DEBUG cout << "Indice " << i << ", costo: " << stC << ", costo migliore: " << best_so_far << endl; #endif if (stC < best_so_far) { bestIndex = i; best_so_far = stC; } } #ifdef DEBUG cout << "Costo migliore: " << best_so_far << ", indice " << bestIndex << endl; #endif if (best_so_far < 0) { doStomp(bestIndex); #ifdef DEBUG for (int i = 0; i < 2; ++i) { for (int j = 0; j < n; ++j) { cout << " " << field[i][j]; } cout << endl; } #endif } } while (best_so_far < 0); int opt = 0; for (int i = 0; i < 2; ++i) { for (int j = 0; j < n; ++j) { if (field[i][j] == 1) { ++opt; } } } ofstream fout("output.txt"); assert( fout ); fout << opt << endl; fout.close(); return 0; }