QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#265790#5646. Uniform ChemistryBitsPlease#AC ✓8ms3876kbC++201.4kb2023-11-25 21:09:272023-11-25 21:09:27

Judging History

你现在查看的是最新测评结果

  • [2023-11-25 21:09:27]
  • 评测
  • 测评结果:AC
  • 用时:8ms
  • 内存:3876kb
  • [2023-11-25 21:09:27]
  • 提交

answer

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;

#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
  cout << vars << " = ";
  string delim = "";
  (..., (cout << delim << values, delim = ", "));
  cout << '\n';
}

using ld = long double;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<ld>> win(m + 1, vector<ld>(n + 1));
  for (int i = 0; i < m; ++i) {
    int s;
    cin >> s;
    vector<vector<ld>> dp(n, vector<ld>(n + 1));
    dp[0][s] = 1;
    for (int k = 1; k < n; ++k) {
      for (int z = s; z < n; ++z) {
        double p = 1.0 / (n - z);
        for (int x = z + 1; x <= n; ++x) {
          dp[k][x] += dp[k - 1][z] * p;
        }
      }
    }
    for (int k = 1; k < n; ++k) {
      win[i][k] = dp[k][n];
    }
  }
  for (int i = 0; i < m; ++i) {
    double ans = 0;
    for (int j = 1; j < n; ++j) {
      double all = 1;
      for (int k = 0; k < m; ++k) if (k != i) {
        double cur = 0;
        for (int z = 0; z < j; ++z) {
          cur += win[k][z];
        }
        all *= (1 - cur);
      }
      ans += all * win[i][j];
    }
    cout << fixed << setprecision(10) << ans << ' ';
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t = 1;
  // cin >> t;
  while(t--) {
    solve();
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3580kb

input:

2 3
1 1 1

output:

1.0000000000 1.0000000000 1.0000000000 

result:

ok 3 numbers, max absolute error 0

Test #2:

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

input:

3 3
1 1 2

output:

0.5000000000 0.5000000000 1.0000000000 

result:

ok 3 numbers, max absolute error 0

Test #3:

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

input:

3 3
1 1 1

output:

0.6250000000 0.6250000000 0.6250000000 

result:

ok 3 numbers, max absolute error 0

Test #4:

score: 0
Accepted
time: 8ms
memory: 3744kb

input:

100 7
1 2 4 8 16 32 64

output:

0.1785934686 0.1798104547 0.1823067706 0.1875653656 0.1993004295 0.2293563224 0.3487225179 

result:

ok 7 numbers, max absolute error 5.00000014e-10

Test #5:

score: 0
Accepted
time: 6ms
memory: 3876kb

input:

100 10
28 58 38 53 1 19 66 60 68 31

output:

0.1320312447 0.1954783754 0.1472783260 0.1801694505 0.1044952834 0.1211120330 0.2277441756 0.2025068243 0.2379248933 0.1362072688 

result:

ok 10 numbers, max absolute error 4.86312102e-11

Test #6:

score: 0
Accepted
time: 4ms
memory: 3692kb

input:

100 10
86 50 88 42 88 20 29 83 89 34

output:

0.2633535451 0.0960168456 0.2973462847 0.0852667612 0.2973462847 0.0658616476 0.0724970696 0.2259810388 0.3184278057 0.0768756085 

result:

ok 10 numbers, max absolute error 4.29709601e-11

Test #7:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

2 1
1

output:

1.0000000000 

result:

ok found '1.000000000', expected '1.000000000', error '0.000000000'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3628kb

input:

10 3
4 6 7

output:

0.3721354167 0.5234953704 0.6678433642 

result:

ok 3 numbers, max absolute error 3.33333916e-11

Test #9:

score: 0
Accepted
time: 1ms
memory: 3708kb

input:

20 10
6 6 9 3 14 15 13 8 6 11

output:

0.1519177372 0.1519177372 0.1871464692 0.1284275431 0.3162342034 0.3704345703 0.2766977534 0.1735820763 0.1519177372 0.2226133627 

result:

ok 10 numbers, max absolute error 4.67095806e-11

Test #10:

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

input:

99 2
40 55

output:

0.5366140249 0.6295926938 

result:

ok 2 numbers, max absolute error 4.64274175e-11

Test #11:

score: 0
Accepted
time: 2ms
memory: 3720kb

input:

99 9
86 68 85 83 75 70 71 73 70

output:

0.2945741171 0.1492344902 0.2780294762 0.2505140657 0.1824354299 0.1572638754 0.1616578500 0.1713381716 0.1572638754 

result:

ok 9 numbers, max absolute error 4.65337768e-11