kmjp's blog

競技プログラミング参加記です

TopCoder SRM 785 : Div1 Easy EllysPalMul

Coding Phaseが微妙だったけど3Chal稼いでレート維持。
https://community.topcoder.com/stat?c=problem_statement&pm=15621&rd=17965

問題

整数Xが与えられる。
X*Nが(leading zeroを取らずに)回文になるようなNが[1,10^9]の範囲にあれば、その最小値を求めよ。

解法

Xは10^5以下なので、X*Nは10^14以下である。
そのうち回文となるようなものは10^7個程度しかない。
そこで、14桁以下の回文を生成し、Xの倍数が愚直に判定していこう。

vector<ll> S;
class EllysPalMul {
	public:
	
	pair<int,int> rev(int a) {
		int v=0;
		int d=0;
		while(a) {
			d++;
			v=v*10+a%10;
			a/=10;
		}
		return {v,d};
	}
	
	int getMin(int X) {
		if(X%10==0) return -1;
		
		ll p10[100]={};
		p10[0]=1;
		int i;
		FOR(i,10) p10[i+1]=p10[i]*10;
		
		ll mi=1LL<<60;
		
		for(i=1;i<=10000000;i++) {
			ll a=i;
			auto v=rev(i);
			ll b=v.first;
			int d=v.second;
			ll v1=a*p10[d]+b;
			ll v2=a/10*p10[d]+b;
			//cout<<i<<" "<<v1<<" "<<v2<<endl;
			if(v1%X==0) mi=min(mi,v1/X);
			if(v2%X==0) mi=min(mi,v2/X);
			
		}
		if(mi>1000000000) return -1;
		return mi;
	}
}

まとめ

最初方針間違えたし、結局凡ミスで落としたしいろいろ残念な回。