Vijos P1304回文数

╰+攻爆jí腚メ 2022-08-21 00:13 150阅读 0赞

**P1304**回文数

[Accepted][]

标签： [NOIP提高组1999][NOIP_1999] \[显示标签\]

## 描述 ##

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。

例如：给定一个10进制数56，将56加56（即把56从右向左读），得到121是一个回文数。

又如：对于10进制数87：  
STEP1：87+78 = 165 STEP2：165+561 = 726  
STEP3：726+627 = 1353 STEP4：1353+3531 = 4884  
在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。

写一个程序，给定一个N（2<=N<=10或N=16）进制数M，其中16进制数字为0-9与A-F，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible!”

## 格式 ##

### 输入格式 ###

共两行  
第一行为进制数N（2<=N<=10或N=16）  
第二行为N进制数M（0<=M<=maxlongint）

### 输出格式 ###

共一行  
第一行为“STEP=”加上经过的步数或“Impossible!”

## 样例1 ##

### 样例输入1\[复制\] ###

>     9
>     87

### 样例输出1\[复制\] ###

>     STEP=6

## 限制 ##

各个测试点1s

## 来源 ##

NOIP1999提高组第2题

#include<stdio.h>
    #include<string.h>
    #define MAX 100
    
    int cvt_num(char*n) {
    	int l=strlen(n),i;
    	char t[MAX];
    	for(i=0;i<l;i++) t[l-i-1]=n[i]>'9'?n[i]-'A'+10:n[i]-'0';
    	memcpy(n,t,l);
    	return l;
    }
    
    int ok(const char*n,int l) {
    	int i;
    	for(i=0;i<l/2;i++) if(n[i]!=n[l-i-1]) return 0;
    	return 1;
    }
    
    void work(char*n,int*l,int k) {
    	int i,r;
    	char t[MAX];
    	for(i=0;i<*l;i++) 
    	t[*l-i-1]=n[i];
    	for(i=r=0;i<*l;i++) 
    	{
    		n[i]+=t[i]+r,r=0;
    		if(n[i]>=k) 
    		n[i]-=k,r++;
    	} 
    	if(r) 
    	n[i]=r,(*l)++;
    }
    
    int main() {
    	char m[MAX];
    	int n,l,i,f;
    	scanf("%d%s",&n,m);
    	l=cvt_num(m);
    	for(i=0;!(f=ok(m,l))&&i<30;work(m,&l,n),i++);
    	if(f) printf("STEP=%d",i);
    	else printf("Impossible!");
    	return 0;
    }

[Accepted]: https://vijos.org/records/56dc1c5b17f3ca7e19f6a0a9
[NOIP_1999]: https://vijos.org/p/NOIP+%E6%8F%90%E9%AB%98%E7%BB%84+1999