/* Christoph Dürr - CNRS, Sorbonne University - 2020
*/

#include <string>
#include <iostream>
#include <cassert>
#include <map>
#include <fstream>

using namespace std;

// global variables
double p, x;

const int STEPS = 128;

struct Cost {
    double algo_cost, opt_cost, ratio;
    string schedule;

    Cost(string s) :schedule(s) {
        int n = 0;    // total number of jobs
        int short_jobs = 0, long_pending_jobs = 0;
        double t = 0; // current time
        algo_cost = 0;

        // compute cost of schedule
        for (int i=0; i < schedule.length(); i += 2)  
            switch(schedule[i]) {
                case 'T': 
                    n++;
                    t += 1; // duration of test
                    if (schedule[i + 1] == 'p') {
                        t += p;  // execute short jobs right away
                        algo_cost += t;
                        short_jobs++;
                    }
                    else
                        long_pending_jobs++;
                    break;
                case 'E':
                    n++;
                    if (schedule[i + 1] == 'p') 
                    {
                        t += p;
                        short_jobs++;
                    }
                    else
                    {
                        t += p + x;
                    }
                    algo_cost += t;   // job completed here
                    break;
                default:
                    long_pending_jobs--;
                    // .x or -x
                    t += p + x;       // executing of long tested job
                    algo_cost += t;
            }    
        while (long_pending_jobs --> 0) {
            t += p + x;
            algo_cost += t;
        }
        opt_cost = p * n * (n + 1) / 2 + x * (n - short_jobs) * (n - short_jobs + 1) / 2;
        ratio = algo_cost / opt_cost;
    }
    
    bool operator<(const Cost &b) const {
        return ratio < b.ratio;
    }
};

ostream &operator<<(ostream &out, const Cost &c) {
    return out << c.schedule << " " << c.algo_cost << "/" << c.opt_cost << "=" << c.ratio;
}

/* returns the ratio obtained from a given node in the game tree.
In this node there is an number of untested jobs, and a number of pending jobs among the tested long jobs.
There is a given current schedule.
    Tx = means test was long
    Tp = test was short and executed immediatly
    .x = a pending long job is executed
    Ex = long untested job is executed
    Ep = short untested job is executed
*/
Cost ratio(int untested, int long_pending_jobs, string schedule) {
    if (untested) {
        Cost best = min(max(ratio(untested - 1, long_pending_jobs,     schedule + "Tp"),
                            ratio(untested - 1, long_pending_jobs + 1, schedule + "Tx")), 
                        max(ratio(untested - 1, long_pending_jobs,     schedule + "Ep"),
                            ratio(untested - 1, long_pending_jobs,     schedule + "Ex")));
        if (long_pending_jobs) 
            return min(best, ratio(untested, long_pending_jobs - 1, schedule + ".x"));
        else
            return best;
    }
    else 
        return Cost(schedule);
}

bool contains(const string &s, char c) {
    return s.find(c) != string::npos;
}

map<string,int> color;

int get_color(const string &s) {
    if (color.count(s) == 0) 
        color[s] = color.size();
    return color[s];
}

/* builds a grid of different instances */
void build_grid(int n, double max_p, double max_x) {
    int grid[STEPS][STEPS];
    for (int pi=0; pi < STEPS; pi++) {
        p = max_p * pi / STEPS;
        for (int xi=0; xi < STEPS; xi++) {
            x = max_x * xi / STEPS;
            Cost c = ratio(n, 0, "");
            if (contains(c.schedule, '.')) {
                cout << "n=" << n << " p=" << p << " x=" << x << " " << c << endl;
            }
            int k = get_color(c.schedule);
            grid[xi][pi] = k;
        }
    }
    ofstream out;
    out.open("tmp.py");
    out << "M = [";
    for (int pi=0; pi < STEPS; pi++) {
        if (pi) 
            out << ",";
        out << "["; 
        for (int xi=0; xi < STEPS; xi++) {
            if (xi) 
                out << ",";  
            out << grid[xi][pi];
        }
        out << "]";
    }
    out << "]" << endl;
    out << "C = {";
    bool first = true;
    for (auto const& x : color) {
        if (!first) 
            out << ", ";
        out << x.second << ":\"" << x.first << "\"";
        first = false;
    }
    out << "}" << endl;
    out << "max_p = " << max_p << endl;
    out << "max_x = " << max_x << endl;
    out.close();
}

/* Usage style 1

 ./a.out n :max_p :max_x

 explores the game tree for n jobs
 and 128 values between 0 and max_p for p
 and similar for x.
 Checks for each instance if some conjecture is true.
 Namely, never execute tested long job when untested jobs are available.
 Produces a file tmp.py with a 128 times 128 matrix giving the equilibrium
 schedule for each instance.
 It can be visualized with plot_tmp.py

Usage style 2

 ./a.out n p x

 explores the game tree of a single instance
 */
int main(int argc, char*argv[]) {
    int n = atoi(argv[1]);
    if (argv[2][0] == ':')  {  
        double max_p = atof(argv[2] + 1);
        double max_x = atof(argv[3] + 1);
        build_grid(n, max_p, max_x);
    }
    else {
        p = atof(argv[2]);
        x = atof(argv[3]);
        cout << ratio(n, 0, "") << endl;
    }
    return 0;
}