QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#825814#9778. Brotatoucup-team133#AC ✓38ms4896kbC++173.1kb2024-12-21 23:23:252024-12-21 23:23:26

Judging History

你现在查看的是最新测评结果

  • [2024-12-21 23:23:26]
  • 评测
  • 测评结果:AC
  • 用时:38ms
  • 内存:4896kb
  • [2024-12-21 23:23:25]
  • 提交

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