QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#575810 | #3204. Risky Lottery | qwqUwU_ | AC ✓ | 206ms | 3976kb | C++14 | 1.7kb | 2024-09-19 16:51:44 | 2024-09-19 16:51:46 |
Judging History
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