Skip to content

Instantly share code, notes, and snippets.

@kotas kotas/
Last active Dec 30, 2015

What would you like to do?
# -*- coding: utf-8 -*-
import bisect
def main():
(num_items, num_days) = map(int, raw_input().split())
prices = sorted(int(raw_input()) for n in xrange(num_items))
goals = (int(raw_input()) for n in xrange(num_days))
for goal in goals:
print find_closest(goal, prices)
def find_closest(goal, prices):
closest = 0
maximum = prices[-1]
first_prices = slice_prices(prices, max_price = goal)
for first_price in first_prices:
if first_price + maximum < closest:
second_price = find_second_price(prices, max_price = goal - first_price, except_once = first_price)
if second_price:
current_price = first_price + second_price
if current_price == goal:
return goal
elif current_price > closest:
closest = current_price
return closest
def slice_prices(prices, max_price):
right = bisect.bisect_right(prices, max_price)
for n in xrange(right - 1, -1, -1):
yield prices[n]
def find_second_price(prices, max_price, except_once):
for price in slice_prices(prices, max_price):
if price == except_once:
except_once = None
return price
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.