Problem Description

During a stormy night, strong winds damaged the roof and doors of Farmer John's barn. The stalls are arranged in a single row, and cows occupy some of these stalls overnight. Since some cows are away on vacation, not all stalls contain cows. All stalls have equal width.

Farmer John needs to purchase wooden planks to cover the stall doors. The lumber supplier can provide planks of any length, but the quantity is severely limited. John wants to minimize the total length of planks purchased.

Given the maximum number of planks M, total number of stalls S, number of cows C, and the stall numbers containing cows, calculate the minimum number of stalls that must be covered when ensuring all occupied stalls are protected, while minimizing total plank length.

Input Format

First line contains three integers M, S, C.
Next C lines, each containing one integer representing a stall number with a cow.

Output Format

Output a single integer representing the number of stalls covered by planks.

Constrainst

1 ≤ M ≤ 50
1 ≤ S ≤ 200
1 ≤ C ≤ S
Stall numbers range from 1 to S.

Sample Input

4 50 18
3
4
6
8
14
15
16
17
21
25
26
27
30
31
40
41
42
43

Sample Output

25

Explanation

One feasible solution: cover stalls 3-8 with one plank, stalls 14-21 with another, stalls 25-31 with a third, and stalls 40-43 with the fourth. This covers exactly 25 stalls.

Problem Analysis

Consider stalls as a binary sequence where 1 represents an occupied stall and 0 represents an empty one. For example, 110100111 with M=2:

Option 1: First plank covers the first four stalls, second plank covers the last three stalls → total length 7
Option 2: First plank covers the first two stalls, second plank covers the last six stalls → total length 8

Different arrangements yield diffferent total lengths. The goal is to find the minimum total length.

Reverse Thinking Approach

Instead of directly determining which planks to use, consider the reverse problem:

1. Start by covering the entire span from the first cow to the last cow with a single plank
2. Then "carve out" the gaps (consecutive empty stalls) between occupied stalls
3. This carving process creates multiple segments

Proof of Equivalence

These two approaches are equivalnet:

• Any forward solution can be transformed into a reverse solution: start with full coverage, then remove the gaps
• Any reverse solution can be transformed into a forward solution: just place planks on the remaining segments
• Both yield the same total length

Optimal Strategy

For gaps (consecutive zeros), in an optimal solution, when carving out a gap, either carve out the entire continuous gap or don't carve it at all. Partial carving is never optimal.

Algorithm steps:

1. Find all gaps between consecutive occupied stalls
2. Sort these gaps in descending order
3. Select the largest M-1 gaps to carve out
4. The answer equals: (last stall - first stall + 1) - sum of selected gaps

Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int maxPlanks, totalStalls, occupiedCount;
    cin >> maxPlanks >> totalStalls >> occupiedCount;
    
    vector<int> positions(occupiedCount);
    for (int i = 0; i < occupiedCount; i++) {
        cin >> positions[i];
    }
    
    sort(positions.begin(), positions.end());
    
    int totalLength = positions[occupiedCount - 1] - positions[0] + 1;
    
    vector<int> gaps;
    for (int i = 0; i < occupiedCount - 1; i++) {
        int gapSize = positions[i + 1] - positions[i] - 1;
        if (gapSize > 0) {
            gaps.push_back(gapSize);
        }
    }
    
    sort(gaps.begin(), gaps.end(), greater<int>());
    
    int carveCount = min(maxPlanks - 1, (int)gaps.size());
    for (int i = 0; i < carveCount; i++) {
        totalLength -= gaps[i];
    }
    
    cout << totalLength << endl;
    
    return 0;
}

Complexity Analysis

Sorting occupied stall positions: O(C log C)
Sorting gaps: O(C log C)
Overall: O(C log C) time, O(C) space