Problem 4

斜めに総当たり戦する感じです．

#include <iostream>
#include <cmath>
using namespace std;

#define MAX 999

bool
isPalindrome(int n)
{
    bool f = false;

    if (100000 <= n && n <= 999999)
    {
        char l[4], r[4];
        
        // 下3桁を反転
        for (int i = 0; i < 3; i++)
        {
            r[i] = '0' + n%10;
            n   /= 10;
        }

        // 上3桁をそのまま
        for (int i = 2; i >= 0; i--)
        {
            l[i] = '0' + n%10;
            n   /= 10;
        }
        l[3] = r[3] = '\0';

        if (strcmp(l, r) == 0)
        {
            f = true;
        }
    }

    return f;
}

int
trace(int _l, int _r)
{
    int r = -1;

    for (int i = 0; _l+i <= MAX || _r+i <= MAX; i++) // 右上に上っていく
    {
        int x = _l-i;
        int y = _r+i;
        if (x > MAX || y > MAX || x*y <= 0)
        {
            break;
        }

        if (isPalindrome(x*y))
        {
            r = x*y;
            break;
        }
    }

    return r;
}

int
main(int argc, char **argv)
{
    int ans = -1;

    for (int n = MAX; n >= 0; n--)
    {
        if ((ans = trace(n, n)) != -1)
        {
            break;
        }

        if ((ans = trace(n-1, n)) != -1)
        {
            break;
        }

        if(n == 953)
            break;
    }
    
    cout << ans << endl;

    return 0;
}