记录编号	462708	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]Contra	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	5.648 s
提交时间	2017-10-22 21:12:11	内存使用	0.63 MiB

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define eps 1e-15
int n,r,q,mx;
double s;
struct matrix {
	double M[105][105];
	matrix() {memset(M,0,sizeof(M));}
	friend matrix operator * (matrix a1,matrix a2) {
		matrix res;
		for(int i=1; i<=mx; ++i) {
			for(int j=1; j<=mx; ++j) {
				if(a1.M[i][j]<eps)continue;
				for(int k=1; k<=mx; ++k) {
					if(a2.M[j][k]<eps)continue;
					res.M[i][k]+=a1.M[i][j]*a2.M[j][k];
				}
			}
		} return res;
	}
};
matrix qpow(matrix a,int t) {
	matrix res;
	for(int i=1; i<=mx; ++i)res.M[i][i]=1.0;
	for( ; t; t>>=1,a=a*a) if(t&1) res=res*a;
	return res;
}
int id[101][101],ID;
bool check(double p) {
	matrix ans;
	ans.M[ID][ID]=1.0;
	for(int i=1; i<=q; ++i)
		for(int j=1; j<=r; ++j) {
			ans.M[ID][id[i][j]]+=p*j;
			if(i<q&&j<r)ans.M[id[i+1][j+1]][id[i][j]]+=p;
			else if(i<q)ans.M[id[i+1][j]][id[i][j]]+=p;
			else if(j<r)ans.M[id[i][j+1]][id[i][j]]+=p;
			else ans.M[id[i][j]][id[i][j]]+=p;
			if(i>1) ans.M[id[i-1][1]][id[i][j]]+=1.0-p;
		}
	ans=qpow(ans,n);
	return ans.M[ID][id[q][1]]>s;
}
bool Main() {
	freopen("nt2012_contra.in","r",stdin);
	freopen("nt2012_contra.out","w",stdout);
	scanf("%d%d%d%lf",&n,&r,&q,&s);
	for(int i=1; i<=q; ++i) for(int j=1; j<=r; ++j) id[i][j]=++ID;
	mx=++ID;
	if(!check(1.0)) {printf("Impossible.");return 0;}
	double l=0,r=1.0,ans=0.0;
	int cnt=0;
	while(cnt++<30) {
		double mid=(l+r)/2.0;
		if(check(mid)) ans=mid,r=mid;
		else l=mid;
	}
	printf("%0.6lf",ans);
	return 0;
}
bool hh=Main();
int main(){;}