题解 | [NOIP1999]回文数

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

void transform (char ch[], int a[], int len)
{
    int i = 0;
    int j = len-1;

    for (j=j; j>=0; --j)
    {
        if (ch[j] >= '0' && ch[j] <= '9')
        {
            a[i] = ch[j] - '0';
        }
        else
        {
            a[i] = ch[j] - 'A' + 10;
        }
        ++i;
    }
}

int is_palindromic(int a[], int len)
{
    int i = 0;
    int j = len - 1;

    while (i < j)
    {
        if (a[i] != a[j])
        {
            return 0;
        }  
        ++i;
        --j; 
    }

    return 1;
}

void get_palindromic(int a[], int b[], int len)
{
    int i = 0;
    int j = 0;

    for (i=len-1, j=0; i>=0; --i, ++j)
    {
        b[j] = a[i];
    }
}


void add(int a[], int b[], int *len, int scale) //scale进制的加法
{
    int i = 0;
    int div = 0;

    while (i < *len)
    {
        div = (a[i] + b[i]) / scale;
        a[i] = (a[i] + b[i]) % scale;
        ++i;
        a[i] = a[i] + div;

        if (a[*len] > 0)
        {
            (*len)++;
        }    
    }
}


int get_step(char ch[], int scale)
{
    int count = 0;
    int len = strlen(ch);
    int a[30] = {0};
    int b[30] = {0};
    transform(ch, a, len);

    while (!is_palindromic(a, len))
    {
        get_palindromic(a, b, len);
        add(a, b, &len, scale);
        ++count;

        if(count > 30)
        {
            return count;
        }
    }

    return count;
}



int main() {
    char ch[8];
    int scale = 0;
    int step = 0;
    scanf("%d", &scale);
    scanf("%s",ch);
    step = get_step(ch, scale);

    if (step > 30)
    {
        printf("Impossible!");
    }
    else
    {
        printf("STEP=%d", step);
    }
    
    return 0;
}