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
2013騰訊編程馬拉松復賽第三場（3月31日）
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;
}
