首页 > 基础算法 > 模拟法 > hdu 1314 Numerically Speaking-模拟-[解题报告]
2013
12-09

hdu 1314 Numerically Speaking-模拟-[解题报告]

Numerically Speaking

问题描述 :

A developer of crossword puzzles (and other similar word games) has decided to develop a mapping between every possible word with from one to twenty characters and unique integers. The mapping is very simple, with the ordering being done first by the length of the word, and then alphabetically. Part of the list is shown below.
a 1
b 2

z 26
aa 27
ab 28

snowfall 157,118,051,752

Your job in this problem is to develop a program which can translate, bidirectionally, between the unique word numbers and the corresponding words.

输入:

Input to the program is a list of words and numbers, one per line starting in column one, followed by a line containing a single asterisk in column one. A number will consist only of decimal digits (0 through 9) followed immediately by the end of line (that is, there will be no commas in input numbers). A word will consist of between one and twenty lowercase alphabetic characters (a through z).

输出:

The output is to contain a single line for each word or number in the input data. This line is to contain the word starting in column one, followed by an appropriate number of blanks, and the corresponding word number starting in column 23. Word numbers that have more than three digits must be separated by commas at thousands, millions, and so forth.

样例输入:

29697684282993
transcendental
28011622636823854456520
computationally
zzzzzzzzzzzzzzzzzzzz
*

样例输出:

elementary            29,697,684,282,993
transcendental        51,346,529,199,396,181,750
prestidigitation      28,011,622,636,823,854,456,520
computationally       232,049,592,627,851,629,097
zzzzzzzzzzzzzzzzzzzz  20,725,274,851,017,785,518,433,805,270

http://poj.org/problem?id=1312

看清楚题目可以看到是一个进制转换的问题

没写出来

看了别人的代码

//============================================================================
// Name        : hello.cpp
// Author      : key
// Version     : 8
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================



#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#include <map>
using namespace std;

#define NUM_INF 0x7FFFFFFF

int Judge(int n,char tmp[30])
{
	
	for(int i=n;i<30;i++)
		
		if(tmp[i])
			
			return 1;
		
		return 0;
		
}

void DecToBin(char a[30])
{
	int i,j,tmp=0,k=0,len=strlen(a);
	char res[30],b[30],cop[30];
	memset(res,0,sizeof(res));
	strcpy(cop,a);
	while(strcmp(cop,"0"))
	{
		i=tmp=j=0;
		while(i<len)
		{
			while(tmp<26&&i<len)
			{
				tmp=tmp*10+cop[i++]-'0';
				if(j&&tmp<26&&i<len)
					b[j++]='0';
			}
			b[j++]=tmp/26+'0';
			tmp=tmp%26;
		}
		res[k++]=tmp;
		memset(cop,0,sizeof(cop));
		for(i=0;i<j;i++)
			cop[i]=b[i];
		len=strlen(cop);
		memset(b,0,sizeof(b));
	}
	for(i=0;i<k;i++)
	   {
		if(!Judge(i,res))
		{
			k=i;
			break;
		}
		while(!res[i])
		{
			res[i]='z';
			res[i+1]--;
			i++;
		}
		if(res[i]==-1)
		{
			res[i]=25;
			res[i+1]--;
		}
		res[i]=res[i]+'a'-1;
	}
	for(i=k-1;i>=0;i--)
		printf("%c",res[i]);
	for(i=k+1;i<23;i++)
		printf(" ");
}

