import math

arrivalRate = 0.1 # a parameter modeling the rate of consumer traffic
scale = 200.0     # a parameter in the consumer price model
shape = 3         # a parameter in the consumer price model

def arrivalProb(time):
    '''Return the probability a potential customer will arrive within an hour.

    argument: time -- the number of hours remaining before sales must end

    assumption: the probability is small, so we can neglect the case that
    two or more potential customers arrive within the same hour'''

    return arrivalRate  # simple version: customer arrival independent of time

def purchaseProb(time,price):
    '''Return the probability an arriving potential customer will buy.

    arguments:
      time -- the number of hours remaining before sales must end
      price -- the price being offered to the potential customer'''

    return math.exp(-((price/scale)**shape)) # simple version: independent of time

def saleProb(time,price):
    '''Return the probability that a sale will occur within an hour.

    arguments:
      time -- the number of hours remaining before sales must end
      price -- the price being offered to any potential customer'''

    # for a sale to occur, a potential customer must arrive and buy
    return arrivalProb(time) * purchaseProb(time,price)
    
def make_table(n,m):
    return [[None]*m for i in range(n)]

def priceAndExpectedRevenue(time,seats):
    '''Return the fixed price that is best and the expected revenue for that price.

    arguments:
      time -- the number of hours remaining before sales must end
      seats -- the number of seats remaining to sell'''

    
    price = 0 # the price at which the expected revenue is achieved
    bestRevenue = 0  # the best expected revenue we have found so far

    while True:  # try different prices
        table = make_table(time+1, seats+1)

        for t in range(time+1):
            for s in range(seats+1):
                if s == 0:
                    table[t][s] = 0.0
                elif t == 0:
                    table[t][s] = 0.0
                else:
                    # consider two cases for what happens in the first hour: sale or no sale
                    # if there is a sale, we earn some revenue that first hour, and more later
                    revenueThisHour = price
                    futureRevenueAfterSale = table[t-1][s-1]
                    totalRevenueWithSale = revenueThisHour + futureRevenueAfterSale
                    # on the other hand, if there is no sale, we earn money only in the future
                    futureRevenueAfterNoSale = table[t-1][s]
                    # we need to figure out how likely we are to make a sale the first hour
                    sp = saleProb(t, price)
                    # so, putting together a weighted average (expected value)
                    table[t][s] = sp*totalRevenueWithSale + (1-sp)*futureRevenueAfterNoSale
        revenue = table[time][seats] # the revenue for the particular price we are now trying
        if revenue > bestRevenue:
            bestRevenue = revenue
            bestPrice = price
        elif revenue < bestRevenue:
            break # surely past the best choice
        price = price + 1
        
    return (bestPrice, bestRevenue)