QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#389177 | #8511. Greek Casino | ucup-team1716# | WA | 1ms | 7696kb | C++14 | 1.3kb | 2024-04-14 04:29:41 | 2024-04-14 04:29:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
int n, sumw, w[MAXN + 5];
double gen[MAXN + 5], t[MAXN + 5], p[MAXN + 5];
vector<int> divs[MAXN + 5];
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> w[i];
sumw += w[i];
}
for (int i = 1; i <= n; ++i) {
gen[i] = (double)w[i] / sumw;
}
for (int i = 1; i <= n; ++i) {
for (int j = i; j <= n; j += i) {
divs[j].push_back(i);
}
}
for (int i = 1; i <= n; ++i) {
double prob = 0;
for (int j = 0; j < (int)divs[i].size(); ++j) {
prob += gen[divs[i][j]];
}
t[i] = 1.0 / (1.0 - prob);
}
p[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 0; j < (int)divs[i].size(); ++j) {
int d1 = divs[i][j];
if (d1 == i) continue;
assert(i % d1 == 0);
int k = lower_bound(divs[i].begin(), divs[i].end(), i / d1) - divs[i].begin();
for (; k < (int)divs[i].size(); ++k) {
int d2 = divs[i][k];
if ((long long)d1 / __gcd(d1, d2) * d2 == i) {
p[i] += p[d1] * t[d1] * gen[d2];
}
}
}
}
// for (int i = 1; i <= n; ++i) {
// cout << t[i] << " ";
// }
// cout << endl;
// for (int i = 1; i <= n; ++i) {
// cout << p[i] << " ";
// }
// cout << endl;
double ans = 0;
for (int i = 1; i <= n; ++i) {
ans += p[i] * t[i];
}
cout << ans - 1 << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 6864kb
input:
3 1 1 1
output:
3.5
result:
ok found '3.500000000', expected '3.500000000', error '0.000000000'
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 7696kb
input:
3 1 1 2
output:
3.66667
result:
wrong answer 1st numbers differ - expected: '3.6666667', found: '3.6666700', error = '0.0000009'