Codeforces 70 C. Lucky Tickets

問題

切符には二つの番号(x,y)がついている。
切符がluckyであるとは、x*y=rev(x)*rev(y)が成り立つことをいう。

ただし、rev(x)は、xの数字を反転させたもので、
例えばrev(132)=231, rev(1200)=21である。

今、xとyをx≦maxx,y≦maxyとなるように決め、
(p,q) 1≦p≦xかつ1≦q≦yとなる切符を全て発行する。
このなかにluckyである切符をw個以上にしたい。

このとき、x*yの最小値およびそのときのx,yを求めよ。
x*yが最小値をとるようなx,yが複数あるときはどれを出力してもかまわない。

制約条件

maxx,maxy≦10^5

方針

luckyな切符を全列挙して、しゃくとり的なことをする。
yをxの関数と見たとき、xを増やすとyは単調減少する。

したがってx=1からmaxxまで、必要なyをしゃくとりっぽく計算することができる。

luckyな切符は次のようにして全列挙できる。
x*y=rev(x)*rev(y)
⇔x/rev(x)=rev(y)/y
したがって、xを決めたときにluckyになるyは、
rev(y)/yがx/rev(x)に等しくなるyである。

これは有理数クラスRを作って、p/rev(p)および、そのときのpの値をmultisetに入れることで、二分探索を使って全て列挙できる。

xを決めたとき、
今のところ決まっているy以下で、luckyな切符を全て作る。
luckyな切符の数がwより大きい間、yを減らし続ける。
これにより現在のxに対応するyが求まる。

それで答えを更新していけばいい。

ソースコード

const ll INF=1ll<<60;

struct R{
	int n,d;
	bool operator<(const R &r)const{
		return (ll)n*r.d<(ll)r.n*d;
	}
	bool operator==(const R &r)const{
		return n==r.n&&d==r.d;
	}
	R(int n,int d){
		int g=__gcd(n,d);
		this->n=n/g; this->d=d/g;
	}
	R(){}
};
multimap<R,int> p_revp;
int maxx,maxy,w;

int rev(int x){
	int d[20],n=0;
	for(;x;x/=10)d[n++]=x%10;
	rep(i,n)x*=10,x+=d[i];
	return x;
}
void run()
{
	cin>>maxx>>maxy>>w;
	p_revp.clear();
	for(int i=1;i<=max(maxx,maxy);i++)p_revp.insert(mp(R(i,rev(i)),i));
	
	ll ans=INF;
	int ansx=maxx,ansy=maxy,cnt=0;
	map<int,int> ys;
	
	for(int x=1;x<=maxx;x++){
		multimap<R,int>::iterator it=p_revp.find(R(rev(x),x));
		
		while(it!=p_revp.end()&&it->first==R(rev(x),x)){
			if(it->second<=ansy)cnt++, ys[it->second]++;
			it++;
		}
		
		while(cnt>w){
			map<int,int>::iterator it=--ys.end();
			int t=min(it->second,cnt-w);
			cnt-=t;
			it->second-=t;
			if(it->second==0)ys.erase(it);
			it--;
		}
		/*
		dbg(x); dbg(w); dbg(cnt);
		fr(i,ys)cerr<<" "<<i->first<<" "<<i->second<<endl;
		*/
		if(cnt>=w){
			map<int,int>::iterator it=--ys.end();
			int y=it->first;
			if(ans>x*(ll)y){
				ansx=x; ansy=y;
				ans=(ll)x*y;
			}
		}
	}
	if(ans!=INF)cout<<ansx<<" "<<ansy<<endl;
	else cout<<-1<<endl;
}