QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#825814 | #9778. Brotato | ucup-team133# | AC ✓ | 38ms | 4896kb | C++17 | 3.1kb | 2024-12-21 23:23:25 | 2024-12-21 23:23:26 |
Judging History
answer
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <random>
#include <stdio.h>
#include <fstream>
#include <functional>
#include <cassert>
#include <unordered_map>
#include <bitset>
#include <chrono>
using namespace std;
#define rep(i,n) for (int i=0;i<n;i+=1)
#define rrep(i,n) for (int i=n-1;i>-1;i--)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << " )\n";
template<class T>
using vec = vector<T>;
template<class T>
using vvec = vec<vec<T>>;
template<class T>
using vvvec = vec<vvec<T>>;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<class T>
bool chmin(T &a, T b){
if (a>b){
a = b;
return true;
}
return false;
}
template<class T>
bool chmax(T &a, T b){
if (a<b){
a = b;
return true;
}
return false;
}
template<class T>
T sum(vec<T> x){
T res=0;
for (auto e:x){
res += e;
}
return res;
}
template<class T>
void printv(vec<T> x){
for (auto e:x){
cout<<e<<" ";
}
cout<<endl;
}
template<class T,class U>
ostream& operator<<(ostream& os, const pair<T,U>& A){
os << "(" << A.first <<", " << A.second << ")";
return os;
}
template<class T>
ostream& operator<<(ostream& os, const set<T>& S){
os << "set{";
for (auto a:S){
os << a;
auto it = S.find(a);
it++;
if (it!=S.end()){
os << ", ";
}
}
os << "}";
return os;
}
template<class T0,class T1,class T2>
ostream& operator<<(ostream& os, const tuple<T0,T1,T2>& a){
auto [x,y,z] = a;
os << "(" << x << ", " << y << ", " << z << ")";
return os;
}
template<class T0,class T1,class T2,class T3>
ostream& operator<<(ostream& os, const tuple<T0,T1,T2,T3>& a){
auto [x,y,z,w] = a;
os << "(" << x << ", " << y << ", " << z << ", " << w << ")";
return os;
}
template<class T,class U>
ostream& operator<<(ostream& os, const map<U,T>& A){
os << "map{";
for (auto e:A){
os << e.first;
os << ":";
os << e.second;
os << ", ";
}
os << "}";
return os;
}
template<class T>
ostream& operator<<(ostream& os, const vec<T>& A){
os << "[";
rep(i,A.size()){
os << A[i];
if (i!=A.size()-1){
os << ", ";
}
}
os << "]" ;
return os;
}
const int MAX_CALC = 1e7;
void solve(){
int N,K;
cin>>N>>K;
chmin(K,MAX_CALC/N);
long double p;
cin>>p;
vec<long double> dp(N+1);
dp[N] = (long double)(1) / (-p + 1);
for (int i=N-1;1<=i;i--){
dp[i] = dp[i+1]/(-p + 1);
}
rep(k,K){
dp[1] = p * dp[1] + 1;
for (int i=2;i<=N;i++){
chmin(dp[i],p * dp[i] + (-p+1) * dp[i-1]);
}
}
cout << accumulate(all(dp),(long double)(0)) << endl;
}
int main(){
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout << setprecision(15);
int T = 1;
while (T--){
solve();
}
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3776kb
input:
5 0 0.5
output:
62
result:
ok found '62.000000000', expected '62.000000000', error '0.000000000'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
5 1 0.5
output:
47
result:
ok found '47.000000000', expected '47.000000000', error '0.000000000'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
10000 0 0.002
output:
247489700298.254
result:
ok found '247489700298.253997803', expected '247489700298.253692627', error '0.000000000'
Test #4:
score: 0
Accepted
time: 4ms
memory: 4884kb
input:
100000 10 0.0002
output:
38767507133.2322
result:
ok found '38767507133.232200623', expected '38767507133.232215881', error '0.000000000'
Test #5:
score: 0
Accepted
time: 2ms
memory: 4800kb
input:
100000 0 0.0002
output:
2430683127170.38
result:
ok found '2430683127170.379882812', expected '2430683127170.376953125', error '0.000000000'
Test #6:
score: 0
Accepted
time: 7ms
memory: 4864kb
input:
100000 20 0.0002
output:
801073272.231681
result:
ok found '801073272.231680989', expected '801073272.231680870', error '0.000000000'
Test #7:
score: 0
Accepted
time: 13ms
memory: 4884kb
input:
100000 40 0.0002
output:
478148.718426307
result:
ok found '478148.718426307', expected '478148.718426307', error '0.000000000'
Test #8:
score: 0
Accepted
time: 3ms
memory: 4788kb
input:
99995 4 0.0001
output:
38976542.8681758
result:
ok found '38976542.868175797', expected '38976542.868175834', error '0.000000000'
Test #9:
score: 0
Accepted
time: 4ms
memory: 4828kb
input:
99995 10 0.0001
output:
3549184.59771202
result:
ok found '3549184.597712020', expected '3549184.597712017', error '0.000000000'
Test #10:
score: 0
Accepted
time: 7ms
memory: 4748kb
input:
99995 16 0.0001
output:
399507.470556742
result:
ok found '399507.470556742', expected '399507.470556742', error '0.000000000'
Test #11:
score: 0
Accepted
time: 0ms
memory: 4788kb
input:
99990 8 0.0001
output:
7773463.94793072
result:
ok found '7773463.947930720', expected '7773463.947930722', error '0.000000000'
Test #12:
score: 0
Accepted
time: 5ms
memory: 4824kb
input:
99990 10 0.0001
output:
3547428.9454723
result:
ok found '3547428.945472300', expected '3547428.945472297', error '0.000000000'
Test #13:
score: 0
Accepted
time: 5ms
memory: 4780kb
input:
99990 12 0.0001
output:
1647102.0204344
result:
ok found '1647102.020434400', expected '1647102.020434395', error '0.000000000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
16664 1 0.0012
output:
257920044630.861
result:
ok found '257920044630.860992432', expected '257920044630.860534668', error '0.000000000'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
16664 21 0.0012
output:
92190688.544415
result:
ok found '92190688.544414997', expected '92190688.544415027', error '0.000000000'
Test #16:
score: 0
Accepted
time: 3ms
memory: 3868kb
input:
16664 41 0.0012
output:
59865.0917859199
result:
ok found '59865.091785920', expected '59865.091785920', error '0.000000000'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3780kb
input:
16659 5 0.0003
output:
63366.2644069548
result:
ok found '63366.264406955', expected '63366.264406955', error '0.000000000'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
16659 11 0.0003
output:
18120.9118635425
result:
ok found '18120.911863543', expected '18120.911863543', error '0.000000000'
Test #19:
score: 0
Accepted
time: 2ms
memory: 3840kb
input:
16659 17 0.0003
output:
16666.5554519674
result:
ok found '16666.555451967', expected '16666.555451967', error '0.000000000'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
16654 9 0.0001
output:
16656.0794165756
result:
ok found '16656.079416576', expected '16656.079416576', error '0.000000000'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
16654 11 0.0001
output:
16655.6741221724
result:
ok found '16655.674122172', expected '16655.674122172', error '0.000000000'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
16654 13 0.0001
output:
16655.6656953627
result:
ok found '16655.665695363', expected '16655.665695363', error '0.000000000'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
2774 2 0.0072
output:
28951389306.9875
result:
ok found '28951389306.987499237', expected '28951389306.987514496', error '0.000000000'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
2774 22 0.0072
output:
11312241.4506539
result:
ok found '11312241.450653899', expected '11312241.450653942', error '0.000000000'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3972kb
input:
2774 42 0.0072
output:
8222.41510850862
result:
ok found '8222.415108509', expected '8222.415108509', error '0.000000000'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3820kb
input:
2769 6 0.0021
output:
13600.5823557316
result:
ok found '13600.582355732', expected '13600.582355732', error '0.000000000'
Test #27:
score: 0
Accepted
time: 1ms
memory: 3940kb
input:
2769 12 0.0021
output:
3239.54997821113
result:
ok found '3239.549978211', expected '3239.549978211', error '0.000000000'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3944kb
input:
2769 18 0.0021
output:
2776.62819487524
result:
ok found '2776.628194875', expected '2776.628194875', error '0.000000000'
Test #29:
score: 0
Accepted
time: 1ms
memory: 3944kb
input:
2764 10 0.0007
output:
2765.98707395509
result:
ok found '2765.987073955', expected '2765.987073955', error '0.000000000'
Test #30:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
2764 12 0.0007
output:
2765.93736284997
result:
ok found '2765.937362850', expected '2765.937362850', error '0.000000000'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
2764 14 0.0007
output:
2765.93617670347
result:
ok found '2765.936176703', expected '2765.936176704', error '0.000000000'
Test #32:
score: 0
Accepted
time: 24ms
memory: 4884kb
input:
100000 1000000000 0.0001
output:
100010.0010001
result:
ok found '100010.001000100', expected '100010.001000100', error '0.000000000'
Test #33:
score: 0
Accepted
time: 38ms
memory: 4008kb
input:
1 1000000000 0.5
output:
2
result:
ok found '2.000000000', expected '2.000000000', error '0.000000000'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
50 50 0.25
output:
66.7341873337045
result:
ok found '66.734187334', expected '66.734187334', error '0.000000000'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
40 100 0.5
output:
788.633123966272
result:
ok found '788.633123966', expected '788.633123966', error '0.000000000'
Test #36:
score: 0
Accepted
time: 0ms
memory: 4004kb
input:
40 160 0.5
output:
80.0000002552479
result:
ok found '80.000000255', expected '80.000000255', error '0.000000000'
Test #37:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
40 162 0.5
output:
80.0000000982337
result:
ok found '80.000000098', expected '80.000000098', error '0.000000000'
Test #38:
score: 0
Accepted
time: 20ms
memory: 3832kb
input:
40 1000000000 0.5
output:
80
result:
ok found '80.000000000', expected '80.000000000', error '0.000000000'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
40 0 0.5000
output:
2199023255550
result:
ok found '2199023255550.000000000', expected '2199023255550.000000000', error '0.000000000'
Test #40:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
40 1 0.5000
output:
1649267441663
result:
ok found '1649267441663.000000000', expected '1649267441663.000000000', error '0.000000000'
Test #41:
score: 0
Accepted
time: 0ms
memory: 4008kb
input:
40 2 0.5000
output:
1236950581248.25
result:
ok found '1236950581248.250000000', expected '1236950581248.250000000', error '0.000000000'
Test #42:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
40 3 0.5000
output:
962072674305
result:
ok found '962072674305.000000000', expected '962072674305.000000000', error '0.000000000'
Test #43:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
40 4 0.5000
output:
738734374914.219
result:
ok found '738734374914.218994141', expected '738734374914.218750000', error '0.000000000'
Test #44:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
40 5 0.5000
output:
575525617666.953
result:
ok found '575525617666.953002930', expected '575525617666.953125000', error '0.000000000'
Test #45:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
40 10 0.5000
output:
173409304583.133
result:
ok found '173409304583.132995605', expected '173409304583.132568359', error '0.000000000'
Test #46:
score: 0
Accepted
time: 0ms
memory: 4012kb
input:
40 15 0.5000
output:
55390502923.0735
result:
ok found '55390502923.073501587', expected '55390502923.073509216', error '0.000000000'
Test #47:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
40 20 0.5000
output:
18180087821.7474
result:
ok found '18180087821.747398376', expected '18180087821.747406006', error '0.000000000'
Test #48:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
40 25 0.5000
output:
5963269457.31878
result:
ok found '5963269457.318779945', expected '5963269457.318783760', error '0.000000000'
Test #49:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
40 30 0.5000
output:
2008652291.2098
result:
ok found '2008652291.209800005', expected '2008652291.209799051', error '0.000000000'
Test #50:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
40 35 0.5000
output:
676323760.766804
result:
ok found '676323760.766803980', expected '676323760.766804099', error '0.000000000'
Test #51:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
40 40 0.5000
output:
231036317.117802
result:
ok found '231036317.117801994', expected '231036317.117801577', error '0.000000000'
Test #52:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
40 45 0.5000
output:
79224360.2456899
result:
ok found '79224360.245689899', expected '79224360.245689899', error '0.000000000'
Test #53:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
40 50 0.5000
output:
27134304.8508336
result:
ok found '27134304.850833599', expected '27134304.850833610', error '0.000000000'
Test #54:
score: 0
Accepted
time: 0ms
memory: 3780kb
input:
2 1 0.0001
output:
2.000200030004
result:
ok found '2.000200030', expected '2.000200030', error '0.000000000'
Test #55:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
2 0 0.0001
output:
2.000300040005
result:
ok found '2.000300040', expected '2.000300040', error '0.000000000'
Test #56:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
2 2 0.0001
output:
2.000200020003
result:
ok found '2.000200020', expected '2.000200020', error '0.000000000'
Test #57:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
2 3 0.0001
output:
2.000200020002
result:
ok found '2.000200020', expected '2.000200020', error '0.000000000'
Test #58:
score: 0
Accepted
time: 16ms
memory: 4884kb
input:
100000 60 0.0002
output:
100020.274838305
result:
ok found '100020.274838305', expected '100020.274838305', error '0.000000000'
Test #59:
score: 0
Accepted
time: 22ms
memory: 4744kb
input:
100000 80 0.0002
output:
100020.0040008
result:
ok found '100020.004000800', expected '100020.004000800', error '0.000000000'
Test #60:
score: 0
Accepted
time: 29ms
memory: 4784kb
input:
100000 100 0.0002
output:
100020.0040008
result:
ok found '100020.004000800', expected '100020.004000800', error '0.000000000'
Test #61:
score: 0
Accepted
time: 26ms
memory: 4896kb
input:
100000 120 0.0002
output:
100020.0040008
result:
ok found '100020.004000800', expected '100020.004000800', error '0.000000000'
Test #62:
score: 0
Accepted
time: 26ms
memory: 4888kb
input:
100000 140 0.0002
output:
100020.0040008
result:
ok found '100020.004000800', expected '100020.004000800', error '0.000000000'
Test #63:
score: 0
Accepted
time: 26ms
memory: 4740kb
input:
100000 180 0.0002
output:
100020.0040008
result:
ok found '100020.004000800', expected '100020.004000800', error '0.000000000'
Test #64:
score: 0
Accepted
time: 19ms
memory: 4840kb
input:
100000 55 0.0002
output:
100070.850328203
result:
ok found '100070.850328203', expected '100070.850328203', error '0.000000000'
Test #65:
score: 0
Accepted
time: 17ms
memory: 4784kb
input:
100000 50 0.0002
output:
103207.684193091
result:
ok found '103207.684193091', expected '103207.684193091', error '0.000000000'
Extra Test:
score: 0
Extra Test Passed