EEIC Programming Contest #0 : C. Median Array

これが一番時間かかった。
https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/median-array

問題

A[1]=X、A[2]=Yとし、A[i]=2*(A[1]～A[i-1]の中間値)とする。
A[K]を求めよ。

解法

実験してみよう。
X=1、Y=10000とか極端にしてみると、A[1]とA[2]の何倍がA[i]にかかるかわかりやすい。
2の累乗ごとに規則性が見えてくる。

以下コメント内は実験で試したときのコード。

int X,Y;
int Q;
ll K;
multiset<ll> A,B;

ll XX(ll v) {
	if(v==1) return 1;
	ll cur=2;
	int s=0;
	while(1) {
		if(v<=cur+(1LL<<s)) return v-cur;
		if(v<=cur+(2LL<<s)) return cur+(2LL<<s)-v;
		cur+=2LL<<s;
		s++;
	}
	
}
ll YY(ll v) {
	if(v==1) return 0;
	if(v==2) return 1;
	ll cur=3;
	ll val=1;
	int s=1;
	while(1) {
		if(v<=cur+(1LL<<s)-val) {
			return v-cur+val;
		}
		cur+=(1LL<<s)-val;
		val<<=1;
		if(v<=cur+(1LL<<s)) return val;
		cur+=1LL<<s;
		s++;
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y>>Q;
	/*
	A.insert(X);
	B.insert(Y);
	
	for(i=3;i<=10000;i++) {
		if(A.size()==B.size()) {
			x=*A.rbegin()+*B.begin();
		}
		else {
			x=2**A.rbegin();
		}
		cout<<i<<" "<<x<<"  "<<YY(i)<<" "<<XX(i)<<endl;
		A.insert(x);
		y=*A.rbegin();
		A.erase(A.find(y));
		B.insert(y);
		if(B.size()>A.size()) {
			y=*B.begin();
			B.erase(B.begin());
			A.insert(y);
		}
	}
	*/
	while(Q--) {
		cin>>K;
		cout<<YY(K)*Y+XX(K)*X<<endl;
	}
	
	
}

まとめ

これ実験でなく解いた人どのぐらいいるんだろう。