TopCoder problem "CollectingUsualPostmarks" used in SRM 415 (Division II Level One)



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 the int[] 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.
 

Definition

    
Class:CollectingUsualPostmarks
Method:numberOfPostmarks
Parameters:int[], int[]
Returns:int
Method signature:int numberOfPostmarks(int[] prices, int[] have)
(be sure your method is public)
    
 

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

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9978

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13506&pm=9978

Writer:

Gluk

Testers:

PabloGilberto , bmerry , Olexiy , ivan_metelsky

Problem categories:

Sorting