gistfile1.txt

#! /bin/python
import math
from functools import lru_cache


@lru_cache(maxsize=10000)    
def compute_optimal_price_slow(prices, start_from, num_delimiters):
    raise ValueError("Interface has changed")
    if len(prices)==start_from:
        total_price=0
    elif num_delimiters==0:
        total_price=_rough_sum(prices[start_from:])
    else:
        split_price=lambda split_at: (_rough_sum(prices[start_from:split_at+1])
                                      +compute_optimal_price(prices, split_at+1,
                                                             num_delimiters-1))
        splits_range=range(start_from, len(prices))
        optimal_split=min(splits_range, key=split_price)
        optimal_price=split_price(optimal_split)
        total_price=optimal_price
    return total_price


@lru_cache(maxsize=10000)    
def compute_optimal_price(prices, start_from, num_delimiters):
    if len(prices)==start_from:
        total_price=0
    elif num_delimiters==0:
        total_price=_rough_sum_from(prices, start_from)
    else:
        min_price=1e10
        accumulator=0
        for split_at in range(start_from, len(prices)):
            accumulator+=prices[split_at]
            current_price=_compute_total_split_price(prices, split_at, accumulator, num_delimiters)
            if current_price<min_price:
                min_price=current_price
        total_price=min_price
    return total_price


@lru_cache(maxsize=10000)
def _compute_total_split_price(prices, split_at, accumulator, num_delimiters):
    rough_sum=_rough(accumulator)
    subsplit_price=compute_optimal_price(prices, split_at+1,
                                         num_delimiters-1)
    current_price=rough_sum+subsplit_price
    return current_price


@lru_cache(maxsize=10000)
def _rough_sum_from(prices, index_from):
    return _rough_sum(prices[index_from:])


@lru_cache(maxsize=10000)
def _rough_sum(prices):
    source_price=sum(prices)
    return _rough(source_price)


def _rough(num):
    remainder=num % 10
    floor_tens=num // 10
    tens=(floor_tens+1) if remainder>=5 else floor_tens
    rough=tens*10
    return rough
    

def main():
    import os
    src_path="debug.txt" if os.path.exists("debug.txt") else "input.txt"
    with open(src_path) as input_file:
        raw_data=input_file.read()
    prices, num_delimiters=parse_input(raw_data)
    price=compute_optimal_price(prices, 0, num_delimiters)
    with open("output.txt", "w") as output_file:
        output_file.write(str(price)+"\n")
    print(price)
    print(compute_optimal_price.cache_info())
    

def parse_input(raw_data):
    extract_numbers=lambda line: map(int, line.split())
    lines=raw_data.splitlines()
    _, num_delimiters=tuple(extract_numbers(lines[0]))
    prices=tuple(extract_numbers(lines[1]))
    return prices, num_delimiters


        
main()