#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = int(1e5) + 10;
int r, n;
double dp[maxn];
int usg[maxn];
int uc[maxn];
int f(double c) {
int j = 1;
for (int i=1; i<=n; ++i) {
dp[i] = 0;
j -= 10;
if (j <= 0) j = 1;
double jc = double(j)/i + dp[i-j] - c;
while (j+1 <= i) {
double tmp = double(j+1)/i + dp[i-j-1] - c;
if (jc <= tmp) {
jc = tmp;
++j;
} else break;
}
dp[i] = jc;
usg[i] = i-j;
uc[i] = uc[i-j] + 1;
}
return uc[n];
}
int main()
{
cin >> n >> r;
double cl = 0, cr = 2;
for (int i=0; i<50; ++i) {
double mid = (cl+cr)/2;
if (r <= f(mid)) cl = mid;
else cr = mid;
}
f(cl);
static char out[256];
sprintf(out, "%.10f", dp[n]+r*cl);
cout << out << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
460 KB |
Output is correct |
2 |
Correct |
4 ms |
332 KB |
Output is correct |
3 |
Correct |
3 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
332 KB |
Output is correct |
3 |
Correct |
3 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
336 KB |
Output is correct |
3 |
Correct |
3 ms |
444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
332 KB |
Output is correct |
3 |
Correct |
3 ms |
452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
344 KB |
Output is correct |
2 |
Correct |
4 ms |
332 KB |
Output is correct |
3 |
Correct |
3 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
352 KB |
Output is correct |
3 |
Correct |
4 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
332 KB |
Output is correct |
3 |
Correct |
3 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
332 KB |
Output is correct |
3 |
Correct |
3 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
332 KB |
Output is correct |
2 |
Correct |
4 ms |
332 KB |
Output is correct |
3 |
Correct |
3 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
147 ms |
1724 KB |
Output is correct |
2 |
Correct |
121 ms |
1772 KB |
Output is correct |
3 |
Correct |
102 ms |
1692 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
148 ms |
1756 KB |
Output is correct |
2 |
Correct |
116 ms |
1740 KB |
Output is correct |
3 |
Correct |
108 ms |
1740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
1740 KB |
Output is correct |
2 |
Correct |
129 ms |
1832 KB |
Output is correct |
3 |
Correct |
118 ms |
1740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
162 ms |
1784 KB |
Output is correct |
2 |
Correct |
119 ms |
1740 KB |
Output is correct |
3 |
Correct |
107 ms |
1744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
153 ms |
1740 KB |
Output is correct |
2 |
Correct |
121 ms |
1868 KB |
Output is correct |
3 |
Correct |
108 ms |
1740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
157 ms |
1836 KB |
Output is correct |
2 |
Correct |
122 ms |
1772 KB |
Output is correct |
3 |
Correct |
107 ms |
1752 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
156 ms |
1800 KB |
Output is correct |
2 |
Correct |
109 ms |
1708 KB |
Output is correct |
3 |
Correct |
104 ms |
1740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
148 ms |
1676 KB |
Output is correct |
2 |
Correct |
119 ms |
1832 KB |
Output is correct |
3 |
Correct |
105 ms |
1720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
1740 KB |
Output is correct |
2 |
Correct |
123 ms |
1796 KB |
Output is correct |
3 |
Correct |
112 ms |
1836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
163 ms |
1824 KB |
Output is correct |
2 |
Correct |
118 ms |
1768 KB |
Output is correct |
3 |
Correct |
113 ms |
1820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
164 ms |
1740 KB |
Output is correct |
2 |
Correct |
131 ms |
1860 KB |
Output is correct |
3 |
Correct |
114 ms |
1740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
160 ms |
1740 KB |
Output is correct |
2 |
Correct |
121 ms |
1832 KB |
Output is correct |
3 |
Correct |
117 ms |
1836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
154 ms |
1740 KB |
Output is correct |
2 |
Correct |
119 ms |
1836 KB |
Output is correct |
3 |
Correct |
115 ms |
1836 KB |
Output is correct |