Choose Stones with Distinct Weights
National Olympiad — Regional round (2009 season)
Submission name: stones.cpp
Problem summary
Select as many stones as possible with no repeated weight.
Input
N followed by N integer stone weights.
Output
The maximum selectable stone count.
Constraints
0 < N <10000; weights are integer gram values at most10000.
Worked example
Input and output for the worked example discussed below.
Input
4 3 1 3 8
Output
3
Solution analysis
- At most one stone may be selected for each distinct weight. Duplicate stones of a weight cannot increase the answer.
- Insert every weight into a set. A set keeps one entry for each distinct value, so its size after input is the number of weight classes.
- The sample weights3,1,3,8 have classes1,3,8. Taking one stone from each class gives3, and taking four would repeat weight3.
Why it works
Every valid selection has at most the number of distinct weights. Choosing one representative of each weight attains that bound, so the set size is the optimum.
Complexity: O(N log N) time and O(N) space using an ordered set.
Watch out. Count distinct weights, not stones. Repeated inputs must not increment the answer more than once.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<set>
using namespace std;
int main(){
int n;
cin>>n;
set<int>weights;
for(int i=0;i<n;i++){
int weight;
cin>>weight;
// Insertion retains one representative of each possible weight.
weights.insert(weight);
}
cout<<weights.size()<<'\n';
}