QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#54923#4234. Tic Tac Toe CountingKING_UT#WA 3ms5832kbC++201.1kb2022-10-11 17:25:592022-10-11 17:26:00

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-11 17:26:00]
  • Judged
  • Verdict: WA
  • Time: 3ms
  • Memory: 5832kb
  • [2022-10-11 17:25:59]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)

const int nmax=55;
const int mmax=10005;

using ld=long double;

ld bin[nmax][nmax];
ld dp[nmax][mmax],eq[nmax][mmax];
ld ans[mmax];

void slv(){
	int n,m;cin>>n>>m;
	m-=n;
	
	bin[0][0]=1;
	rep(i,n+1)rep(j,n+1){
		if(i)bin[i][j]+=bin[i-1][j];
		if(j)bin[i][j]+=bin[i][j-1];
		if(i+j>0){
			bin[i][j]*=(i+j);
			bin[i][j]/=m+n+1-(i+j);
		} 
	}
	
	rng(i,1,n+1)dp[i][0]=1;
	rng(i,1,n+1)rep(j,m-i+1){
		rng(k,i,n+1){
			dp[k][j+i]+=dp[i][j]*bin[i][k-i];
		}
	}
	rep(i,m+1)eq[n][i]=1;
	gnr(i,1,n+1)per(j,m-i+1){
		rng(k,i,n+1){
			eq[i][j]+=eq[k][j+i]*bin[i][k-i];
		}
	}
	rng(i,1,n+1)rep(j,m-i+1){
		ld w=0;
		rng(k,i,n+1){
			w+=eq[k][j+i]*bin[i][k-i];
		}
		ans[n-i]+=w*dp[i][j];
	}
	rep(i,n-1)ans[i+1]+=ans[i];
	rep(i,n)ans[i]+=1;
	rep(i,n-1)ans[i+1]+=ans[i];
	
	rep(i,n)cout<<ans[i]<<endl;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	slv();
}

详细

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 5832kb

input:

4
XX..O....
X...OX...
OOOX.X.X.
OOOXXX...

output:

1.00000000000000000000
2.00000000000000000000
3.00000000000000000000
4.00000000000000000000

result:

wrong answer 1st lines differ - expected: '191 194', found: '1.00000000000000000000'