#include #include #define MAX 50050 int N; int ch = 0; char vlak[MAX]; char novy_vlak[MAX]; struct podvlak { int prvni, posledni; int delka; } **podvlaky; int main(int argc, char ** argv) { // přečteme vstup scanf("%d", &N); scanf("%s", vlak); // triviální vlak délky 1 if (N == 1) { printf("0\n\n"); return 0; } // inicializace -- podvlaky délky 1 podvlaky = calloc(N, sizeof(struct podvlak *)); podvlaky[0] = calloc(N, sizeof(struct podvlak)); for (int i=0;i podvlaky[d-1][j+1].delka) ktery = j; else ktery = j+1; // na okrajích je stejný vagón if ((vlak[j] == vlak[j+d]) && // zkusíme použít vlak, který obsahuje oba vagóny z okraje ((d == 1 ? 0 : podvlaky[d-2][j+1].delka) + 2 > podvlaky[d-1][ktery].delka)){ podvlaky[d][j].delka = (d == 1 ? 0 : podvlaky[d-2][j+1].delka) + 2; podvlaky[d][j].prvni = j; podvlaky[d][j].posledni = j+d; } else { podvlaky[d][j].delka = podvlaky[d-1][ktery].delka; podvlaky[d][j].prvni = podvlaky[d-1][ktery].prvni; podvlaky[d][j].posledni = podvlaky[d-1][ktery].posledni; } } } int delka = 0; int levy = podvlaky[N-1][0].prvni; int pravy = podvlaky[N-1][0].posledni; // Do nového vlaku nakopírujeme jen ty vagóny, které tvoří palindrom while (1) { novy_vlak[podvlaky[pravy-levy][levy].prvni] = vlak[podvlaky[pravy-levy][levy].prvni]; novy_vlak[podvlaky[pravy-levy][levy].posledni] = vlak[podvlaky[pravy-levy][levy].posledni]; int lt = levy+1, rt = pravy-1; if ((delka += 2) >= podvlaky[N-1][0].delka) break; levy = podvlaky[rt-lt][lt].prvni; pravy = podvlaky[rt-lt][lt].posledni; } // Vypíšeme vagóny, které jsme vyhodili (indexovano od 1) printf("%d\n", N - podvlaky[N-1][0].delka); for (int d=0,i=0;i