QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#215895#1777. Fortune From FollyPhantomThreshold#WA 1ms4048kbC++141.4kb2023-10-15 14:15:172023-10-15 14:15:18

Judging History

你现在查看的是最新测评结果

  • [2023-10-15 14:15:18]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4048kb
  • [2023-10-15 14:15:17]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef double frac;

namespace gauss{
	
	frac a[233][233],ans[233];
	void gauss(int ROW,int COLUMN){
		int m=COLUMN,r=1;
		int n=ROW;
		for (int i=1;i<=m && r<=n;i++){
			frac maxx=0;
			int maxp=r;
			for (int j=r;j<=n;j++){
				if (a[j][i]!=0){
					maxx=a[j][i],maxp=j;
					break;	
				}
			}
			if (maxx==0) continue;
			for (int j=i;j<=m;j++)
				swap(a[r][j],a[maxp][j]);
			for (int j=r+1;j<=n;j++){
				frac t=a[j][i]/a[r][i];
				for (int k=i;k<=m;k++){
					a[j][k]=a[j][k]-t*a[r][k];
				}
			}
			r++;
		}
		for (int i=n;i>=1;i--){
			for (int j=1;j<=m;j++){
				if (a[i][j]!=0){
					frac t=a[i][j];
					for (int l=j;l<=m;l++) a[i][l]=a[i][l]/t;
					for (int k=i-1;k>=1;k--){
						frac t=a[k][j]/a[i][j];
						for (int l=j;l<=m;l++)
							a[k][l]=a[k][l]-t*a[j][l];
					}
					break;
				}
			}
		}
		
	}
}

int n,k;
frac p;

int main(){
	ios_base::sync_with_stdio(false);
	cin >> n >> k >> p;
	
	int mx=(1<<n)-1;
	for (int mask=0;mask<=mx;mask++){
		int nxt0=((mask<<1)&mx)|0;
		int nxt1=((mask<<1)&mx)|1;
		gauss::a[mask+1][mask+1]+=1.0;
		if (__builtin_popcount(mask)>=k){
			gauss::a[mask+1][mx+2]=0.0;
		}
		else{
			gauss::a[mask+1][nxt0+1]-=(1-p);
			gauss::a[mask+1][nxt1+1]-=p;
			gauss::a[mask+1][mx+2]+=1.0;
		}
	}
	
	gauss::gauss(mx+1,mx+2);
	cout << fixed << setprecision(12) << gauss::a[1][mx+2] << "\n";
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3960kb

input:

2 1 0.0006

output:

1666.666666666542

result:

ok found '1666.6666667', expected '1666.6666667', error '0.0000000'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3992kb

input:

2 1 0.0043

output:

232.558139534885

result:

ok found '232.5581395', expected '232.5581395', error '0.0000000'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3992kb

input:

2 1 0.4202

output:

2.379819133746

result:

ok found '2.3798191', expected '2.3798191', error '0.0000000'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

2 1 0.6729

output:

1.486104919007

result:

ok found '1.4861049', expected '1.4861049', error '0.0000000'

Test #5:

score: 0
Accepted
time: 1ms
memory: 4048kb

input:

2 1 0.9925

output:

1.007556675063

result:

ok found '1.0075567', expected '1.0075567', error '0.0000000'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3992kb

input:

2 1 0.9999

output:

1.000100010001

result:

ok found '1.0001000', expected '1.0001000', error '0.0000000'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3824kb

input:

2 2 0.0006

output:

2779444.444096875377

result:

ok found '2779444.4440969', expected '2779444.4444444', error '0.0000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3828kb

input:

2 2 0.0072

output:

19429.012345685092

result:

ok found '19429.0123457', expected '19429.0123457', error '0.0000000'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

2 2 0.0848

output:

150.854396582414

result:

ok found '150.8543966', expected '150.8543966', error '0.0000000'

Test #10:

score: -100
Wrong Answer
time: 0ms
memory: 3776kb

input:

2 2 0.7554

output:

2.323801959227

result:

wrong answer 1st numbers differ - expected: '3.0762536', found: '2.3238020', error = '0.2446000'