#!/usr/bin/env pypy3

from fractions import Fraction
from itertools import combinations_with_replacement
import re, sys

help = """
Usage: ./non_adaptive.py <n> <p> <x> 

n = number of jobs
p = a range in the form [10:20:1]. 
    a single number p will be interpreted as the range [0:p].
x = similar

Examples:
    # tries different integer values of p, and x.
    ./non_adaptive.py 6 [1:20:1] [0:20:1]

    # tries different fractional values of p and x (no rounding errors)
    ./non_adaptive.py 6 [1/1:20/1:1/10] [0/1:20/1:1/10]

    # tries different floating point values of p and x (much quicker)
    ./non_adaptive.py 6 [1:20:0.1] [0:20:0.1]


"""

def read_param(s):
    if "/" in s:
        return Fraction(s)
    elif "." in s:
        return float(s)
    else:
        return int(s)


def read_range(s):
    assert s[0] == "[" and s[-1] == "]"
    t = s[1:-1].split(":")
    assert len(t) == 3
    return (read_param(t[0]), read_param(t[1]), read_param(t[2]))


def my_range(r):
    lo, hi, step = r
    v = lo
    if not v:
        v = step
    while v <= hi:
        yield v
        v += step


def cost(p, x, schedule):
    n = len(schedule) // 2
    rank = n 
    obj = p * 0      # will become a fraction if p is a fraction
    for i in range(n):
        a = schedule[2 * i: 2 * i + 2]
        if a == 'Tx':
            obj += rank
        elif a == 'Tp':
            obj += (1 + p) * rank
            rank -= 1
        elif a == 'Ex':
            obj += (p + x) * rank
            rank -= 1
        elif a == 'Ep':
            obj += p * rank
            rank -= 1
    while rank:
        obj += (p + x) * rank
        rank -= 1
    return obj


def ratio(p, x, algo):
    """Best adversarial strategy to algorithm's strategy algo
    """
    best = (1, "")
    n = len(algo)
    nT = algo.count('T')
    nE = algo.count('E')
    for nTx in range(nT + 1):
        for nEx in range(nE + 1):
            Tx = nTx
            Ex = nEx
            adv = []
            for a in algo:
                if a == 'T':
                    if Tx:
                        adv.append('Tx')
                        Tx -= 1
                    else:
                        adv.append('Tp')
                if a == 'E':
                    if Ex:
                        adv.append('Ex')
                        Ex -= 1
                    else:
                        adv.append('Ep')
            schedule = ''.join(adv)
            adv = "Ep" * (n - nTx - nEx) + "Ex" * (nTx + nEx) 
            adv_cost = cost(p, x, adv)
            if not adv_cost:
                print(p, x)
            alt = (cost(p, x, schedule) / adv_cost, schedule) 
            if alt > best:
                best = alt
    return best


def algo2(n, p, x):
    """Algorithm tries all possible strategies
    """
    best = (float('inf'), "None")
    for algo in combinations_with_replacement("TE", n):
        alt = ratio(p, x, ''.join(algo))
        if alt < best:
            best = alt
    return best

def algo1(n, p, x):
    """Algorithm tries only two phase strategies
    """
    best = (float('inf'), "None")
    for i in range(n + 1):
        algo = "T" * i + "E" * (n - i)
        alt = ratio(p, x, algo)
        if alt < best:
            best = alt
    return best


if __name__ == "__main__":
    pattern = re.compile('T*E*')

    if len(sys.argv) < 4:
        print(help)
        sys.exit(1)

    n = int(sys.argv[1])
    range_p = read_range(sys.argv[2])
    range_x = read_range(sys.argv[3])

    for p in my_range(range_p):
        for x in my_range(range_x):
            r1 = algo1(n, p, x)
            r2 = algo2(n, p, x)
            if r1[0] > r2[0]:
                print(p, x, r1, r2)
            # print(p, range_x, r1, r2)