QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#363889 | #8511. Greek Casino | ucup-team2000# | WA | 2ms | 6004kb | C++20 | 1.8kb | 2024-03-24 04:54:37 | 2024-03-24 04:54:37 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define f first
#define s second
#define lep(i,a,b) for (int i=(a); i <= (b); i++)
#define rep(i,b,a) for (int i = (b); i >= (a); i--)
typedef long double D;
const int maxn = 2e5 + 5;
D dp[maxn];
vector<int> divs[maxn];
// dp[i] = sum_j{ P(i->j) * (1+dp[j])}
// = sum_{div}sum_{j} ( P(i->j | div) * (1 + dp[j]))
// lcm(a,b) = ab / gcd(a,b)
// lcm / gcd needs to be coprime with a
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
lep(i,1,n) {
for (int j = i; j <= n; j += i) divs[j].pb(i);
}
int totW = 0;
vector<int> W(n+1);
lep(i,1,n) {
cin >> W[i];
totW += W[i];
}
rep(i,n,1) {
D num = 0;
int p_i = 0;
for (int d: divs[i]) {
p_i += W[d];
}
for (int j = 2 * i; j <= n; j += i) {
D prob = 0;
for (int d: divs[i]) {
if (__gcd(j/d,i/d)==1) {
prob+= W[d * (j/i)];
}
}
num += D(prob) * (D(1) + dp[j]);
}
num += D(p_i);
D den = D(totW - p_i);
dp[i] = num / den;
// map<int,int> probs;
// for (int d: divs[i]) {
// p_i += W[i]; // pick any divisor, gcd will be the same
// for (int j = 2 * i; j <= n; j += i) {
// if (__gcd(j/d,a/d) == 1) {
// // ab / gcd = j
// // b = j * gcd / a
// probs[j] += W[j * d / i];
// }
// }
// }
// // dp[i] = p_i(1 + dp[i]) + sum_j p[j](1 + dp[j])
// // c dp[i] = d
// int c = (1 - p_i);
// int d
}
cout << fixed << setprecision(12) << dp[1] << "\n";
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5828kb
input:
3 1 1 1
output:
3.500000000000
result:
ok found '3.500000000', expected '3.500000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 5812kb
input:
3 1 1 2
output:
3.666666666667
result:
ok found '3.666666667', expected '3.666666667', error '0.000000000'
Test #3:
score: -100
Wrong Answer
time: 2ms
memory: 6004kb
input:
1337 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
1.010368266826
result:
wrong answer 1st numbers differ - expected: '1.0183368', found: '1.0103683', error = '0.0078251'