/* This is a programme for working out a palindrome of n-th order.
20180713
by hank_finch*/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int pwr (int order, int n)
{
int i, mult;
for (i = 0, mult = 1; i < n; i++)
{
mult *= order;
}
return mult;
}

int trsnum (char *s, int length, int n)
{
int i, d, num = 0;
for (i = 0; i < length; i++)
{
if (s[i] - '0' >= 0 && s[i] - '0' < 10) //Limit the location of the string
{
num += (s[i] - '0') * pwr (n, length - 1 - i);
}else{
switch (s[i])
{
case 'A': d = 10; break;
case 'B': d = 11; break;
case 'C': d = 12; break;
case 'D': d = 13; break;
case 'E': d = 14; break;
case 'F': d = 15; break;
default: break;
}
num += d * pwr (n, length - 1 - i);
}
}
return num;
}

char* trsstring (int num, int n)
{
int i, k, temp;
char string;
if (n <= 10)
{
for (k = 0, temp = num; temp / n != 0; k++)
{
temp /= n;
}
string = (char)malloc ((k + 2)*sizeof (char));
for (i = 0; num != 0; i++)
{
string[k - i] = '0' + num % n;
num /= n;
}
}
if (n > 10)
{
for (k = 0, temp = num; temp / n != 0; k++)
{
temp /= n;
}
string = (char*)malloc ((k + 1) * sizeof(char));
for (i = 0; num != 0; i++)
{
if (num % n > 9)
{
switch (num % n)
{
case 10: string[k - i] = 'A';
num /= n;
break;
case 11: string[k - i] = 'B';
num /= n;
break;
case 12: string[k - i] = 'C';
num /= n;
break;
case 13: string[k - i] = 'D';
num /= n;
break;
case 14: string[k - i] = 'E';
num /= n;
break;
case 15: string[k - i] = 'F';
num /= n;
break;
default: break;
}
}else
{
string [k - i] = '0' + num % n;
num /= n;
}
}
}
return string;
}

char* reverse (char *s)
{
char p;
p = (char) malloc (1000*sizeof(char));
int i, length;
length = strlen(s);
for (i = 0; i < length; i++)
{
p[i] = s[length - 1 - i];
}
p[length] = '\0';
return p;
}//Here the returned p is the pointer of the address of the reversed string

int main()
{//Input an n-th order string.
int a, b, sum, i, n;
char str[1000];
char *s = str;
char *p;
scanf ("%d", &n);
scanf ("%s", str);
s[strlen(str)] = '\0';
p = reverse (s);
if (trsnum (s, strlen(s),n) == trsnum (p, strlen (p), n))
{
printf ("STEP=1");
return 0;
}
for (i = 0; trsnum (s, strlen(s),n) != trsnum (p, strlen (p), n); i++)
{
a = trsnum (s, strlen(s), n);
b = trsnum (p, strlen(p), n);
sum = a + b;
s = trsstring (sum, n);
p = reverse (s);
if (i >= 30)
{
printf ("Impossible!");
return 0;
}
}
printf ("STEP=%d", i);
return 0;
}
代码如上，第三组没有通过