Stamps
InterviewTime limit1sMemory limit128 MB
Given a needed stamp count and each friend's offer, find the fewest friends whose offers sum to at least the needed amount, or report impossible.
- Level
Easy3 of 10
- Topics
- Greedy, Sorting, Array, Implementation
- Solved
- No attempts yet
Problem
Everybody hates Raymond. He is the largest stamp collector on planet earth, and because of that he always makes fun of everyone else at the stamp collector parties. Fortunately, everybody loves Lucy, and she has a plan. She secretly asks her friends whether they could lend her some stamps, so that she can embarrass Raymond by showing an even larger collection than his.
Raymond is so sure of his superiority that he always announces how many stamps he will show. Since Lucy knows how many she owns, she knows how many more she needs. She also knows how many friends are willing to lend her stamps and how many each of them would lend. But she wants to borrow from as few friends as possible, and if she would need too many, she would rather not do it at all. Can you tell her the minimum number of friends she needs to borrow from?
Input
The first line contains the number of scenarios. Each scenario describes one collectors' party. The first line of a scenario contains how many stamps Lucy needs to borrow (from 1 to 1,000,000) and how many friends (from 1 to 1,000) offer to lend her some. The second line contains the number of stamps (from 1 to 10,000) that each of her friends is offering, separated by spaces.
Output
For each scenario, first print a line containing "Scenario #i:", where i is the scenario number starting at 1. Then print a line with the minimum number of friends Lucy needs to borrow from. If it is impossible to reach the required amount even by borrowing everything from everybody, print impossible instead. Print a blank line between two consecutive scenarios.