首页 > ACM题库 > HDU-杭电 > hdu 4541-ten googol-面试题-[解题报告]hoj
2015
02-17

hdu 4541-ten googol-面试题-[解题报告]hoj

Ten Googol

Time Limit: 500/200 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 326    Accepted Submission(s): 180

Problem Description
  Google的面试题向来以古怪闻名,延续自技术公司用逻辑题测试求职者的古老传统.现在我们来看看下面这题:

  面试官在房间的白板上写下6个数字:
    10,9,60,90,70,66
  现在的问题是,接下来该出现什么数字?

  想不出来了吧?不要再从数学的角度想了,把这些数字用正常的英文拼写出来:
    ten(10)
    nine(9)
    sixty(60)
    ninety(90)
    seventy(70)
    sixty-six(66)
  我们可以惊奇的发现这些数字都是按字母的多少排序的!再仔细一看:ten(10)不是唯一一个可以用3个字母拼出的数字,还有one(1),two(2),six(6);nine(9)也不是唯一一个用4个字母拼出的数字,还有zero(0),four(4)和five(5).而题目中的数字,每一个都是用给定长度的字母拼写出来的数字里最大的一个!

  现在我们回到原题:接下去该是哪个数字呢?
  我们注意到,66对应的字母长度为8(特别提醒:连接符不算在内),不管之后跟着哪个数,它都应该有9个字母,而且应该是9个字母拼出的数字里最大的。仔细找一下,你可能就会得出ninety-six(96)。不可能是100以上的数字,因为它会以one hundred开头,这已经有10个字母了。

  对于Google面试官来说,96只不过是可以接受的答案之一,另一个更好的回答是:
  100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
  也就是10的101次方,即:ten googol(有关Googol的资料可以在wiki中了解)。据说当年Google这个名字的创建也是由googol演化过来的(江湖传说肖恩拼写时老爱出错,本来想注册googol或者googolplex,结果由于手误就注册了google)。

  好了,当你解出了这道难题,面试官的下一道题目接踵而至——给你两个正整数N和M,要求你输出由N个字母组成的第M大数(我们只考虑0~99和googol级别的数字)。

注意:这里所说的“第M大数”是指从小到大的第M大,具体参见Sample

 

Input
输入数据第一行有一个数字T,代表有T组数据。
每组数字由两个正整数N和M组成。

[Technical Specification]
1<=T<=100
3<=N<=9
1<=M<=100

 

Output
首先输出case数(见sample),接着输出由N个字母组成的第M大数,如果没有,则输出-1。
 

Sample Input
6 3 1 3 2 4 1 4 2 5 1 9 100
 

Sample Output
Case #1: 1 Case #2: 2 Case #3: 0 Case #4: 4 Case #5: 3 Case #6: -1
 

Source
 

Recommend
liuyiding
 
注意  googol是指1*10的100次方  其长度为6只能和长度为3的单词搭配
注意 40  forty  只有5位    没有u
注意英语单词中的数字的表示 不要搞错了
 
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[10][111],ct[10];
const int mmax=99999999;
struct haha
{
    int cnt;//位数
    int num;//数值
    int flag;//标记是小于10 还是大与10
}b[20000];
int main()
{
    int i,j,k=0,cas,c=0;
    scanf("%d",&cas);
    for(i=0;i<10;i++)  ct[i]=0;
    for(i=0;i<=9;i++)
    {
        b[c].num=i;b[c].flag=1;
        c++;
    }
	b[c].num=10;b[c].flag=2;
	c++;
    b[1].cnt=b[2].cnt=b[6].cnt=b[10].cnt=3;
    b[0].cnt=b[4].cnt=b[5].cnt=b[9].cnt=4;
    b[3].cnt=b[7].cnt=b[8].cnt=5;
    for(i=2;i<=9;i++)
    {
        b[c].num=i*10;b[c].flag=3;
        c++;
    }
    b[11].cnt=b[12].cnt=6;b[13].cnt=5;b[14].cnt=5;
    b[15].cnt=5;b[16].cnt=7;b[17].cnt=6;b[18].cnt=6; 
	//printf("c=%d",c);
    for(i=11;i<=19;i++)
    {
        b[c].num=i;
        b[c].flag=2;
        c++;
    }
    
    b[19].cnt=b[20].cnt=6;
    b[21].cnt=b[22].cnt=8;
    b[23].cnt=b[24].cnt=7;
    b[25].cnt=9;
    b[26].cnt=b[27].cnt=8;
    for(i=0;i<c;i++)
    {
        int cnt=b[i].cnt;
        int num=b[i].num;
        a[cnt][ct[cnt]++]=num;
    }
    for(i=0;i<c;i++)
        for(j=0;j<c;j++)
        {
            if(b[i].flag==3&&b[j].flag==1)
            {
                int num;
				if(b[j].num==0) continue;
                int cnt=b[i].cnt+b[j].cnt;
                if(cnt>9) continue;
                  num=b[i].num+b[j].num;
                a[cnt][ct[cnt]++]=num;
            }
        }
    for(i=3;i<=9;i++)
    {
        sort(a[i],a[i]+ct[i]);
    }
/*	for(i=3;i<=9;i++)
	{
		for(j=0;j<ct[i];j++)
		{
			printf("%d ",a[i][j]);
		}
		printf("\n");
	}
*/
    while(cas--)
    {
        int n,m;
        k++;
        scanf("%d %d",&n,&m);
        printf("Case #%d: ",k);
        if(n==9&&m==ct[n]+1) {printf("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n");continue;}
   else if(n==9&&m==ct[n]+2) {printf("20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n");continue;}
   else if(n==9&&m==ct[n]+3) {printf("60000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n");continue;}
   else if(n==9&&m==ct[n]+4) {printf("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n");continue;}	
   if(ct[n]<m) {printf("-1\n");continue;}
        printf("%d\n",a[n][m-1]);

    }
    return 0;
}


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