RaceManagement.cpp

#include <bits/stdc++.h>
#define ll        long long int
#define ld        long double
#define pi        pair<int,int>
#define all(x)    x.begin(), x.end()
#define allr(x)   x.rbegin(), x.rend()
#define sz(x)     ((int)x.size())
#define ln(x)     ((int)x.length())
#define mp        make_pair
#define pb        push_back
#define ff        first
#define ss        second
#define endl      '\n'
#define dbg(x)    cout << #x << ": " << x << endl
#define clr(x,v)  memset(x, v, sizeof(x))
#define fix(x)    cout << setprecision(x) << fixed;
#define FASTIO    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

const double PI = acos(-1.0);
const double eps = 1e-9;
const ll mod = 1e9 + 7;
const ll inf = 1LL << 30;
const int MAXN = 1e5 + 5;

class RaceManagement
{
public:
    double getPayoutFactor(vector <int>, vector <int>, int);
};

/*
{30} {100} 10
0
0.7 * 100
1
0.3 * -100 * P
*/

double RaceManagement::getPayoutFactor(vector <int> prob, vector <int> amt, int need)
{
    int n = sz(amt);

    auto check = [&](double pay)
    {
        double ret = 0;
        for(int mask = 0; mask < 1 << n; mask++)
        {
            double p = 1;
            double win = 0, lose = 0;
            for(int i = 0; i < n; i++)
                if((mask >> i) & 1)
                    p *= prob[i] / 100.0, win += amt[i];
                else
                    p *= (100.0 - prob[i]) / 100.0, lose += amt[i];
            if(__builtin_popcount(mask) == 1)
                ret += p * (-win * pay + lose);
            else
                ret += p * (win + lose);
        }
        return ret > need || fabs(ret - need) < eps;
    };

    if(check(1e9)) return -2;

    double ans = -1;
    double lo = 0, hi = 1e9;
    for(int itr = 0; itr < 100; itr++)
    {
        double mid = (lo + hi) / 2;
        if(check(mid))
            ans = lo = mid;
        else
            hi = mid;
    }
    return ans;
}
// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.4 (beta) modified by pivanof
bool KawigiEdit_RunTest(int testNum, vector <int> p0, vector <int> p1, int p2, bool hasAnswer, double p3)
{
    cout << "Test " << testNum << ": [" << "{";
    for (int i = 0; int(p0.size()) > i; ++i)
    {
        if (i > 0)
        {
            cout << ",";
        }
        cout << p0[i];
    }
    cout << "}" << "," << "{";
    for (int i = 0; int(p1.size()) > i; ++i)
    {
        if (i > 0)
        {
            cout << ",";
        }
        cout << p1[i];
    }
    cout << "}" << "," << p2;
    cout << "]" << endl;
    RaceManagement *obj;
    double answer;
    obj = new RaceManagement();
    clock_t startTime = clock();
    answer = obj->getPayoutFactor(p0, p1, p2);
    clock_t endTime = clock();
    delete obj;
    bool res;
    res = true;
    cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
    if (hasAnswer)
    {
        cout << "Desired answer:" << endl;
        cout << "\t" << p3 << endl;
    }
    cout << "Your answer:" << endl;
    cout << "\t" << answer << endl;
    if (hasAnswer)
    {
        res = fabs(p3 - answer) <= 1e-9 * max(1.0, fabs(p3));
    }
    if (!res)
    {
        cout << "DOESN'T MATCH!!!!" << endl;
    }
    else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2)
    {
        cout << "FAIL the timeout" << endl;
        res = false;
    }
    else if (hasAnswer)
    {
        cout << "Match :-)" << endl;
    }
    else
    {
        cout << "OK, but is it right?" << endl;
    }
    cout << "" << endl;
    return res;
}
int main()
{
    bool all_right;
    all_right = true;

    vector <int> p0;
    vector <int> p1;
    int p2;
    double p3;

    {
        // ----- test 0 -----
        int t0[] = {30};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        int t1[] = {100};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        p2 = 10;
        p3 = 2.0;
        all_right = KawigiEdit_RunTest(0, p0, p1, p2, true, p3) && all_right;
        // ------------------
    }

    {
        // ----- test 1 -----
        int t0[] = {50, 40};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        int t1[] = {300, 200};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        p2 = 100;
        p3 = 2.076923076923077;
        all_right = KawigiEdit_RunTest(1, p0, p1, p2, true, p3) && all_right;
        // ------------------
    }

    {
        // ----- test 2 -----
        int t0[] = {50};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        int t1[] = {100};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        p2 = 1000;
        p3 = -1.0;
        all_right = KawigiEdit_RunTest(2, p0, p1, p2, true, p3) && all_right;
        // ------------------
    }

    {
        // ----- test 3 -----
        int t0[] = {0};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        int t1[] = {100};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        p2 = 100;
        p3 = -2.0;
        all_right = KawigiEdit_RunTest(3, p0, p1, p2, true, p3) && all_right;
        // ------------------
    }

    if (all_right)
    {
        cout << "You're a stud (at least on the example cases)!" << endl;
    }
    else
    {
        cout << "Some of the test cases had errors." << endl;
    }
    return 0;
}
// END KAWIGIEDIT TESTING



//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!