読者です 読者をやめる 読者になる 読者になる

AOJ 2323: Revenge of Champernowne Constant

この問題、全AOJ-ICPC勢に嫌われてそう。
やっぱり変なコーナーケースとかもあるしなんか知らないけどオーバーフローしたのでごまかした

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
char str[110];
int b[110];
long long pow10[17];
char to[110];
char rg[210]="1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162";
int main(){
	pow10[0]=1;
	for(int i=1;i<17;i++)pow10[i]=pow10[i-1]*10;
	while(1){
		scanf("%s",str);
		if(str[0]=='#')break;
		long long ret=9999999999999999LL;
		int n=strlen(str);
		bool OK=true;
		for(int i=0;i<n;i++)if(rg[i]!=str[i])OK=false;
		if(OK){
			printf("1\n");continue;
		}
		bool oz=true;
		for(int i=0;i<n;i++)if(str[i]!='0')oz=false;
		if(oz){
			long long at=2;
			for(int i=1;i<=n;i++)at+=(pow10[i]-pow10[i-1])*i;
			printf("%lld\n",at);continue;
		}
		for(int i=1;i<=n;i++){
			for(int j=0;j<i;j++){
				if(str[j]=='0')continue;
				long long fi=0;
				for(int k=0;k<i-j;k++){
					fi*=10;
					fi+=str[j+k]-'0';
				}
				long long la=0;
				for(int k=0;k<j;k++){
					la*=10;
					la+=str[k]-'0';
				}
				long long s=la+1;
				long long t=fi;
			//	printf("%lld %lld\n",s,t);
				while(s%10==0)s/=10;
				while(t%10==0)t/=10;
				long long f=fi*pow10[j]+la;
				if(s==1&&(j==0||la)){
					if(t==1){
						f=pow10[i]-1;
					}else{
						f=(fi-1)*pow10[j]+la;
					}
				}
				f++;
				long long F=f;
				bool ok=true;
				int at=j;
				while(at<n){
					sprintf(to,"%lld",f);
					int len=strlen(to);
					for(int k=0;k<len;k++){
						if(at>=n)break;
						if(to[k]!=str[at])ok=false;
						at++;
					}
					f++;
				}
				if(ok){
					long long at=-j;
					for(int k=1;k<i;k++){
						at+=(pow10[k]-pow10[k-1])*k;
					}
					at+=(F-pow10[i-1])*i;
					if(at<0)continue;
					ret=min(ret,at+1);
				}
			}
		}
		printf("%lld\n",ret);
	}
}