THMMY.gr

def movement(terrain, from_x, from_y, to_x, to_y):
    if to_y <= from_y:
        raise Exception("Can only go forward and not move from y = "+str(from_y) + " to y = " + 
str(to_y))
    if abs(to_y-from_y) > 1 or abs(from_x-to_x)>1:
        raise Exception('Cannot move immediately from ('+str(from_x)+','+str(from_y)+') to ('+str(to_x)
+','+str(to_y)+') because teleportation is not possible')
    return ( float(to_x-from_x)**2 + float(to_y-from_y)**2 )**0.5 * (terrain[from_x][from_y] + 
terrain[to_x][to_y])/2

def path(terrain, start_x, end_x):
    size = len(terrain) 
    t = [(_ for _ in range(size)] for _ in range(size)] 
    # size2size 2D table - DOWT create with other expressions (can cause memory problems) 
    for x in range(0, size): 
        t[x][0] = # fill in initial conditions 
    for y in range(1, size): 
        for x in range(0, size): 
            t[x][y] = # implement the recursive formula 
    return # return the correct quantity

def makestops(D):
    t = [0] * len(D)
    best = 0
    for k in range(1, len(D)):
        t[k] = float('inf')
        for i in range(k):
            for R in range(100, 201, 100):
                if D[k] - D[i] <= R:
                    q = t[i] + 2 * R - D[k] + D[i]

                    if q < t[k]:
                        t[k] = q
                        best = k

                    else:
                        t[k] = t[best]
                        if i >85:
                            print(i)

    return t[-1]


D = [0, 110, 260, 310, 400, 470, 530, 600,
700, 800, 930, 1040, 1190, 1270, 1450, 1500,
1650, 1760, 1890, 1960, 2030, 2200, 2390, 2480,
2630, 2810, 2990, 3050, 3100, 3170, 3350, 3410,
3520, 3710, 3830, 3980, 4070, 4220, 4390, 4440,
4600, 4790, 4950, 5040, 5200, 5260, 5370, 5550,
5640, 5730, 5790, 5840, 5990, 6070, 6150, 6270,
6320, 6450, 6520, 6650, 6800, 6860, 6970, 7120,
7230, 7280, 7410, 7550, 7670, 7860, 7990, 8170,
8240, 8310, 8480, 8580, 8650, 8830, 8930, 9090,
9240, 9420, 9560, 9720, 9820, 9910, 10090, 10200,
10390, 10530, 10670, 10730, 10920, 11030, 11160,
11270, 11350, 11530, 11660, 11710, 11850]

print(makestops(D))

P = [0, 1, 5, 8, 9, 10, 17, 17, 18, 20, 21, 23, 25, 27, 27,
     27, 29, 30, 32, 34, 35, 37, 38, 38, 38, 40, 41, 42,
     43, 45, 45, 46, 47, 50, 51, 52, 55, 56, 58, 65, 65,
     67]


def cut_cable(P, n):
    c = [0] * (n + 1)
    d = [0] * (n + 1)
    best = 0
    for i in range(0, n + 1):
        for j in range(i):
            q = P[i - j] + c[j]
            if q > c[i]:
                c[i] = q
                best = q
                d[i] = i - j

            else:
                c[i] = best

    return c[n], d



print(cut_cable(P, 41))