【USACO-Chapter 1-1.2】【進数変換】Palindromic Squares

1924 ワード

【タイトル説明】
回文数とは、左から右へ読むのと右から左へ読むのと同じ数です.例えば12321は典型的な回文数である.
1進数B(2<=B<=20、10進数で表す)が与えられ、1以上300(10進数以下)以下であり、その二乗がB進数で表される場合、回文数の数である.「A」、「B」…で10、11などを表す.
【入力形式】(palsquare.in)
1行、1つの個別の整数B(Bは10進数で表される).
【出力形式】(palsquare.out)
各行に2つのB進数の要求に合致する数字で、2番目の数は1番目の数の平方で、2番目の数は回文数です.
【入力サンプル】
 
 
10

【出力サンプル】
1 1
2 4
3 9
11 121
22 484
26 676
101 10201
111 12321

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 30;
int b;
int cou;
int num[maxn];
char map[20] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J'};
int ans[20];
void init()
{
	freopen("palsquare.in","r",stdin);
	freopen("palsquare.out","w",stdout);
}

void readdata()
{
	scanf("%d",&b);
}

bool check()
{
	bool flag = true;
	if(cou == 1)return flag;
    for(int i = 0;i <= cou/2;i++)
	{
        if(map[num[i]] != map[num[cou-i-1]])
		{
			flag = false;
			break;
		}
	}
	return flag;
}

void change(int* num, int& cou, int x)
{
	memset(num,0,sizeof(num));
	cou = 0;
    while(x != 0)
	{
        num[cou] = x % b;
		x /= b;
		++cou;
	}
}

void writeans(int x)
{
	int cou1 = 0;
	change(ans, cou1, x);
	for(int i = cou1 - 1;i >= 0;i--)
	{
		printf("%c",map[ans[i]]);
	}
	printf(" ");
	for(int i = 0;i < cou;i++)
	{
	      printf("%c",map[num[i]]);
	}
	printf("
"); } void solve() { for(int i = 1;i <= 300;i++) { change(num, cou, i*i); if(check()) { writeans(i); } } } int main() { init(); readdata(); solve(); return 0; }