Submission #65470056

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long N;
    int T, M, K;
    cin >> N >> T >> M >> K;
    vector<vector<double>> V(T+1, vector<double>(T*M+1, 0.0));
    for(int j = 0; j <= T*M; j++){
        V[T][j] = (j >= K ? 1.0 : 0.0);
    }
    for(int t = T-1; t >= 0; t--){
        for(int j = 0; j <= t*M; j++){
            double best = 0.0;
            for(int u = 1; u <= M && u <= N; u++){
                int q = M / u;
                int r = M - u*q;
                double P0 = 1.0 - double(u)/N;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long N;
    int T, M, K;
    cin >> N >> T >> M >> K;
    vector<vector<double>> V(T+1, vector<double>(T*M+1, 0.0));

    for(int j = 0; j <= T*M; j++){
        V[T][j] = (j >= K ? 1.0 : 0.0);
    }
    for(int t = T-1; t >= 0; t--){
        for(int j = 0; j <= t*M; j++){
            double best = 0.0;
            for(int u = 1; u <= M && u <= N; u++){
                int q = M / u;
                int r = M - u*q;
                double P0 = 1.0 - double(u)/N;
                double Pq = double(u - r)/N;
                double Pq1 = double(r)/N;
                double expected = 0.0;
                expected += P0 * V[t+1][j];
                expected += Pq * V[t+1][j + q];
                expected += Pq1 * V[t+1][j + q + 1];
                best = max(best, expected);
            }
            V[t][j] = best;
        }
    }
    cout << fixed << setprecision(12) << V[0][0] << "\n";
    return 0;
}

Submission Info

Judge Result