首页 > ACM题库 > HDU-杭电 > HDU 4541-Ten Googol[解题报告]HOJ
2015
07-25

HDU 4541-Ten Googol[解题报告]HOJ

Ten Googol

问题描述 :

  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

输入:

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

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

输出:

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

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

样例输入:

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

样例输出:

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

题解:根据字符个数制表如下:

3:1, 2 ,6 ,10
4:0, 4,  5 , 9
5:3, 7, 8, 40 ,50 ,60
6:11,12, 20, 30, 80 ,90
7:15 ,16 ,70
8:13, 14 ,18, 19 ,41 ,42 ,46 ,51 ,52 ,56 ,61 ,62 ,66
9:17 ,21 ,22 ,26 ,31 ,32 ,36 ,44 ,45 ,49 ,54 ,55 ,59 ,64 ,65 ,69 ,81 ,82 ,86 ,91 ,92 ,96

 

googol 级别特殊处理。OK!

 

代码:

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <string>
using namespace std;

#define MAXV 100010
#define MAX 25

int mp[MAX][MAX] ={
    {4, 1, 2, 6, 10},
    {4, 0, 4, 5, 9},
    {6, 3, 7, 8, 40, 50, 60},
    {6, 11, 12, 20, 30, 80, 90},
    {3, 15, 16, 70},
    {13,13, 14 ,18, 19 ,41 ,42 ,46 ,51 ,52 ,56 ,61 ,62 ,66},
    {26,17 ,21 ,22 ,26 ,31 ,32 ,36 ,44 ,45 ,49 ,54 ,55 ,59 ,64 ,65 ,69 ,81 ,82 ,86 ,91 ,92 ,96, 101}
};

int main(){
    int T,n,m;
    scanf("%d",&T);
    for(int i = 1; i <= T; i++){
        scanf("%d%d",&n,&m);
        printf("Case #%d: ",i);
        if(m > mp[n-3][0]){
            printf("-1\n");continue;
        }
        if(n == 9 && m > 22){
            if(m == 23){
                printf("10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n");
            }
            else if(m == 24){
                printf("20000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n");
            }
            else if(m== 25){
                printf("60000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n");
            }
            else if(m==26){
                printf("100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000\n");
            }
        }
        else {
            printf("%d\n",mp[n-3][m]);
        }
    }
    return 0;
}

 

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

参考:http://blog.csdn.net/ljd4305/article/details/12342937