QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#507993 | #3204. Risky Lottery | WorldFinalEscaped | AC ✓ | 1962ms | 4704kb | C++20 | 2.3kb | 2024-08-07 01:44:41 | 2024-08-07 01:44:41 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-5;
double best[15], bestans;
double p[15];
int n, m;
int pw3[15], go[6561][9];
double coef[8];
double calc() {
static double dp[8][6561];
for (int i = 0; i <= n; i++) {
for (int j = 0; j < pw3[m]; j++)
dp[i][j] = 0;
}
dp[0][0] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < pw3[m]; j++) {
// if (dp[i - 1][j] < eps) continue;
for (int k = 0; k < m; k++) {
// printf("%d -> %d\n", j, go[j][k]);
dp[i][go[j][k]] += dp[i - 1][j] * p[k];
}
}
// for (int j = 0; j < pw3[m]; j++) {
// printf("dp[%d][%d] = %.3f\n", i, j, dp[i][j]);
// }
}
double ans = 0;
for (int k = 0; k < m; k++) {
// ans = 0;
coef[k] = 0;
for (int i = 0; i < pw3[m]; i++) {
bool ok = true;
for (int t = 0; t < k; t++)
if ((i / pw3[t]) % 3 == 1)
ok = false;
if ((i / pw3[k]) % 3) ok = false;
if (ok) {
coef[k] += dp[n - 1][i];
// ans += p[k] * dp[n - 1][i];
}
}
// printf("%.10f\n", ans);
}
return ans;
}
mt19937 rng(114514);
const int MAGIC = 32768;
inline double rnd() {
return (rng() & (MAGIC - 1)) / 1. / MAGIC;
}
int main() {
cin >> n >> m;
pw3[0] = 1;
for (int i = 1; i <= m; i++) pw3[i] = 3 * pw3[i - 1];
for (int i = 0; i < pw3[m]; i++) {
for (int j = 0; j < m; j++) {
int cur = i / pw3[j] % 3;
if (cur == 2)
go[i][j] = i;
else
go[i][j] = i + pw3[j];
}
}
for (int i = 0; i < m; i++) p[i] = 1. / m;
// p[0] = 0.46410, p[1] = 0.26795, p[2] = 0.26795, p[3] = 0;
// printf("%.10f\n", calc());
// return 0;
int times = 3000;
while (times--) {
calc();
double all = 0;
for (int i = 0; i < m; i++) {
p[i] *= exp(coef[i]);
all += p[i];
}
for (int i = 0; i < m; i++)
p[i] /= all;
}
for (int i = 0; i < m; i++)
printf("%.5f\n", p[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3996kb
input:
3 1
output:
1.00000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4088kb
input:
3 2
output:
0.50000 0.50000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 2ms
memory: 4076kb
input:
3 3
output:
0.46410 0.26795 0.26795
result:
ok 3 numbers
Test #4:
score: 0
Accepted
time: 6ms
memory: 4084kb
input:
3 4
output:
0.45778 0.25164 0.14529 0.14529
result:
ok 4 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 4008kb
input:
4 1
output:
1.00000
result:
ok found '1.00000', expected '1.00000', error '0.00000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 4076kb
input:
4 2
output:
0.50000 0.50000
result:
ok 2 numbers
Test #7:
score: 0
Accepted
time: 2ms
memory: 4028kb
input:
4 3
output:
0.44852 0.42633 0.12515
result:
ok 3 numbers
Test #8:
score: 0
Accepted
time: 7ms
memory: 4040kb
input:
4 4
output:
0.44773 0.42487 0.12566 0.00174
result:
ok 4 numbers
Test #9:
score: 0
Accepted
time: 28ms
memory: 4176kb
input:
4 5
output:
0.44766 0.42474 0.12570 0.00175 0.00015
result:
ok 5 numbers
Test #10:
score: 0
Accepted
time: 4ms
memory: 4032kb
input:
5 4
output:
0.36157 0.32120 0.19955 0.11767
result:
ok 4 numbers
Test #11:
score: 0
Accepted
time: 31ms
memory: 4112kb
input:
5 5
output:
0.35819 0.31559 0.19182 0.09677 0.03763
result:
ok 5 numbers
Test #12:
score: 0
Accepted
time: 120ms
memory: 4068kb
input:
5 6
output:
0.35785 0.31502 0.19107 0.09511 0.03515 0.00580
result:
ok 6 numbers
Test #13:
score: 0
Accepted
time: 33ms
memory: 4120kb
input:
6 5
output:
0.32664 0.29758 0.23155 0.12260 0.02163
result:
ok 5 numbers
Test #14:
score: 0
Accepted
time: 128ms
memory: 4208kb
input:
6 6
output:
0.32653 0.29742 0.23128 0.12245 0.02165 0.00067
result:
ok 6 numbers
Test #15:
score: 0
Accepted
time: 497ms
memory: 4280kb
input:
6 7
output:
0.32652 0.29739 0.23123 0.12242 0.02166 0.00067 0.00012
result:
ok 7 numbers
Test #16:
score: 0
Accepted
time: 529ms
memory: 4236kb
input:
7 7
output:
0.29455 0.27044 0.22469 0.14066 0.05801 0.01094 0.00072
result:
ok 7 numbers
Test #17:
score: 0
Accepted
time: 1962ms
memory: 4704kb
input:
7 8
output:
0.29453 0.27042 0.22465 0.14063 0.05797 0.01091 0.00072 0.00017
result:
ok 8 numbers