#C7762. Flower Pot Placement Optimizer
Flower Pot Placement Optimizer
Flower Pot Placement Optimizer
You are given a row of houses located at distinct integer positions along a street. The positions are provided in non-decreasing order. Additionally, you are given an integer k representing the number of flower pots available.
Your task is to determine the maximum number of flower pots that can be placed following the placement rules described below:
- A flower pot must be placed at an integer coordinate.
- No flower pot is placed at a location that is already occupied by a house.
- You cannot place more than k flower pots.
- Under the rules provided, it turns out that if you have at least one flower pot, you are able to place exactly k pots.
Note: Even though the positions of the houses are given, the optimal strategy always allows placing exactly k pots (or 0 if k is 0). Your program should compute and output this number.
The following examples illustrate the requirement:
- For houses at positions [1, 2, 3, 7, 10] with k = 3, the answer is 3.
- For houses at positions [1, 2, 3, 7] with k = 2, the answer is 2.
- For houses at positions [1, 2, 3] with k = 1, the answer is 1.
inputFormat
The input is given via stdin and consists of two lines:
- The first line contains two integers n and k, where n is the number of houses and k is the number of available flower pots.
- The second line contains n space-separated integers representing the positions of the houses in non-decreasing order.
outputFormat
Output a single integer via stdout — the maximum number of flower pots that can be placed according to the rules.
## sample5 3
1 2 3 7 10
3