Ten Googol
Time Limit: 500/200 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 545 Accepted Submission(s): 267
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
开始领会错题意了。。以为two googol 是 2^101 ..结果后面发现是 2*10^101.
#include#include #include #include #include using namespace std;int a[10][30]={{ -1},{ -1},{ -1},{ -1,1,2,6,10},{ -1,0,4,5,9},{ -1,3,7,8,40,50,60},{ -1,11,12,20,30,80,90},{ -1,15,16,70},{ -1,13,14,18,19,41,42,46,51,52,56,61,62,66},{ -1,17,21,22,26,31,32,36,44,45,49,54,55,59,64,65,69,81,82,86,91,92,96}};char str[5][200] ={ "0", "10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "60000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000", "100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"};int main(){ int tcase; scanf("%d",&tcase); int t = 1; while(tcase--){ int k,b; scanf("%d%d",&k,&b); printf("Case #%d: ",t++); if(k==3){ if(b>4) printf("-1\n"); else printf("%d\n",a[k][b]); } if(k==4){ if(b>4) printf("-1\n"); else printf("%d\n",a[k][b]); } if(k==5){ if(b>6) printf("-1\n"); else printf("%d\n",a[k][b]); } if(k==6){ if(b>6) printf("-1\n"); else printf("%d\n",a[k][b]); } if(k==7){ if(b>3) printf("-1\n"); else printf("%d\n",a[k][b]); } if(k==8){ if(b>13) printf("-1\n"); else printf("%d\n",a[k][b]); } if(k==9){ if(b>26) printf("-1\n"); else if(b>22) printf("%s\n",str[b-22]); else printf("%d\n",a[k][b]); } } return 0;}