LRKPALIN

lrkpalin.cpp

#include <cstdio>
#include <iostream>
#include <cstring>

FILE *in, *out;

char s[10001];

int k, q, len, i, x, y;
short table[10000][10000];

void build_table(){
    int length, i;

    for (i = 0; i < len; i++){
        table[i][i] = 0;
    }

    for (i = 0; i < len-1; i++){
        if (s[i] != s[i+1]){
            table[i][i+1] = 1;
            table[i+1][i] = 1;
        }
    }

    for (length = 3; length != len; length++){
        for (i = 0; i < len-length+1; i++){
            table[i][i+length-1] = table[i+1][i+length-2];
            if (s[i] != s[i+length-1])
                table[i][i+length-1] += 1;
        }
    }
}

int main(){
    in = fopen("LRKPALIN.INP", "r");
    out = fopen("LRKPALIN.OUT", "w");
    fscanf(in, "%s%d%d", s, &k, &q);
    len = strlen(s);
    build_table();

    for (i = 0; i < q; i++){
        fscanf(in, "%d%d", &x, &y);
        --x;
        --y;
        //std::cout << table[x][y] << std::endl;
        if (table[x][y] <= k)
            fputs("1\n", out);
        else
            fputs("0\n", out);
    }

    fclose(in);
    fclose(out);
}