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 ;
}