CollectingUsualPostmarks
SRM 415 · 2008-08-26 · by Gluk
SRM 415 · 2008-08-26 · by Gluk · Sorting
Problem Statement
Problem Statement
Your hobby is collecting postmarks. There is a total of N distinct postmarks, numbered from 0 to N-1. Their prices are given in the int[] prices, where the i-th element (0-indexed) is the price of postmark i.
Your goal is to collect as many distinct postmarks as possible. The postmarks you currently have are given in theint[] have. Initially, you have no money. You can sell postmarks to get money to buy different postmarks. Return the maximum number of distinct postmarks you can collect.
Your goal is to collect as many distinct postmarks as possible. The postmarks you currently have are given in the
Constraints
- N will be between 1 and 50, inclusive.
- prices will contain exactly N elements.
- Each element of prices will be between 1 and 1,000,000, inclusive.
- have will contain between 0 and N elements, inclusive.
- All elements of have will be distinct.
- Each element of have will be between 0 and N-1, inclusive.
Examples
0)
{13,10,14,20}
{3,0,2,1}
Returns: 4
You already have all the postmarks.
1)
{7,5,9,7}
{}
Returns: 0
You have no postmarks so you can do nothing.
2)
{4,13,9,1,5}
{1,3,2}
Returns: 4
Sell postmark 2 and buy postmarks 0 and 4.
3)
{16,32,13,2,17,10,8,8,20,17}
{7,0,4,1,6,8}
Returns: 8
4)
{103319,56341,86810,6759,22569,73426,43476,54173,73949,15507,153082,71186,62462,56242,25423,9339,126400,96946,82740,138962,50488,54254,59483}
{21,4,9,18,3,20,7,1,5,15,12,0,6,8}
Returns: 15
Submissions are judged against all 92 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CollectingUsualPostmarks with a public method int numberOfPostmarks(vector<int> prices, vector<int> have) · 92 test cases · 2 s / 256 MB per case