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

2013腾讯编程马拉松复赛第三场（3月31日）

开始领会错题意了。。以为two googol 是 2^101 ..结果后面发现是 2*10^101.

#include<stdio.h>

#include<string.h>

#include <iostream>

#include <algorithm>

#include <stdlib.h>

using namespace std;

int a[][]={

{-},

{-},

{-},

{-,,,,},

{-,,,,},

{-,,,,,,},

{-,,,,,,},

{-,,,},

{-,,,,,,,,,,,,,},

{-,,,,,,,,,,,,,,,,,,,,,,}

};

char str[][] ={"",

    "",

    "",

    "",

    ""

};

int main()

{

    int tcase;

    scanf("%d",&tcase);

    int t = ;

    while(tcase--){

        int k,b;

        scanf("%d%d",&k,&b);

        printf("Case #%d: ",t++);

        if(k==){

            if(b>) printf("-1\n");

            else printf("%d\n",a[k][b]);

        }

        if(k==){

            if(b>) printf("-1\n");

            else printf("%d\n",a[k][b]);

        }

        if(k==){

            if(b>) printf("-1\n");

            else printf("%d\n",a[k][b]);

        }

        if(k==){

            if(b>) printf("-1\n");

            else printf("%d\n",a[k][b]);

        }

        if(k==){

            if(b>) printf("-1\n");

            else printf("%d\n",a[k][b]);

        }

        if(k==){

            if(b>) printf("-1\n");

            else printf("%d\n",a[k][b]);

        }

        if(k==){

            if(b>) printf("-1\n");

            else if(b>) printf("%s\n",str[b-]);

            else printf("%d\n",a[k][b]);

        }

    }

    return ;

}

巴特西

hdu 4541(麻烦的模拟)

Ten Googol

最新文章

热门文章