# PPaste!

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75``` ```import sys import itertools from bisect import bisect_right def parse_input(): """ Returns a couple: the objective calories and a list of restaurants (name, calories) """ objective = int(sys.stdin.readline()) restaurants = [] for line in sys.stdin.readlines(): name, cal = (x.strip('" \n') for x in line.split('=')) cal = int(cal) restaurants.append((name, cal)) return objective, restaurants def naive_create_schedule(objective, restaurants, days=5): """ Returns the schedule: the calories that we will eat this week and the list of restaurants that are the closest to our objective """ assert(days <= len(restaurants)) sol_value = 0 sol_names = [] for restaurants in itertools.combinations(restaurants, days): calories = sum(restaurant[1] for restaurant in restaurants) if abs(objective - calories) < abs(objective - sol_value): sol_value = calories sol_names = [restaurant[0] for restaurant in restaurants] return sol_value, sol_names def fast_create_schedule(objective, restaurants, days=5): """ Returns the schedule: the calories that we will eat this week and the list of restaurants Greedy: We pick the restaurant that is close to the per-day calories we need to eat """ # We sort the restaurants list to use binary search and keep track of the # old indexes restaurants_cal = sorted( [(restaurant[1], i) for i, restaurant in enumerate(restaurants)] ) sol_value = 0 sol_names = [] for i in range(days): mean = objective / (days - i) # Find the closest restaurant to the mean # (rightmost value less than or equal to) j = bisect_right(restaurants_cal, (mean, 0)) - 1 cal, index = restaurants_cal[j] sol_value += cal sol_names.append(restaurants[index][0]) objective -= cal del restaurants_cal[j] return sol_value, sol_names if __name__ == '__main__': cal, restaurants = parse_input() print(fast_create_schedule(cal, restaurants, days=5)) print(naive_create_schedule(cal, restaurants, days=5)) ```