QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #288414 | #5646. Uniform Chemistry | Sorting# | AC ✓ | 13ms | 5868kb | C++14 | 1.6kb | 2023-12-22 17:01:02 | 2023-12-22 17:01:03 |
Judging History
answer
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
using namespace std;
const int N = 100 + 3;
const int M = 10 + 3;
typedef long double ld;
int n, m;
ld chance[N][M][N], ans[M];
ld over[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 1; i <= m; ++i){
int s;
cin >> s;
chance[0][i][s] = 1.0;
}
over[0] = 1.0;
for(int turn = 1; turn <= n - 1; ++turn){
for(int i = 1; i <= m; ++i){
chance[turn][i][n] = chance[turn - 1][i][n];
for(int j = n - 1; j >= 1; --j){
ld coef = (ld)1.0 / (n - j);
for(int k = j + 1; k <= n; ++k){
chance[turn][i][k] += chance[turn - 1][i][j] * coef;
}
chance[turn][i][j] = 0;
}
}
over[turn] = 1.0;
for(int i = 1; i <= m; ++i)
over[turn] *= 1.0 - chance[turn][i][n];
// over[turn] = 1.0 - over[turn];
for(int i = 1; i <= m; ++i){
// cout << chance[turn][i][n] << " " << chance[turn - 1][i][n] << " curr prrev" << endl;
if(chance[turn - 1][i][n] >= (ld)1.0 - (ld)1e-9) continue;
ans[i] += (chance[turn][i][n] - chance[turn - 1][i][n]) * over[turn - 1] / (1.0 - chance[turn - 1][i][n]);
}
// for(int i = 1; i <= m; ++i){
// cout << ans[i] << " ";
// }
// cout << endl;
}
for(int i = 1; i <= m; ++i){
cout << fixed << setprecision(12) << ans[i] << " ";
}
cout << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3924kb
input:
2 3 1 1 1
output:
1.000000000000 1.000000000000 1.000000000000
result:
ok 3 numbers, max absolute error 0
Test #2:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
3 3 1 1 2
output:
0.500000000000 0.500000000000 1.000000000000
result:
ok 3 numbers, max absolute error 0
Test #3:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
3 3 1 1 1
output:
0.625000000000 0.625000000000 0.625000000000
result:
ok 3 numbers, max absolute error 0
Test #4:
score: 0
Accepted
time: 9ms
memory: 5316kb
input:
100 7 1 2 4 8 16 32 64
output:
0.178593468624 0.179810454731 0.182306770639 0.187565365588 0.199300429529 0.229356322414 0.348722517944
result:
ok 7 numbers, max absolute error 4.70999989e-10
Test #5:
score: 0
Accepted
time: 13ms
memory: 5868kb
input:
100 10 28 58 38 53 1 19 66 60 68 31
output:
0.132031244734 0.195478375445 0.147278326003 0.180169450530 0.104495283362 0.121112032972 0.227744175567 0.202506824313 0.237924893251 0.136207268849
result:
ok 10 numbers, max absolute error 4.36900516e-13
Test #6:
score: 0
Accepted
time: 13ms
memory: 5868kb
input:
100 10 86 50 88 42 88 20 29 83 89 34
output:
0.263353545116 0.096016845558 0.297346284686 0.085266761167 0.297346284686 0.065861647587 0.072497069566 0.225981038841 0.318427805743 0.076875608528
result:
ok 10 numbers, max absolute error 3.3945069e-13
Test #7:
score: 0
Accepted
time: 1ms
memory: 3876kb
input:
2 1 1
output:
1.000000000000
result:
ok found '1.000000000', expected '1.000000000', error '0.000000000'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
10 3 4 6 7
output:
0.372135416667 0.523495370370 0.667843364198
result:
ok 3 numbers, max absolute error 4.6918025e-13
Test #9:
score: 0
Accepted
time: 0ms
memory: 4244kb
input:
20 10 6 6 9 3 14 15 13 8 6 11
output:
0.151917737209 0.151917737209 0.187146469189 0.128427543102 0.316234203356 0.370434570308 0.276697753353 0.173582076306 0.151917737209 0.222613362677
result:
ok 10 numbers, max absolute error 4.08451051e-13
Test #10:
score: 0
Accepted
time: 3ms
memory: 4572kb
input:
99 2 40 55
output:
0.536614024946 0.629592693813
result:
ok 2 numbers, max absolute error 4.27435864e-13
Test #11:
score: 0
Accepted
time: 12ms
memory: 5684kb
input:
99 9 86 68 85 83 75 70 71 73 70
output:
0.294574117090 0.149234490230 0.278029476178 0.250514065747 0.182435429935 0.157263875388 0.161657850037 0.171338171587 0.157263875388
result:
ok 9 numbers, max absolute error 4.66238159e-13