void BigNumMultiSmall(int a1[],int &n)
{
	int i;
	a1[0]=a1[0]*26;
	for(i=1;i<n;i++)
	{
		a1[i]*=26;
		a1[i]+=a1[i-1]/10;
		a1[i-1]=a1[i-1]%10;
	}
	while(a1[i-1]>9)
	{
		a1[i]=a1[i-1]/10;
		a1[i-1]=a1[i-1]%10;
		i++;
	}
	n=i;
}
void BinToDec(char a[30])
{
	int j,k,t,m=0,len=strlen(a),i=0;
	int res[30]={0},tmp[30]={0};
	for(i=0;i<len;i++)
		a[i]=a[i]-'a'+1;
	while(a[0])
	{
		res[m++]=a[0]%10;
		a[0]/=10;
	}
	for(i=1;i<len;i++)
	{
		BigNumMultiSmall(res,m);
		memset(tmp,0,sizeof(tmp));
		k=t=0;
		while(a[i])
		{
			tmp[k++]=a[i]%10;
			a[i]/=10;
		}
		for(j=0;j<m;j++)
		{
			t=t+res[j]+tmp[j];
			res[j]=t%10;
			t/=10;
		}
	}
	for(i=m-1;i>=0;i--)
	{
		printf("%d",res[i]);
		if((i+1)%3==1&&i)
			printf(",");
	}
}

int main()
{
	int i,t;
	char ch[30];
	while(scanf("%s",ch)!=EOF&&strcmp(ch,"*"))
	{
		if(ch[0]>='a'&&ch[0]<='z')
		{
			printf("%s",ch);
			for(i=strlen(ch)+1;i<23;i++)
				printf(" ");
			BinToDec(ch);
		}
		else
		{
			DecToBin(ch);
			t=strlen(ch);
			for(i=0;i<t;i++)
			{
				printf("%c",ch[i]);
				if((i+1)%3==t%3&&i<t-1)
					printf(",");
			}
		}
		printf("\n");
	}
	return 0;
}
// void printf_num(string str)
// {
// 	int i;
// 	for(i=0;str[i];i++)
// 	{
// 		if(i && ((str.length()-i)%3==0))
// 			cout<<",";
// 		cout<<str[i];
// 	}
// 	cout<<endl;
// }
// 
// void printf_str(string str)
// {
// 	int i;
// 	cout<<str;
// 	for(i=str.length();i<22;i++)
// 		cout<<" ";
// }
// 
// int main()
// {
// 	char str[1010];
// 	int n,m;
// 	while(scanf("%s",str)!=EOF)
// 	{
// 		if(str[0] == '*')
// 			break;
// 		if(str[0] >= 'a'&&str[0]<='z')
// 		{
// 			printf_str(str);
// 			printf_num(transformNumber(str,26,10));
// 		}
// 		else
// 		{
// 			printf_str(transformNumber(str,10,26));
// 			printf_num(str);
// 		}
// 	}
// 	return 0;
// };


