USACO-T008: Palindromic Square

/*
ID: mickyta1
TASK: palsquare
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

string baseNumber(int x, int base){
    string ans = "";
    while(x > 0){
        int newDigit = x % base;
        if(newDigit >= 10){
            ans = (char)('A' + newDigit - 10) + ans;
        } else {
            ans = (char)('0' + newDigit) + ans;
        }
        x /= base;
    }
    return ans;
}

bool isPalindrome(string &str){
    int len = str.size();
    for(int i = 0; i < len / 2; ++i){
        if(str[i] != str[len - i - 1]){
            return false;
        }
    }
    return true;
}

int main(){

    freopen("palsquare.in", "r", stdin);
    freopen("palsquare.out", "w", stdout);

    int base;
    scanf("%d", &base);
    for(int i = 1; i <= 300; ++i){
        string i2baseB = baseNumber(i * i, base);
        if(isPalindrome(i2baseB)){
            cout << baseNumber(i, base) << ' ' << i2baseB << '\n';
        }
    }

    fclose(stdin);
    fclose(stdout);

    return 0;
}