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; } }
まとめ
最初方針間違えたし、結局凡ミスで落としたしいろいろ残念な回。