SPOJ #692. Fruit Farm

Another palindrome related problem. Actually nothing too theoretical here, but please keep following hints in mind:

1.　How to check whether a natural number is Palindrome
　　Not sure whether there's closed form to Palindrome, I simply used a naive algorithm to check: log10() to get number of digits, and check mirrored digits.

2.　Pre calculation
　　1<=a<=b<=1000. so we can precalculate all Palindromes within that range beforehand.

3.　Understand problem statement, only start from a Palindrome
　　For each range, it must start from a Palindrome - we can simply skip non-Palindromes. And don't forget to remove all tailing non-Palindromes.

// 692 Fruit Farm

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <cstdlib>

using namespace std;

/////////////////////////

#define gc getchar_unlocked

int read_int()

{

  char c = gc();

  while(c<'' || c>'') c = gc();

  int ret = ;

  while(c>='' && c<='') {

    ret =  * ret + c - ;

    c = gc();

  }

  return ret;

}

int read_string(char *p)

{

    int cnt = ;

    char c;

    while((c = gc()) == ' ');    //    skip spaces

    //

    while(c != )

    {

        p[cnt ++] = c;

        c = gc();

    }

    return cnt;

}

void print_fast(const char *p, int len)

{

    fwrite(p, , len, stdout);

}

/////////////////////////

bool isPalin(int n)

{

    if(n >=  && n < ) return true;

    //    Get digit length

    int nDigits =  + (int)floor(log10(n * 1.0));

    //    Get separated digits

    int digits[] = {};

    for(int i = ; i < nDigits; i ++)

    {

        int d = n / (int)pow(10.0, i*1.0) % ;

        digits[i] = d;

    }

    //    Check digits

    bool bEven = nDigits %  == ;

    int inxLow = nDigits /  - ;

    int inxHigh = (nDigits / ) + (bEven ?  : );

    int nDigits2Check = nDigits / ;

    for(int i = ; i < nDigits2Check; i ++)

    {

        if(digits[inxLow] != digits[inxHigh]) return false;

        inxLow --; inxHigh ++;

    }

    return true;

}

bool Palin[] = {false};

void precalc_palin()

{

    for(int i = ; i <= ; i ++)

    {

        if(isPalin(i))

        {

            Palin[i-] = true;

            //printf("%d ", i);

        }

    }

    //printf("\n");

}

void calc(int a, int b, int l)

{

    int rcnt = ; int mya = , myb = ;

    for(int i = a; i <= b; i++)

    {

        if(!Palin[i-]) continue;

        //printf("At %d\n", i);

        int cnt = ; int bound = min(b, i + l - );

        for(int j = i; j <= bound; j ++)

        {

            if(Palin[j-])    cnt ++;

        }

        //printf("[%d, %d] = %d\t", i, bound, cnt);

        if(cnt > rcnt)

        {

            rcnt = cnt; mya = i; myb = bound;

        }

    }

    // shrink

    if(rcnt > )

    {

        while(!Palin[myb-]) myb--;

        printf("%d %d\n", mya, myb);

    }

    else

    {

        printf("Barren Land.\n");

    }

}

int main()

{

    //    pre-calc all palindrome in [1-1000]

    precalc_palin();

    int runcnt = read_int();

    while(runcnt--)

    {

        int a = read_int();

        int b = read_int();

        int l = read_int();

        calc(a, b, l);

    }

    return ;

}

巴特西

SPOJ #692. Fruit Farm

最新文章

热门文章