UVa 11057

From Algorithmist
Jump to navigation Jump to search

11057 - Exact Sum[edit]

Summary[edit]

Peter wants to spend his allowance on books. It takes him a week to read a book because he likes to savour every word. Peter receives his allowance every two weeks, so he'd like to buy two books that he can read until he gets his allowance again.

Given the value of his allowance, and the prices of a list of books that he wants, find two books that add up to his allowance exactly. Where there are multiple answers, output the pair that minimizes the difference in price between the two books.

Explanation[edit]

There can be up to 10000 books in the worst case, so we can't afford to check every pair of books. So, we need to be a bit more clever. If our target is and you choose to buy a book of price , the price of the other book must be . If we sort the books then we can find the other book in logarithmic time using binary search. Keep track of the books that add up to the target with the least difference.

Note: The problem statement specifically states that there will always be a solution. In other words, there will always be at least two books that add up to the target value.

Solutions[edit]

Input[edit]

2
40 40
80

5
10 2 6 8 4
10

Output[edit]

Peter should buy books whose prices are 40 and 40.

Peter should buy books whose prices are 4 and 6.