// int compare(const string& str1, const string& str2);
// string Minus_int(string str1, string str2);
// string Add_int(string str1, string str2);
// string Multiply_int(string str1, string str2);
// string Divide_int(string str1, string str2,int flat);
// 
// string int_to_str(int n)
// {
// 	string str="";
// 	while(n)
// 	{
// 		str+=('0'+n%10);
// 		n/=10;
// 	}
// 	return str;
// }
// void abc_to_num(char* str)
// {
// 	int i;
// 	printf("%s",str);
// 	for(i=strlen(str);i<22;i++)
// 		printf(" ");
// 	string sum="0";
// 	int temp;
// 	i=0;
// 	while(str[i])
// 	{
// 		sum = Multiply_int(sum ,"26");
// 		temp = (str[i]-'a'+1);
// 		sum = Add_int(sum , int_to_str(temp));
// 		i++;
// 	}
// 	cout<<sum<<endl;
// }
// 
// char str_to_abc(string str)
// {
// 	int sum=0;
// 	int i=0;
// 	while(str[i])
// 	{
// 		sum*=10;
// 		sum+=str[i]-'0';
// 		i++;
// 	}
// 	return sum+'a'-1;
// }
// 
// void num_to_abc(string n)
// {
// 	int i;
// 	string n_temp = n;
// 	string str;
// 	string temp;
// 	while(n!="0")
// 	{
// 		temp = Divide_int(n,"26",0);
// 		temp[0]=str_to_abc(temp);
// 		temp[1]='\0';
// 		str = temp+str;
// 		n = Divide_int(n,"26",1);
// 	}
// 	cout<<str;
// 	for(i=str.length();i<22;i++)
// 		cout<<" ";
// 	cout<<n_temp<<endl;
// }
// 
// int main()
// {
// 	char str[1010];
// 	while(scanf("%s",str)!=EOF)
// 	{
// 		if(str[0] == '*')
// 			break;
// 		if(str[0]>='0'&&str[0]<='9')
// 			num_to_abc(str);
// 		else
// 			abc_to_num(str);
// 	}
// 	return 0;
// }
// 
// int compare(const string& str1, const string& str2)
// {
// 	if(str1.size() > str2.size())
// 	{
// 		return 1;
// 	}
// 	else if(str1.size() < str2.size())
// 	{
// 		return -1;
// 	}
// 	else
// 	{
// 		//return string
// 		return str1.compare(str2);
// 	}
// }
// 
// string Add_int(string str1, string str2)
// {
// 	int sign = 1;
// 	string str="";
// 	if(str1[0] == '-')
// 	{
// 		if(str2[0]=='-')
// 		{
// 			sign = -1;
// 			str = Add_int(str1.substr(1),str2.substr(1));
// 		}
// 		else
// 		{
// 			str = Minus_int(str2,str1.substr(1));
// 		}
// 	}
// 	else
// 	{
// 		if(str2[0] == '-')
// 		{
// 			str = Minus_int(str1, str2.substr(1));
// 		}
// 		else
// 		{
// 			string::size_type l1, l2;
// 			int i;
// 			l1 = str1.size();
// 			l2 = str2.size();
// 			if(l1 < l2)
// 			{
// 				for(i = 0; i < l2-l1; i++)
// 				{
// 					str1 = "0"+str1;
// 				}
// 			}
// 			else
// 			{
// 				for(i = 0; i < l1-l2; i++)
// 				{
// 					str2 = "0" + str2;
// 				}
// 			}
// 			int int1 = 0;
// 			int int2 = 0;//进位
// 			for(i = str1.size()-1;i>=0; i--)
// 			{
// 				int1 = (int(str1[i]-'0' + str2[i]-'0')+int2)%10;
// 				int2 = (int(str1[i]-'0'+str2[i]-'0')+int2)/10;
// 				str = char(int1+'0')+str;
// 			}
// 			if(int2 != 0)
// 			{
// 				str = char(int2+'0')+str;
// 			}
// 		}
// 	}
// 	if(sign == -1 && str[0] != '0') //处理符号位 
// 	{
// 		str = "-"+str;
// 	}
// 	return str;
// 	
// }
// string Minus_int(string str1, string str2)
// {
// 	int i;
// 	int sign = 1;
// 	string str="";
// 	if(str2[0] == '-')
// 	{
// 		if(str1[0] != '-')
// 		{
// 			str = Add_int(str1,str2.substr(1));
// 		}
// 		else
// 		{
// 			sign = -1;
// 			str = Minus_int(str2.substr(1),str1.substr(1));
// 		}
// 	}
// 	else
// 	{
// 		if(str1[0] == '-')
// 		{
// 			sign = -1;
// 			str = Add_int(str1.substr(1),str2.substr(1));
// 		}
// 		else
// 		{
// 			int ret = compare(str1,str2);
// 			if(ret == 0)
// 				return 0;
// 			else if(ret < 0)
// 			{
// 				string temp = str1;
// 				str1= str2;
// 				str2=temp;
// 				sign = -1;
// 			}
// 			string::size_type tempint;
// 			tempint = str1.size() - str2.size();
// 			for( i = str2.size()-1; i >= 0; i--)
// 			{
// 				if(str1[tempint+i] < str2[i])
// 				{
// 					str1[i+tempint-1] = char(int(str1[i+tempint-1]-'0'-1)+'0');
// 					str = char(str1[i+tempint]-str2[i]+58) + str;
// 				}
// 				else
// 				{
// 					str = char(str1[i+tempint]-str2[i]+48) + str;
// 				}
// 			}
// 			for( i = tempint-1; i >=0; i--)
// 			{
// 				str = str1[i]+str;
// 			}
// 		}
// 	}
// 	
// 	str.erase(0,str.find_first_not_of('0'));
// 	if(str.empty())
// 		str = '0';
// 	else if(sign == -1)
// 	{
// 		str = '-'+str;
// 	}
// 	
// 	return str;
// 	
// }
// string Multiply_int(string str1, string str2)
// {
// 	int sign = 1;
// 	string str="0";
// 	if(str1[0] == '-')
// 	{
// 		sign *= -1;
// 		str1 = str1.substr(1);
// 	}
// 	if(str2[0]=='-')
// 	{
// 		sign *= -1;
// 		str2 = str2.substr(1);
// 	}
// 	int i,j;
// 	string::size_type l1,l2;
// 	l1 = str1.size();
// 	l2 = str2.size();
// 	for( i = l2 -1; i >=0; i--)
// 	{
// 		string tempstr = ""; //用来表示乘法中的那个错位的
// 		int int1 = 0; //乘法结果
// 		int int2 = 0;//进位
// 		int int3 = int(str2[i]-'0');
// 		if(int3!= 0)
// 		{
// 			for(j = 0; j< (int)(l2-i-1); j++)
// 			{
// 				tempstr = "0"+ tempstr;
// 			}
// 			for(j = l1-1; j >=0; j--)
// 			{
// 				int1 = (((int)(str1[j]-'0'))*int3+int2)%10;
// 				int2 = (((int)(str1[j]-'0'))*int3+int2)/10;
// 				tempstr = char(int1+'0') + tempstr;
// 			}
// 			if(int2 != 0)
// 			{
// 				tempstr = char(int2+'0')+tempstr;
// 			}
// 		}
// 		str=Add_int(str,tempstr);
// 	}
// 	if(str[0] =='0')
// 		str = "0";
// 	else if(sign == -1)
// 	{
// 		str = "-"+str;
// 	}
// 	return str;
// 	
// }
// string Divide_int(string str1, string str2,int flat)
// {
// 	string quotient,residue;
// 	quotient="";
// 	residue="";
// 	int sign1 = 1;
// 	int sign2 = 1;
// 	if(str2 == "0")
// 	{
// 		cout << "除数为0" <<endl;
// 		return "";
// 	}
// 	if(str1 == "0")
// 	{quotient = "0"; residue = "0";}
// 	if(str1[0] == '-')
// 	{
// 		str1 = str1.substr(1);
// 		sign1 *= -1;
// 		sign2 = -1;
// 	}
// 	if(str2[0]=='-')
// 	{
// 		str2 = str2.substr(1);
// 		sign1 *= -1;
// 	}
// 	int res = compare(str1, str2);
// 	if(res < 0)
// 	{
// 		quotient = "0";
// 		residue = str1;
// 	}
// 	else if(res == 0)
// 	{
// 		quotient = "1";
// 		residue = "0";
// 	}
// 	else
// 	{
// 		string::size_type l1, l2;
// 		l1 = str1.size();
// 		l2 = str2.size();
// 		string tempstr="";
// 		tempstr.append(str1,0,l2-1);
// 		for(int i = l2-1; i < l1; i++)
// 		{
// 			tempstr = tempstr+str1[i];
// 			for(char ch = '9'; ch >='0';ch--) //试商,这个还蛮关键的
// 			{
// 				string str="";
// 				str = str + ch;
// 				if(compare(Multiply_int(str2,str), tempstr) <=0)
// 				{
// 					quotient = quotient + ch;
// 					tempstr = Minus_int(tempstr,Multiply_int(str2, str));
// 					break;
// 				}
// 			}
// 		}
// 		residue = tempstr;
// 	}
// 	quotient.erase(0, quotient.find_first_not_of('0'));
// 	if(quotient.empty())
// 		quotient = "0";
// 	else if(sign1 == -1)
// 	{
// 		quotient ="-"+quotient;
// 	}
// 	if(sign2 == -1 && residue[0] != '0')
// 	{
// 		residue = '-' + residue;
// 	}
// 	if(flat==1)		 //shang
// 	return quotient;
// 	else			 //yushu
// 	return residue;
// }

解题转自:http://blog.csdn.net/jw72jw/article/details/6666756


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.