kmjp's blog

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

Codeforces #315 Div1 A. Primes or Palindromes?

残念ながら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;
}

まとめ

解法は愚直に計算していくだけだが、最大どの位まで計算すればよいか実験が必要な問題。