QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103348#5009. LightbulbsjoesmittyAC ✓54ms66120kbC++203.2kb2023-05-05 12:23:062023-05-05 12:23:08

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-05 12:23:08]
  • 评测
  • 测评结果:AC
  • 用时:54ms
  • 内存:66120kb
  • [2023-05-05 12:23:06]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
 
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
 
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
 
template <typename T>
void pr(vector<T> &v) {
    FOR(i, 0, sz(v)) cout << v[i] << " ";
    cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
    FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
    cin >> x;
}
template <typename T>
void re(vector<T> &a) {
    FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
    re(first);
    re(rest...);
}
template <typename T>
void pr(T x) {
    cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
    cout << first << " ";
    pr(rest...);
    cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
    cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
 
const ll MOD  =  1000000007;
#define inf 1e18;
#define INF INT_MAX;

long double PI = 4*atan(1);
long double eps = 1e-12;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//default_random_engine g{1};

int main() {
    //auto start = chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);cin.tie(0);
    // ofstream cout("pieaters.out");
    // ifstream cin("pieaters.in");
    #ifdef DEBUG
      freopen("input.txt", "r", stdin);
      freopen("output.txt", "w", stdout);
    #endif 
    

    int n,m;
    cin >> n >> m;
    ld p; cin >> p;
    vector<ld> ppow(2010);
    ppow[0] = 1;
    FOR(i,1,2010) {
        ppow[i] = ppow[i-1] * p;
    }
    vector<vector<ld>> dp(m+2, vector<ld>(m+2));
    vector<ld> sum(m+2);
    dp[0][0] = 1;
    dp[1][0] = 1;
    dp[1][1] = p;

    sum[1] = p;

    FOR(i,2,m+1) {
        dp[i][0] = 1;
        FOR(c,1,i+1) {
            dp[i][c] = ppow[c] + (1-p) * sum[c];
        }
        
        FOR(c,1,i+1) {
            sum[c] -= dp[i-c][c] * ppow[c-1];
            sum[c] *= p;
            sum[c] += dp[i][c];
        }
    }

    vector<ld> lt(m+1);
    RFOR(i,m+1,0) {
        lt[i] = 1 - dp[m][i + 1];
    }

    vector<ld> prgt(m+1);
    FOR(i,1,m+1) {
        prgt[i] = 1 - pow(lt[i-1], n);
    }

    ld ans = 0;
    FOR(i,1,m+1) {
        ans += prgt[i];
    }

    cout << setprecision(16) << ans << endl;
    
    

    // auto stop = chrono::high_resolution_clock::now();
    // auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
    // cout << duration.count() << endl;
    //cin.close();
    //cout.close();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3712kb

input:

2 3 0.5

output:

1.828125

result:

ok found '1.82812', expected '1.82812', error '0.00000'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3828kb

input:

47 74 1

output:

74

result:

ok found '74.00000', expected '74.00000', error '0.00000'

Test #3:

score: 0
Accepted
time: 3ms
memory: 17268kb

input:

1029 939 0.8855861

output:

98.99189010514394

result:

ok found '98.99189', expected '98.99189', error '0.00000'

Test #4:

score: 0
Accepted
time: 13ms
memory: 11832kb

input:

253 736 0.9414655

output:

159.6160091491425

result:

ok found '159.61601', expected '159.61601', error '0.00000'

Test #5:

score: 0
Accepted
time: 11ms
memory: 12120kb

input:

1484 733 0.9973144

output:

733

result:

ok found '733.00000', expected '733.00000', error '0.00000'

Test #6:

score: 0
Accepted
time: 21ms
memory: 40456kb

input:

788 1538 0.0531632

output:

4.41179676518171

result:

ok found '4.41180', expected '4.41180', error '0.00000'

Test #7:

score: 0
Accepted
time: 22ms
memory: 40344kb

input:

920 1536 0.1090426

output:

6.111925881641036

result:

ok found '6.11193', expected '6.11193', error '0.00000'

Test #8:

score: 0
Accepted
time: 16ms
memory: 31224kb

input:

1243 1331 0.1649220

output:

7.659146384674685

result:

ok found '7.65915', expected '7.65915', error '0.00000'

Test #9:

score: 0
Accepted
time: 10ms
memory: 30688kb

input:

475 1318 0.2207709

output:

8.550943477282559

result:

ok found '8.55094', expected '8.55094', error '0.00000'

Test #10:

score: 0
Accepted
time: 12ms
memory: 22828kb

input:

798 1113 0.2766503

output:

10.34886273625031

result:

ok found '10.34886', expected '10.34886', error '0.00000'

Test #11:

score: 0
Accepted
time: 9ms
memory: 23056kb

input:

1130 1120 0.3325297

output:

12.40944374793205

result:

ok found '12.40944', expected '12.40944', error '0.00000'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3956kb

input:

453 118 0.3883786

output:

11.0089219676322

result:

ok found '11.00892', expected '11.00892', error '0.00000'

Test #13:

score: 0
Accepted
time: 15ms
memory: 16852kb

input:

1675 913 0.4442579

output:

17.0173700062717

result:

ok found '17.01737', expected '17.01737', error '0.00000'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3952kb

input:

1909 100 0.5001373

output:

16.64447958681738

result:

ok found '16.64448', expected '16.64448', error '0.00000'

Test #15:

score: 0
Accepted
time: 12ms
memory: 15776kb

input:

140 895 0.5560167

output:

19.06587073561682

result:

ok found '19.06587', expected '19.06587', error '0.00000'

Test #16:

score: 0
Accepted
time: 14ms
memory: 15900kb

input:

1364 893 0.6118656

output:

27.21550514839211

result:

ok found '27.21551', expected '27.21551', error '0.00000'

Test #17:

score: 0
Accepted
time: 3ms
memory: 11160kb

input:

665 698 0.6677450

output:

30.40915854504293

result:

ok found '30.40916', expected '30.40916', error '0.00000'

Test #18:

score: 0
Accepted
time: 29ms
memory: 48304kb

input:

899 1695 0.7236244

output:

41.24939732900387

result:

ok found '41.24940', expected '41.24940', error '0.00000'

Test #19:

score: 0
Accepted
time: 22ms
memory: 38480kb

input:

1121 1500 0.7794733

output:

53.15486971527511

result:

ok found '53.15487', expected '53.15487', error '0.00000'

Test #20:

score: 0
Accepted
time: 25ms
memory: 37364kb

input:

354 1477 0.8353526

output:

65.64134871752847

result:

ok found '65.64135', expected '65.64135', error '0.00000'

Test #21:

score: 0
Accepted
time: 15ms
memory: 28844kb

input:

876 1275 0.8912320

output:

105.4989150188958

result:

ok found '105.49892', expected '105.49892', error '0.00000'

Test #22:

score: 0
Accepted
time: 13ms
memory: 29108kb

input:

1009 1280 0.9471114

output:

211.9634269995962

result:

ok found '211.96343', expected '211.96343', error '0.00000'

Test #23:

score: 0
Accepted
time: 10ms
memory: 17284kb

input:

1029 939 0.8148304

output:

61.08082887232805

result:

ok found '61.08083', expected '61.08083', error '0.00000'

Test #24:

score: 0
Accepted
time: 7ms
memory: 11936kb

input:

253 736 0.7410725

output:

37.25537609222364

result:

ok found '37.25538', expected '37.25538', error '0.00000'

Test #25:

score: 0
Accepted
time: 7ms
memory: 12136kb

input:

1484 733 0.6380010

output:

29.3678715018031

result:

ok found '29.36787', expected '29.36787', error '0.00000'

Test #26:

score: 0
Accepted
time: 19ms
memory: 40452kb

input:

788 1538 0.9987455

output:

1538

result:

ok found '1538.00000', expected '1538.00000', error '0.00000'

Test #27:

score: 0
Accepted
time: 16ms
memory: 40516kb

input:

920 1536 0.9982458

output:

1536

result:

ok found '1536.00000', expected '1536.00000', error '0.00000'

Test #28:

score: 0
Accepted
time: 31ms
memory: 31208kb

input:

1243 1331 0.9975471

output:

1331

result:

ok found '1331.00000', expected '1331.00000', error '0.00000'

Test #29:

score: 0
Accepted
time: 19ms
memory: 30564kb

input:

475 1318 0.9965706

output:

1317.854534801272

result:

ok found '1317.85453', expected '1317.85453', error '0.00000'

Test #30:

score: 0
Accepted
time: 20ms
memory: 22780kb

input:

798 1113 0.9952046

output:

1112.464529172114

result:

ok found '1112.46453', expected '1112.46453', error '0.00000'

Test #31:

score: 0
Accepted
time: 11ms
memory: 22844kb

input:

1130 1120 0.9932945

output:

1081.844388934158

result:

ok found '1081.84439', expected '1081.84439', error '0.00000'

Test #32:

score: 0
Accepted
time: 2ms
memory: 3960kb

input:

453 118 0.9906252

output:

118

result:

ok found '118.00000', expected '118.00000', error '0.00000'

Test #33:

score: 0
Accepted
time: 9ms
memory: 16796kb

input:

1675 913 0.9868909

output:

702.3323892031898

result:

ok found '702.33239', expected '702.33239', error '0.00000'

Test #34:

score: 0
Accepted
time: 1ms
memory: 3960kb

input:

1909 100 0.9816693

output:

100

result:

ok found '100.00000', expected '100.00000', error '0.00000'

Test #35:

score: 0
Accepted
time: 13ms
memory: 15928kb

input:

140 895 0.9743676

output:

318.2334251957926

result:

ok found '318.23343', expected '318.23343', error '0.00000'

Test #36:

score: 0
Accepted
time: 6ms
memory: 15896kb

input:

1364 893 0.9641641

output:

298.1443787644043

result:

ok found '298.14438', expected '298.14438', error '0.00000'

Test #37:

score: 0
Accepted
time: 3ms
memory: 11000kb

input:

665 698 0.9498898

output:

200.4524444322451

result:

ok found '200.45244', expected '200.45244', error '0.00000'

Test #38:

score: 0
Accepted
time: 54ms
memory: 66060kb

input:

2000 2000 0.9370000

output:

198.0280835332252

result:

ok found '198.02808', expected '198.02808', error '0.00000'

Test #39:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

2000 1 0.0010000

output:

0.8648000746025003

result:

ok found '0.86480', expected '0.86480', error '0.00000'

Test #40:

score: 0
Accepted
time: 51ms
memory: 66120kb

input:

1 2000 0.9974000

output:

855.0293453348893

result:

ok found '855.02935', expected '855.02935', error '0.00000'

Test #41:

score: 0
Accepted
time: 45ms
memory: 65948kb

input:

2000 2000 1.0000000

output:

2000

result:

ok found '2000.00000', expected '2000.00000', error '0.00000'

Test #42:

score: 0
Accepted
time: 50ms
memory: 65996kb

input:

2000 2000 0.0000000

output:

0

result:

ok found '0.00000', expected '0.00000', error '-0.00000'