Cod sursa(job #1996688)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 2 iulie 2017 13:40:52
Problema Bile2 Scor 60
Compilator cpp Status done
Runda Simulare 18a Marime 1 kb
#include <fstream>

using namespace std;

ifstream fin ("bile2.in"); ofstream fout ("bile2.out");

const int nmax = 1000;
double d[nmax + 1][nmax + 1];

int main() {
    int n, k;
    long long a, b;
    fin >> n >> k >> a >> b;
    ++ k;

    for (int i = 1; i <= k; ++ i) {
        d[ i ][ 1 ] = 1;
    }
    for (int i = k + 1; i <= n; ++ i) {
        d[ i ][ 1 ] = 1;

        for (int j = i - k + 2; j <= i; ++ j) {
            d[ i ][ j ] = d[i - 1][ j ] * (i - j) / i;
        }

        double coef = 1.0 / i;
        for (int j = 1; j <= k - 1; ++ j) coef *= 1.0 * j / (i - j);

        for (int j = i - k + 1; j >= 2; -- j) {
            d[ i ][ j ] = d[i - 1][ j ] * (i - j) / i + d[i - k][j - 1] * j * coef;

            coef *= 1.0 * (i - (j - 1)) / (i - k - (j - 2));
        }
    }

    int ans = -1;
    for (int i = 1; i <= n; ++ i) {
        if (1 - d[ n ][ i ] >= 1.0 * a / b) {
            ans = i; break;
        }
    }

    fout << ans << "\n";

    fin.close();
    fout.close();
    return 0;
}