残念ながらCが間に合わずレート微減。Hackの余地が全然なかった…。
http://codeforces.com/contest/568/problem/A
問題
P(n)はn以下の正整数のうち素数であるものの数を表す。
R(n)はn以下の正整数のうち、10進数表記で(leading zeroを除き)回文になっているものの数を表す。
有理数Aに対し、P(n)≦A*R(n)を満たす最大のnを求めよ。
解法
nの増加に対し、P(n)の方がR(n)より増加ペースが速いため、Aが大きいほど大きなnが解となる。
Aの上限は42だが、その際の解は1179858。
よって1~120万程度まで素数と回文となる正整数の数を列挙すればよい。
int P,Q; const int prime_max = 2000001; int NP,prime[300000],divp[prime_max]; map<int,int> M; void cprime() { for(int i=2;i<prime_max;i++) if(divp[i]==0) { //M[i]=NP; prime[NP++]=i; for(ll j=1LL*i*i;j>i&&j<prime_max;j+=i) divp[j]=i; } } int ispar(int num) { int d[10]={}; int n=0,i; while(num) { d[n]=num%10; num/=10; n++; } FOR(i,n) if(d[i]!=d[n-1-i]) return 0; return 1; } void solve() { int i,j,k,l,r,x,y; string s; cin>>P>>Q; cprime(); divp[1]=1; int ma=-1; ll pi=0,ru=0; for(i=1;i<=2000000;i++) { if(divp[i]==0) pi++; if(ispar(i)) ru++; if(pi*Q<=P*ru) ma=i; } if(ma==-1) cout<<"Palindromic tree is better than splay tree"<<endl; else cout<<ma<<endl; }
まとめ
解法は愚直に計算していくだけだが、最大どの位まで計算すればよいか実験が必要な問題。