2014
02-09

# Digits

A googol written out in decimal has 101 digits. A googolplex has one plus a googol digits. That’s a lot of digits!

Given any number x0, define a sequence using the following recurrence:

xi+1 = the number of digits in the decimal representation of xi

Your task is to determine the smallest positive i such that xi = xi-1.

Input consists of several lines. Each line contains a value of x0. Every value of x0 is non-negative and has no more than one million digits. The last line of input contains the word END.

Input consists of several lines. Each line contains a value of x0. Every value of x0 is non-negative and has no more than one million digits. The last line of input contains the word END.

42
END

3

#include<iostream>
#include<stdio.h>
#include<fstream>
#include<string.h>
#include <stdint.h>

using namespace std;

int main()
{
FILE *f;
char line[1000002];
char *m;
int n,n1=1,count=2,n2,v;
while ((m = fgets(line, 1000002, stdin))!=NULL)
{
count=2;
n2=0;
n = strlen(m);
//cout << "Input: " << line;
if(m[0] != 'E')
{
if( n==2 && m[0] == '1')
{
cout<<1<<"\n";
continue;
}
if(n==2)
{
cout<<2<<"\n";
continue;
}

n=n-1;
while(1)
{
n1=0;
while(n!=0)
{
n = n/10;
n1 = n1 + 1;
}
if(n2==n1)
break;
else
n2=n1;
n=n1;
count++;
}
cout<<count<<"\n";
}
else
break;
}

return 0;
}

1. 嗯 分析得很到位，确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样：push时，比较要push的elem和辅助栈的栈顶，elem<=min.top()，则min.push(elem).否则只要push（elem）就好。在pop的时候，比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();}，否则{stack.pop();}.

2. 这道题目的核心一句话是：取还是不取。
如果当前取，则index+1作为参数。如果当前不取，则任用index作为参数。