首页 > ACM题库 > HDU-杭电 > hdu 2498 Digits[解题报告]hoj
2014
02-09

hdu 2498 Digits[解题报告]hoj

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作为参数。