lamps.cpp

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int lamps, opsToDo;
int correctLamp[201];
bool lampState[201];

int solutions;
bool solution[1000][201];

int compareSolutions(const void *p1, const void *p2) {
    bool *s1 = (bool *) p1;
    bool *s2 = (bool *) p2;
    for (int i = 1; i < lamps; ++i) {
        if (s1[i] == 1 && s2[i] == 0) return 1;
        else if (s2[i] == 1 && s1[i] == 0) return -1;
    }
    return 0;
}

bool isMatch() {
    for (int i = 1; i < lamps; ++i) {
        if (correctLamp[i] != -1 && correctLamp[i] != lampState[i]) {
            return false;
        }
    }
    return true;
}
void printLamps() {
    for (int i = 1; i < lamps; ++i) {
        cout << lampState[i];
    }
    cout << endl;
}

void applyOps(int a, int b, int c, int d) {
    if (a) {
        for (int i = 1; i < lamps; ++i) {
            lampState[i] = !lampState[i];
        }
    }
    if (b) {
        for (int i = 1; i < lamps; ++i) {
            if (i % 2 == 1) {
                lampState[i] = !lampState[i];
            }
        }
    }
    if (c) {
        for (int i = 1; i < lamps; ++i) {
            if (i % 2 == 0) {
                lampState[i] = !lampState[i];
            }
        }
    }
    if (d) {
        for (int i = 1; i < lamps; ++i) {
            if ((i - 1) % 3 == 0) {
                lampState[i] = !lampState[i];
            }
        }
    }
}

void printSolutions() {
    if (solutions == 0) {
        cout << "IMPOSSIBLE" << endl;
    } else {
        for (int i = 0; i < solutions; ++i) {
            for (int j = 1; j < lamps; ++j) {
                cout << solution[i][j];
            }
            cout << endl;
        }
    }
}

void findSolutions() {
  for (int a = 0; a <= 1; ++a) {
    for (int b = 0; b <= 1; ++b) {
      for (int c = 0; c <= 1; ++c) {
        for (int d = 0; d <= 1; ++d) {
          int ops = a+b+c+d;
          if (ops <= opsToDo &&
              ((opsToDo % 2 == 0 && ops % 2 == 0) ||
               (opsToDo % 2 == 1 && ops % 2 == 1))
             ) {
            applyOps(a, b, c, d);
            if (isMatch()) {
              memcpy(solution[solutions], lampState, sizeof(bool)*201);
              solutions++;
            }
            applyOps(a, b, c, d);
          }
        }
      }
    }
  }
}

int main() {
    memset(correctLamp, -1, sizeof(int)*201);
    memset(lampState, 1, sizeof(bool)*201);
    
    cin >> lamps >> opsToDo; lamps++;

    int i;
    while (cin >> i && i != -1) {
        correctLamp[i] = true;
    }
    while (cin >> i && i != -1) {
        correctLamp[i] = false;
    }
    
    findSolutions();
    qsort(solution, solutions, sizeof(bool)*201, compareSolutions);
    printSolutions();
    
    return 0;
}

palindrom.cpp

#include <cstring>
#include <iostream>
#include <string>

using namespace std;

string s;

int mem[1100][1100];
vector<vector int> > mem;

int mods(int i1, int i2) {
    if (mem[i1][i2] == -1) {
        if (s[i1] == s[i2]) {
            if (i1 + 1 == i2 || i1 == i2) mem[i1][i2] = 0;
            else mem[i1][i2] = mods(i1 + 1, i2 - 1);
        } else if (s[i1] != s[i2]) {
            mem[i1][i2] = 1 + min(mods(i1+1, i2),
                                  mods(i1, i2-1));
        }
    }
    return mem[i1][i2];
}

int main() {
    int n; cin >> n;
    getline(cin, s);
    
    memset(mem, -1, sizeof(int)*1100*1100);

    cout << mods(0, s.length() - 1) << endl;
    
    return 0;
}