ApplesAndOrangesEasy
SRM 659 · 2015-05-01 · by zxqfl
Problem Statement
For each valid i, you know that the info[i]-th fruit Garth ate was an apple. (Fruits Garth ate are numbered starting from 1. For example, info[i]=1 means that the very first fruit Garth ate was an apple.)
Please find and return the maximum number of apples Garth could have eaten.
Notes
- If Garth makes his list at a point in time when he ate fewer than K fruits, his list will have fewer than K fruits but the requirement will still be the same: there have to be at most K/2 apples in the list.
Constraints
- N will be between 2 and 2,000, inclusive.
- K will be between 2 and N, inclusive.
- info will contain between 0 and N elements, inclusive.
- Each element of info will be between 1 and N, inclusive.
- The elements of info will be distinct.
- The elements of info will be consistent with Garth's observation.
3
2
{}
Returns: 2
Garth ate N=3 fruites. The requirement is that any K=2 consecutive fruits may contain at most K/2 = 1 apple. As info is empty, you have no additional information about the fruits Garth ate. Garth might have eaten an apple, then an orange, then an apple. This satisfies the conditions: After eating the 1st fruit, the list is [apple]. After eating the 2nd fruit, the list is [apple, orange]. After eating the 3rd fruit, the list is [orange, apple]. Each list contains at most 1 apple.
10
3
{3, 8}
Returns: 2
All fruits, except for the 3rd and the 8th, must have been oranges.
9
4
{1, 4}
Returns: 5
9
4
{2, 4}
Returns: 4
23
7
{3, 2, 9, 1, 15, 23, 20, 19}
Returns: 10
Submissions are judged against all 128 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ApplesAndOrangesEasy with a public method int maximumApples(int N, int K, vector<int> info) · 128 test cases · 2 s / 256 MB per case