学步园

import java.util.*;
import java.math.*;

public class Main {

	/**
	 * @param args
	 */
	static String INF="99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999";
	static BigInteger a=new BigInteger(INF);
	static BigInteger snum=a;
	static boolean all9(int len){for(int i=0; i<len; ++i) if(in[i]!='9') return false; return true;}
	static BigInteger pow(int a){BigInteger r=BigInteger.ONE; while(a!=0){ --a; r=r.multiply(BigInteger.TEN);} return r;}
	static boolean up(BigInteger a){boolean ok=true; for(;a.compareTo(BigInteger.ZERO)!=0;){if(a.mod(BigInteger.TEN).compareTo(BigInteger.valueOf(9))!=0){ ok=false;break;}a=a.divide(BigInteger.TEN);}return ok;}
	static char[] in=new char[201];
	static int flen;
	static String str;
	static boolean can(int len,int s){
		
		if(s<in.length&&in[s]!='1') return false;
		for(int i=s+1; i<s+len&&i<in.length; ++i){
			if(in[i]!='0')
				return false;
		}
		return true;
	}
	static boolean check(int len){
//		System.out.println("the len is");
//		System.out.println(len);
		int count=0;
		snum=a;
		int olen=len;
		boolean ok;
		int fl,ll,i,j;
		BigInteger f,l,cn,pn;
		l=f=BigInteger.ZERO;
		for(fl=0; fl<olen; ++fl){
			len=olen;	
			if(fl+1==olen&&in[0]=='0' ) {ok=false;continue;}
			ok=true;
			cn=pn=BigInteger.valueOf(-1);
			ll=0;
			f=new BigInteger(str.substring(0, fl+1));
			i=fl+1;
			if(i<in.length&&in[i]=='0') { ok=false; continue;}
			
			int twolife=-1;
			if(all9(fl+1)&&can(len+1,fl+1)) twolife=0;

			if(fl+1==len&&all9(len)){if(!can(len+1,fl+1)) ok=false;}
			if(!ok) continue;
			cn=pn=BigInteger.valueOf(-1);
			ok=true;
            if(twolife==0) len=olen+1;
            if(twolife==-1) len=olen;
            
            j=fl+len;

			while(j<in.length){
				cn=BigInteger.ZERO;
			    cn=new BigInteger(str.substring(i, j+1));
			    i+=len;
	//		    System.out.println(cn);
				if(up(cn)) len++;
				if(pn.compareTo(BigInteger.valueOf(-1))!=0){
					if(pn.add(BigInteger.ONE).compareTo(cn)!=0) {ok=false; break;}
				}
				else{
					if(f.compareTo(cn.subtract(BigInteger.ONE).mod(pow(fl+1)))!=0){
						ok=false; break;
					}
				}
				pn=cn;
				j+=len;
				count++;
			}
			if(i<in.length&&in[i]=='0') ok=false;
			if(ok==false) continue;
			l=BigInteger.ZERO;
			if(i<in.length)
			l=new BigInteger(str.substring(i, in.length));
			ll=in.length-i;
	//		System.out.println("the last is");
	//		System.out.println(l);

			BigInteger tmp2;
			tmp2=a;
		    if(pn.compareTo(BigInteger.valueOf(-1))!=0) {if((pn.add(BigInteger.ONE).divide(pow(len-ll))).compareTo(l)!=0) ok=false;}
			else{
			int cclen;
			if(twolife==0) cclen=olen+1;
			else if(twolife==-1) cclen=olen;
			else cclen=olen;	
			if(ll+fl+1>cclen||(olen==fl+1&&ll+fl+1>=cclen)){
				BigInteger fm=(f.add(BigInteger.ONE)).divide(pow(cclen-ll));
				BigInteger lm=l.mod(pow(ll+fl+1-olen));
				tmp2=f.add((l.subtract(lm)).multiply(pow(cclen-ll)));
				if(fm.compareTo(lm)!=0)
					ok=false;
			}
			if(ok&&tmp2.compareTo(a)==0){
				int mm=fl+1;
				if(mm==olen&&all9(olen)){mm++;}
	        	tmp2=l.multiply(pow(mm)).add(((f.add(BigInteger.ONE)).mod(pow(mm))));	
	        	tmp2=tmp2.subtract(BigInteger.ONE);

			}
			}
			if(!ok) continue;
			int clen;
			if(twolife==0) clen=olen+1;
			else if(twolife==-1) clen=olen;
			else clen=olen;
			if(ok){
			   BigInteger tmp=BigInteger.ZERO;
			   if(in.length>=(clen+fl+1)){
				   for(int k=fl+1; k<fl+1+clen; ++k){
					   tmp=tmp.multiply(BigInteger.TEN).add(BigInteger.valueOf(in[k]-'0'));
				   }
				   tmp=tmp.subtract(BigInteger.ONE);
			   }
			   else{
				   tmp=tmp2;
			   }
			   if(snum.compareTo(tmp)>0)
			   { snum=tmp;flen=olen-fl;}
			   else if(snum.compareTo(tmp)==0&&flen>olen-fl){
				   flen=olen-fl;
			   }

			}
			
			
		}
		
		if(snum.compareTo(a)!=0)
			return true;
		return false;
	}
	static BigInteger caculate(BigInteger a,int len){
		BigInteger r=BigInteger.ZERO;
		BigInteger tmp=new BigInteger("9");
		for(int i=1; i<len; ++i,tmp=tmp.multiply(BigInteger.TEN)){
			r=r.add(tmp.multiply(BigInteger.valueOf(i)));
		}

		String b="1";
		for(int i=1; i<len; ++i)
			b+="0";
		BigInteger s=new BigInteger(b);
		r=r.add(a.subtract(s).multiply(BigInteger.valueOf(len)));
		return r.add(BigInteger.valueOf(flen));
	}
	static boolean all0(char[] a){
		for(int i=0; i<a.length; ++i)
			if(a[i]!='0')
				return false;
		return true;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext()){
        str=cin.next();       
        in=str.toCharArray();
        if(all0(in)) {
        	str=1+str;
        	snum=new BigInteger(str);
        	flen=2;
        	System.out.println(caculate(snum,in.length+1));
        }
        else{
        int i;
        for(i=1; i<=in.length; ++i){
        	if(check(i)){
 //       		System.out.println(i);
 //       		System.out.println(snum);
 //       		System.out.println(flen);
        		System.out.println(caculate(snum,i));
        		break;
        	}
        	
        }

        }
	}
	}
}

