QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #773042 | #8037. Gambler's Ruin | Andeviking | WA | 1ms | 3980kb | C++20 | 1.9kb | 2024-11-23 00:07:15 | 2024-11-23 00:07:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<long double> p;
vector<ll> c;
int n;
const long double EPS = 1e-10L;
long double f(long double x, long double y)
{
ll sx = 0, sy = 0;
for (int i = 1; i <= n; ++i)
if (p[i] * x >= 1)
sx += c[i];
else if ((1 - p[i]) * y >= 1)
sy += c[i];
// cout << sx << ' ' << sy << ' ' << x << ' ' << y << ' ' << sx + sy - max(sx * x, sy * y) << '\n';
return sx + sy - max(sx * x, sy * y);
}
long double get(long double x)
{
long double l = 0, r = 1000000;
long double lans = f(x, l), rans = f(x, r);
long double ans = max(lans, rans);
for (int _ = 0; _ < 100; ++_) {
long double lmid = l + (r - l) / 3;
long double rmid = r - (r - l) / 3;
lans = f(x, lmid), rans = f(x, rmid);
ans = max(lans, rans);
if (lans - rans >= EPS)
r = rmid;
else
l = lmid;
}
// cout << x << ' ' << l << ' ' << ans << '\n';
return ans;
}
void solve()
{
cin >> n;
p.resize(n + 5);
c.resize(n + 5);
for (int i = 1; i <= n; ++i)
cin >> p[i] >> c[i];
long double l = 0, r = 1000000;
long double lans = get(l), rans = get(r);
long double ans = max(lans, rans);
for (int _ = 0; _ < 100; ++_) {
long double lmid = l + (r - l) / 3;
long double rmid = r - (r - l) / 3;
lans = get(lmid), rans = get(rmid);
ans = max(lans, rans);
if (lans - rans >= EPS)
r = rmid;
else
l = lmid;
}
// cout << f(1 / .6L, 1.9) << '\n';
// cout << get(1 / .6L) << '\n';
cout << fixed << setprecision(10) << ans << '\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T = 1;
while (T--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3848kb
input:
2 1 15 0 10
output:
9.9999999997
result:
ok found '10.0000000', expected '10.0000000', error '0.0000000'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
3 0.4 100 0.5 100 0.6 100
output:
33.3333333332
result:
ok found '33.3333333', expected '33.3333333', error '0.0000000'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3908kb
input:
1 0 1
output:
-0.0000000001
result:
ok found '-0.0000000', expected '0.0000000', error '0.0000000'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3860kb
input:
2 1 0 1 100
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3864kb
input:
1 0.5 100
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3960kb
input:
3 0.4 100 0.6 100 0.6 100
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3892kb
input:
3 0.2 100 0.2 100 0.8 100
output:
49.9999999999
result:
ok found '50.0000000', expected '50.0000000', error '0.0000000'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
2 0.999999 1000000 0.999998 2
output:
0.9999983793
result:
ok found '0.9999984', expected '0.9999990', error '0.0000006'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3980kb
input:
2 0 100000 0.000001 1
output:
0.0000000000
result:
ok found '0.0000000', expected '0.0000000', error '-0.0000000'
Test #10:
score: -100
Wrong Answer
time: 1ms
memory: 3852kb
input:
2 0 1000000000 0.000001 1
output:
0.0000000000
result:
wrong answer 1st numbers differ - expected: '1.0000000', found: '0.0000000', error = '1.0000000'