记录编号	133523	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]Contra	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.861 s
提交时间	2014-10-28 09:36:24	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZE_MT=40;
class MATRIX{
public:
	int n,m;
	double s[SIZE_MT][SIZE_MT];
	void clear(int a,int b){n=a,m=b;for(int i=0;i<a;i++){for(int j=0;j<b;j++){s[i][j]=0;}}}
	void clearunit(int a){clear(a,a);for(int i=0;i<a;i++) s[i][i]=1;}
};
MATRIX operator * (MATRIX a,MATRIX b){
	MATRIX c;
	c.n=a.n,c.m=b.m;
	for(int i=0;i<c.n;i++)
		for(int j=0;j<c.m;j++){
			c.s[i][j]=0;
			for(int k=0;k<a.m;k++)
				c.s[i][j]+=a.s[i][k]*b.s[k][j];
		}
	return c;
}
MATRIX quickpow(MATRIX a,int n){
	MATRIX ans;ans.clearunit(a.n);
	while(n){
		if(n&1) ans=ans*a;
		a=a*a;
		n>>=1;
	}
	return ans;
}
pair<int,int> states[SIZE_MT];int stot;
//其中first是u值,second是生命值
int N,R,Q;
double S;
int findstate(int u,int q){
	return find(states+1,states+stot+1,make_pair(u,q))-states;
}
MATRIX transfer(double p){//过关概率为p
	MATRIX D;
	//0是ans
	D.clear(stot+1,stot+1);
	//D.s[i][j]代表每次转移时i对之后的j的贡献系数
	D.s[0][0]=1;
	for(int i=1;i<=stot;i++){
		int u=states[i].first,q=states[i].second;
		//过了则u++,q++
		D.s[i][findstate(min(u+1,R),min(q+1,Q))]=p;
		D.s[i][0]=p*min(u+1,R);
		//不过则u=0,q--
		if(q-1) D.s[i][findstate(0,q-1)]=1-p;
	}
	return D;
}
double calc(double p){
	MATRIX D=transfer(p);
	MATRIX O;O.clear(1,stot+1);
	O.s[0][findstate(0,Q)]=1;
	O=O*quickpow(D,N);
	return O.s[0][0];
}
void work(void){
	if(calc(1.0)<=S){
		printf("Impossible.\n");
		return;
	}
	double l=0,r=1.0;
	int tot=0;
	while(tot++<30){
		double mid=(l+r)/2;
		if(calc(mid)>=S) r=mid;
		else l=mid;
	}
	printf("%.6lf\n",l);
}
void make_states(void){//给合法状态打一张表
	stot=0;
	for(int u=0;u<=R;u++){
		//此时生命值>=u+1
		for(int j=min(u+1,Q);j<=Q;j++) states[++stot]=make_pair(u,j);
	}
}
int main(){
	freopen("nt2012_contra.in","r",stdin);
	freopen("nt2012_contra.out","w",stdout);
	cin>>N>>R>>Q>>S;
	make_states();
	work();
	return 0;
}