import pprint

def solve(words, heuristic, num_sections):
    avg = sum(words)/float(len(words))

    #first compute number of words in any subslice
    num_words = [[0 for j in xrange(len(words)+1)] for i in xrange(len(words)+1)]
    for section_length in xrange(1, len(words)+1):
        #try all ranges from 0 to num words - 1
        for i in xrange(len(words) - section_length + 1):
            j = i + section_length
            num_words[i][j] = num_words[i][j-1] + words[j-1]

    #results is a 3D array[n][i][j] where n is number of sections,
    #i is the start section index, j is the end section index,
    #containing (the minimal badness, partition) or None if impossible
    #or "notprocced" if it wasn't relevant
    results = [[["notprocced" for j in xrange(len(words)+1)] for i in xrange(len(words)+1)]
               for n in xrange(num_sections+1)]

    #completely solve for spliiting into 1 section, then 2, etc... up to num_sections
    for n in xrange(1, num_sections+1):
        #try all section leigths from 1 to the num words
        for section_length in xrange(1, len(words)+1):
            #try all ranges from 0 to num words - 1
            for i in xrange(len(words) - section_length + 1):
                j = i + section_length
                if n > section_length:
                    #infinitely bad, we have too many sections
                    results[n][i][j] = (None, 0, None)
                    continue

                #what is the solution? if we have 1 section, that's the base case
                if n == 1:
                    words_in_sub = num_words[i][j]
                    results[1][i][j] = (heuristic(words_in_sub, avg), 0, None)
                else:
                    #otherwise try all partitions & pick the best
                    bestbad = None
                    bestsplits = None
                    bestpartition = None
                    for splits_on_left in xrange(1, n):
                        for partition in xrange(i+1, j):
                            bad1 = results[splits_on_left][i][partition]
                            bad2 = results[n - splits_on_left][partition][j]
                            if bad1 == "notprocced" or bad2 == "notprocced":
                                raise ValueError("not procced subproblem")
                            if bad1[0] is None or bad2[0] is None:
                                #impossible
                                continue
                            if bestbad is None or bad1[0] + bad2[0] < bestbad:
                                bestpartition = partition
                                bestsplits = splits_on_left
                                bestbad = bad1[0] + bad2[0]
                    results[n][i][j] = (bestbad, bestsplits, bestpartition)

    verbose = False
    if verbose:
        for n in xrange(len(results)):
            print "For splitting into %d sections:" % (n,)
            for i in xrange(len(results[n])):
                for j in xrange(len(results[n][i])):
                    if results[n][i][j] == "notprocced":
                        continue
                    print "From %d to %d, badness=%s" % (i, j, results[n][i][j])
            print "====="
        print num_sections, 0, len(words), results[num_sections][0][len(words)]

    #trace out the results
    splits = []
    def trace_result_of(n, i, j):
        badness, leftsplits, partition = results[n][i][j]
        #print n, i, j, "=", badness, leftsplits, partition
        if n == 1:
            splits.append(words[i:j])
            return

        trace_result_of(leftsplits, i, partition)
        trace_result_of(n-leftsplits, partition, j)
    trace_result_of(num_sections, 0, len(words))

    return splits

section_words = [100, 100, 100, 100, 100, 100, 40000, 100, 100, 100, 100]

def heuristic(num_words, avg):
    return abs(num_words - avg)**3

def print_solution(solution):
    num_words = sum(map(sum, solution))
    print "Total=%d, %d readings, avg=%.2f" % (num_words, len(solution), num_words/float(len(solution)))
    for i, breaks in enumerate(solution):
        print "Reading #%d (%5d words): %s" % (i+1, sum(breaks), breaks)

print_solution(solve(section_words, heuristic, 5))