QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#575810#3204. Risky LotteryqwqUwU_AC ✓206ms3976kbC++141.7kb2024-09-19 16:51:442024-09-19 16:51:46

Judging History

This is the latest submission verdict.

  • [2024-09-19 16:51:46]
  • Judged
  • Verdict: AC
  • Time: 206ms
  • Memory: 3976kb
  • [2024-09-19 16:51:44]
  • Submitted

answer

#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcountll(s)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll; 
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline ll read(){
	ll x=0,f=1,c=getchar();
	while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
const int N=11;
int n,m;
double p[N];
const double Tmax=1e6;
const double eps=1e-7,dt=0.9998,ed=1e-7;
double fac[N];
double a[N],f[N];
inline double calc(double *p){
	rep(i,1,m){
		rep(i,0,n)f[i]=(!i)*fac[n];
		rep(j,1,m)if(j!=i){
			per(s,n-1,0){
				double res=p[j];
				for(int k=1;k<=s;++k,res*=p[j]){
					if(k==1&&j<i)continue;
					f[s]+=res*f[s-k]/fac[k];
				}
			}
		}
		a[i]=f[n-1];
	}
	double avr=0;rep(i,1,m)avr+=a[i];avr/=m;
	double s=0;rep(i,1,m)s+=(avr-a[i])*(avr-a[i]);
	return s;
}
mt19937 gen(114514);
int main() {
    //freopen("data.in", "r", stdin);
	n=read(),m=read();
	fac[0]=1;rep(i,1,n)fac[i]=fac[i-1]*i;
	if(m==1){ printf("1"); return 0; }
	rep(i,1,m)p[i]=1.0/m;
	double res=calc(p),T=Tmax;
	while(T>ed){
		//int x=1,y=1;
		//rep(i,2,m){
			//if(a[i]<a[x])x=i;
			//if(a[i]>a[y])y=i;
		//}
		int x=gen()%m+1,y=gen()%m+1;
		while(x==y)x=gen()%m+1,y=gen()%m+1;
		static double q[N];
		rep(i,1,m)q[i]=p[i];
		double t=min(q[x],q[x]*(T/Tmax));
		q[x]-=t,q[y]+=t;
		double now=calc(q);
		if(now<res){
			res=now;
			rep(i,1,m)p[i]=q[i];
		}
		T*=dt;
	}
	rep(i,1,m)printf("%.6lf\n",p[i]);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3752kb

input:

3 1

output:

1

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #2:

score: 0
Accepted
time: 9ms
memory: 3976kb

input:

3 2

output:

0.500000
0.500000

result:

ok 2 numbers

Test #3:

score: 0
Accepted
time: 11ms
memory: 3904kb

input:

3 3

output:

0.464102
0.267949
0.267949

result:

ok 3 numbers

Test #4:

score: 0
Accepted
time: 15ms
memory: 3816kb

input:

3 4

output:

0.457784
0.251643
0.145286
0.145286

result:

ok 4 numbers

Test #5:

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

input:

4 1

output:

1

result:

ok found '1.00000', expected '1.00000', error '0.00000'

Test #6:

score: 0
Accepted
time: 10ms
memory: 3920kb

input:

4 2

output:

0.500000
0.500000

result:

ok 2 numbers

Test #7:

score: 0
Accepted
time: 10ms
memory: 3868kb

input:

4 3

output:

0.448523
0.426330
0.125147

result:

ok 3 numbers

Test #8:

score: 0
Accepted
time: 21ms
memory: 3784kb

input:

4 4

output:

0.447737
0.424873
0.125655
0.001736

result:

ok 4 numbers

Test #9:

score: 0
Accepted
time: 30ms
memory: 3908kb

input:

4 5

output:

0.447730
0.424860
0.125659
0.001723
0.000028

result:

ok 5 numbers

Test #10:

score: 0
Accepted
time: 28ms
memory: 3868kb

input:

5 4

output:

0.361568
0.321203
0.199555
0.117675

result:

ok 4 numbers

Test #11:

score: 0
Accepted
time: 42ms
memory: 3872kb

input:

5 5

output:

0.358191
0.315587
0.191823
0.096772
0.037627

result:

ok 5 numbers

Test #12:

score: 0
Accepted
time: 60ms
memory: 3916kb

input:

5 6

output:

0.357850
0.315018
0.191068
0.095116
0.035151
0.005797

result:

ok 6 numbers

Test #13:

score: 0
Accepted
time: 57ms
memory: 3908kb

input:

6 5

output:

0.326643
0.297580
0.231548
0.122604
0.021625

result:

ok 5 numbers

Test #14:

score: 0
Accepted
time: 81ms
memory: 3804kb

input:

6 6

output:

0.326568
0.297470
0.231360
0.122495
0.021644
0.000463

result:

ok 6 numbers

Test #15:

score: 0
Accepted
time: 113ms
memory: 3912kb

input:

6 7

output:

0.326566
0.297468
0.231356
0.122493
0.021644
0.000454
0.000019

result:

ok 7 numbers

Test #16:

score: 0
Accepted
time: 152ms
memory: 3816kb

input:

7 7

output:

0.294575
0.270479
0.224750
0.140731
0.058088
0.010979
0.000397

result:

ok 7 numbers

Test #17:

score: 0
Accepted
time: 206ms
memory: 3856kb

input:

7 8

output:

0.294569
0.270471
0.224738
0.140718
0.058072
0.010971
0.000335
0.000125

result:

ok 8 numbers