Cod sursa(job #636925)

Utilizator Teodor94Teodor Plop Teodor94 Data 20 noiembrie 2011 02:15:17
Problema PalM Scor 20
Compilator cpp Status done
Runda .com 2011 Marime 2.05 kb
#include<cstdio>
#include<cstring>

const int N = 505;

int n, st[N], dr[N], m[N][N];
char s[N];

inline int min(int x, int y) {
    return x < y ? x : y;
}

bool alfa(int x, int y, int tip) {
    for (int i = x; i < y; ++i)
        if (tip == 1) {
            if (s[i] > s[i+1])
                return false;
        }
        else {
            if (s[i] < s[i+1])
                return false;
        }
    return true;
}

int cautbin(int x, int tip) {
    int i, pas = (1 << 9);

    for (i = 0; pas; pas >>= 1)
        if (tip == 1) {
            if (x - i - pas >= 0 && alfa(x - i - pas, x, 1))
                i += pas;
        }
        else {
            if (x + i + pas < n && alfa(x, x + i + pas, 2))
                i += pas;
        }

    if (tip == 1)
        return x - i;

    return x + i;
}

void munte() {
    for (int i = 0; i < n; ++i) {
        st[i] = cautbin(i, 1);
        dr[i] = cautbin(i, 2);
    }
}

bool palind(int x, int y) {
    while (s[x] == s[y] && x < y) {
        ++x;
        --y;
    }

    if (x >= y)
        return true;

    return false;
}

bool mount(int x, int y) {
    while (s[x] <= s[x + 1] && x <= y)
        ++x;

    if (x >= y)
        return true;

    while (s[x] >= s[x + 1] && x <= y)
        ++x;

    if (x >= y)
        return true;

    return false;
}

void rez() {
    int lgmax = 0;

    for (int i = 0; i < n - 1; ++i)
        for (int j = i + 1; j < n; ++j)
            m[i][j] = mount(i, j);

    //for (int i = 0; i < n - 1; ++i, printf("\n"))
        //for (int j = i + 1; j < n; ++j)
            //printf("%d %d %d\n", i, j, m[i][j]);

    for (int i = 0; i < n - 1; ++i)
        for (int j = n - 1; j >= i + 1; --j)
            if (j - i + 1 <= lgmax)
                break;
            else
            if (m[i][j] && palind(i, j) && j - i + 1 > lgmax) {
                lgmax = j - i +1;
                break;
            }

    printf("%d\n", lgmax);
}

int main() {
    freopen("palm.in", "r", stdin);
    freopen("palm.out", "w", stdout);

    gets(s);
    n = strlen(s);

    //munte();

    rez();

    return 0;
}