别人的c++代码： 
    #include<cstdio>
    #include<cstring>

    class BigNum
    {
    public:
            BigNum(char *str,int _len)
            {
                    memset(a,0,sizeof(a));
                    len=_len;
                    for(int i=len-1;i>=0;i--) a[i]=(*str++)-'0';
            }
            BigNum(int n)
            {
                    memset(a,0,sizeof(a));
                    for(len=0;n;n/=10,len++) a[len]=n%10;
            }
            operator bool() { return len>0; }
            BigNum operator++()
            {
                    a[0]++;
                    int i;
                    for(i=0;i<len && a[i]>9;i++)
                    {
                            a[i]-=10;
                            a[i+1]++;
                    }
                    if(i==len)
                    {
                            a[i]=1;
                            len++;
                    }
                    return *this;
            }
            void inc()
            {
                    a[0]++;
                    for(int i=0;i<len && a[i]>9;i++)
                    {
                            a[i]-=10;
                            a[i+1]++;
                    }
            }
            friend BigNum operator+(BigNum a,BigNum b)
            {
                    if(a.len<b.len) a.len=b.len;
                    for(int i=0;i<a.len;i++) a.a[i]+=b.a[i];
                    a.ceil();
                    return a;
            }
            friend BigNum operator+(BigNum a,int b)
            {
                    return a+(BigNum)b;
            }
            friend BigNum operator-(BigNum a,BigNum b)
            {
                    for(int i=a.len-1;i>0;i--)
                    {
                            a.a[i]-=b.a[i];
                            a.a[i]--;
                            a.a[i-1]+=10;
                    }
                    a.a[0]-=b.a[0];
                    a.ceil();
                    return a;
            }
            friend BigNum operator-(BigNum a,int b)
            {
                    return a-(BigNum)b;
            }
            friend BigNum operator*(BigNum a,BigNum b)
            {
                    BigNum c=0;
                    c.len=a.len+b.len;
                    for(int i=0;i<a.len;i++)
                            for(int j=0;j<b.len;j++) c.a[i+j]+=a.a[i]*b.a[j];
                    c.ceil();
                    return c;
            }
            friend BigNum operator*(BigNum a,int b)
            {
                    return a*(BigNum)b;
            }
            friend bool operator<(BigNum a,BigNum b)
            {
                    if(a.len==b.len)
                    {
                            int i;
                            for(i=a.len-1;i>0 && a.a[i]==b.a[i];i--);
                            return a.a[i]<b.a[i];
                    }
                    else return a.len<b.len;
            }
            friend bool find(BigNum a,char *str)
            {
                    for(int i=a.len-1;i>=0 && *str;i--)
                            if(a.a[i]!=(*str++)-'0') return false;
                    return true;
            }
            void print()
            {
                    for(int i=len-1;i>=0;i--) printf("%d",a[i]);
                    printf("/n");
            }
            int a[300],len;
    private:
            void ceil()
            {
                    for(int i=0;i<len;i++)
                    {
                            a[i+1]+=a[i]/10;
                            a[i]%=10;
                    }
                    len++;
                    while(len && !a[len-1]) len--;
            }
    };

    bool pd(char *a)
    {
            BigNum t=9,now=0;
            for(char *p=a;*p;p++,t=t*10+9)
            {
                    if(*p!='0') return false;
                    now=now*10+t;
            }
            now=now+2;
            now.print();
            return true;
    }

    char a[210];
    void work()
    {
            int len=strlen(a);
            BigNum t=0,now=0;
            if(pd(a)) return;
            for(int i=1;i<=len;i++,t=t*10+9)
            {
                    now=now+t;
                    BigNum ans=0;
                    for(int j=0;j<i;j++)
                    {
                            if(a[j]=='0') continue;
                            BigNum prev(a,j);
                            prev.inc();
                            if(j>0 && !find(prev,a+i)) continue;
                            char nn[210];
                            int k;
                            for(k=0;k<i && a[j+k];k++) nn[k]=a[j+k];
                            for(;k<i;k++) nn[k]=prev.a[i-k-1]+'0';
                            BigNum n(nn,i),temp=n;
                            int p;
                            for(p=j+i;p<len && find(++n,a+p);p+=n.len);
                            if(p>=len)
                            {
                                    temp=(temp-1)*i-now-j+1;
                                    if(!ans || temp<ans) ans=temp;
                            }
                    }
                    if(ans)
                    {
                            ans.print();
                            break;
                    }
            }
    }

    int main()
    {
            scanf("%s",a);
            work();
            return 0;
    }