首页 > 搜索 > BFS搜索 > HDU 3781-Aronson-模拟-[解题报告]HOJ
2015
04-11

HDU 3781-Aronson-模拟-[解题报告]HOJ

Aronson

问题描述 :

Aronson’s sequence ak is a sequence of integers defined by the sentence "t is the first, fourth, eleventh, … letter of this sentence.", where the … are filled in appropriately so that the sentence makes sense. The first few values are 1, 4, 11, 16, 24, 29, 33, 35, 39, …. Note the non-letter characters and spaces are not considered in the formulation of the sequence. When k <= 100000, it turns out that ak <= 1000000.

To formulate the sequence, you must be able to write the ordinal numbers in English. The ordinal numbers are first, second, third, …, while the cardinal numbers are one, two, three, …. It is easiest to define the ordinals in terms of the cardinals, so we describe these first.

A cardinal number less than twenty is written directly from the first two columns of table 1 (3->three, 17->seventeen, etc.). A cardinal number greater than or equal to twenty, but less than one hundred is written as the tens part, along with a nonzero ones part (40-> forty, 56->fifty six, etc). A cardinal number greater than or equal to one hundred, but less than one thousand, is written as the hundreds part, along with a nonzero remainder (100->one hundred, 117->one hundred seventeen, 640->six hundred forty, 999->nine hundred ninety nine). A cardinal number greater than or equal to one thousand, but less than one million, is written as the thousands part, along with a nonzero remainder (12345->twelve thousand three hundred forty five). An ordinal number is written as a cardinal number, but with the last word ordinalized using the columns three and four of table 1.

Some example ordinal numbers are 3rd->third, 56th->fifty sixth, 100th->one hundredth, and 12345th->twelve thousand three hundred forty fifth.

输入:

The input consists of a number of cases. Each case is specified by a positive integer k on one line (1 <= k <= 100000). The sequence of k values will be non-decreasing. The input is terminated by a line containing a single 0.

输出:

The input consists of a number of cases. Each case is specified by a positive integer k on one line (1 <= k <= 100000). The sequence of k values will be non-decreasing. The input is terminated by a line containing a single 0.

样例输入:

1
3
9
0

样例输出:

1
11
39
Hint
Table 1 n cardinal nth ordinal 1 one 1st first 2 two 2nd second 3 three 3rd third 4 four 4th fourth 5 five 5th fifth 6 six 6th sixth 7 seven 7th seventh 8 eight 8th eighth 9 nine 9th ninth 10 ten 10th tenth 11 eleven 11th eleventh 12 twelve 12th twelfth 13 thirteen 13th thirteenth 14 fourteen 14th fourteenth 15 fifteen 15th fifteenth 16 sixteen 16th sixteenth 17 seventeen 17th seventeenth 18 eighteen 18th eighteenth 19 nineteen 19th nineteenth 20 twenty 20th twentieth 30 thirty 30th thirtieth 40 forty 40th fortieth 50 fifty 50th fiftieth 60 sixty 60th sixtieth 70 seventy 70th seventieth 80 eighty 80th eightieth 90 ninety 90th ninetieth 100 hundred 100th hundredth 1000 thousand 1000th thousandth

//用了大神的阿拉伯数字转英文,很强大;后面就直接一个bfs模拟就ok了;

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

using namespace std;



string num[1001] = {"", "first", "second", "third", "fourth", "fifth", "sixth", "seventh",
		"eighth", "ninth", "tenth", "eleventh", "twelfth", "thirteenth", "fourteenth",
		"fifteenth", "sixteenth", "seventeenth", "eighteenth", "nineteenth", "twentieth"
};

string t[1001] = {"", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten",
		"eleven", "twelve", "thirteen", "fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen",
		"twenty"
};
string retNum(int val) {
	string res;
	if(val >= 100) {
		res += t[val / 100] + t[100];
		val %= 100;
	}
	if(val >= 20) {
		res += t[val / 10 * 10];
		if(val % 10 != 0) res += t[val % 10];
		return res;
	}
	return res + t[val];
}

string getNum(int val) {
	string res;
	if(val >= 1000) {
		res += retNum(val / 1000);
		if(val % 1000 == 0) return res + num[1000];
		res += t[1000];
		val %= 1000;
	}
	if(val >= 100) {
		res += retNum(val / 100);
		if(val % 100 == 0) return res + num[100];
		res += t[100];
		val %= 100;
	}
	if(val >= 20) {
		if(val % 10 == 0) return res += num[val];
		res += retNum(val / 10 * 10);
		return res + num[val % 10];
	}
	else {
		return res + num[val];
	}
}
void init()
{
	num[30] = "thirtieth";t[30] = "thirty";
	num[40] = "fortieth";t[40] = "forty";
	num[50] = "fiftieth";t[50] = "fifty";
	num[60] = "sixtieth";t[60] = "sixty";
	num[70] = "seventieth";t[70] = "seventy";
	num[80] = "eightieth";t[80] = "eighty";
	num[90] = "ninetieth";t[90] = "ninety";
	num[100] = "hundredth";t[100] = "hundred";
	num[1000] = "thousandth";t[1000] = "thousand";
}

int judge(string s)
{
	int i,m=0,len=s.length();
	for(i=0;i<len;i++)
		if(s[i]=='t')
			m++;
	return m;
}
int numm[110000];
void bfs()
{
	int sum=5,m=11,cnt=3;
	numm[1]=1;
	numm[2]=4;
	numm[3]=11;
	queue <string> que;
	que.push(getNum(4));
	que.push(getNum(11));
	while(!que.empty())
	{
		int i,len;
		string str=que.front();
		que.pop();
		len=str.length();
		for(i=0;i<len;i++)
		{
			if(str[i]=='t')
			{
				numm[++cnt]=m+i+1;
				string tem=getNum(m+i+1);
				sum+=judge(tem);
				if(sum<=100100)
				{
					que.push(tem);
				}
			}
		}
		m+=str.length();
	}
}
int main (void)
{
	int n;
	init();
	bfs();
	while (scanf("%d",&n),n)
		printf("%d\n",numm[n]);
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/zkfzkfzkfzkfzkfzkfzk/article/details/8036915