记录编号	171529	评测结果	AAAA
题目名称	[NOIP 1999]回文数	最终得分	100
用户昵称	noier	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2015-07-19 19:48:05	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<deque>
#include<fstream>
#include<map>
using namespace std;
bool add();
void init();
bool check();
void output();
void fz();
deque<int> num1, num2;
int n;
map<char, int> sheet;
FILE *in = fopen("huiwen.in", "r");
FILE *out = fopen("huiwen.out", "w");
int main()
{
	fscanf(in,"%d",&n);
	init();
	bool flag = false;
	for (int i = 0; i <= 30; i++)
	{
		flag = add();
		if (flag)
		{
			fprintf(out, "%d", i);
			break;
		}
	}
	if (!flag)
		fprintf(out, "impossible", 0);
	return 0;
}
void init()
{
	sheet.insert(pair<char, int>('0', 0));
	sheet.insert(pair<char, int>('1', 1 ));
	sheet.insert(pair<char, int>('2', 2));
	sheet.insert(pair<char, int>('3', 3));
	sheet.insert(pair<char, int>('4', 4));
	sheet.insert(pair<char, int>('5', 5));
	sheet.insert(pair<char, int>('6', 6));
	sheet.insert(pair<char, int>('7', 7));
	sheet.insert(pair<char, int>('8', 8));
	sheet.insert(pair<char, int>('9', 9));
	sheet.insert(pair<char, int>('a', 10));
	sheet.insert(pair<char, int>('b', 11));
	sheet.insert(pair<char, int>('c', 12));
	sheet.insert(pair<char, int>('d', 13));
	sheet.insert(pair<char, int>('e', 14));
	sheet.insert(pair<char, int>('f', 15));
	char temp;
	while (fscanf(in,"%1s",&temp )!=EOF)
	{
        num1.push_back(sheet.at(temp));
		num2.push_front(sheet.at(temp));
	}
}
bool add()
{
	bool ans=check();
	if (ans)
	{
		output();
		return true;
	}
	num2.clear();
	fz();
	for (int i = num1.size() - 1; i >= 0; i--)
		num1.at(i) += num2.at(i);
	for (int i = num1.size() - 1; i >= 0; i--)
	{
		if (num1.at(i) >= n&&i!=0)
		{
			num1.at(i) = num1.at(i) - n;
			num1.at(i-1) +=1;
		}
		else if (num1.at(i) >= n&&i == 0)
		{
			num1.at(i) = num1.at(i) - n;
			num1.push_front(1);
		}
	}
	return false;
}
bool check()
{
	for (unsigned int i = 0, j = num1.size() - 1; i <= j; i++, j--)
		if (num1.at(i) != num1.at(j))
			return false;
	return true;
}
void output()
{
	for (int i = 0; i < num1.size(); i++)
	{
		if (num1.at(i) < 10)
			fprintf(out, "%d", num1.at(i));
		else
			fprintf(out, "%c", 'a' + num1.at(i) - 10);
	}
	
	fprintf(out, "\n", 0);
}
void fz()
{
	deque<int>::iterator it;
	it = num1.begin();
	while (it != num1.end())
	{
		num2.push_front(*it);
		it++;
	}
}