Birds on a Wire ⧉

The problem input provides us the length of the wire, the minimum distance between two birds, and the positions of each bird so far. All we need to do to maximize the number of additional birds on the wire is to greedily place a new bird wherever it can fit, i.e. the minimum distance from the previous bird. Although we don't need to place one bird at a time--since the minimum distance is constant, the number of birds we can fit on an empty section of the wire that spans [start,end] is (end-start)/minimum distance + 1. The tricky part is determining the start and end of each section. Once that is done, simply cram as many birds onto the wire as possible and report the total.

birds.cpp

birds.py

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
// birds can't sit any closer to the poles than this
const ll offset = 6;
int main() {
  ll n, l, d;
  cin >> l >> d >> n;
  vector<ll> birds(n);
  for (auto &b : birds)
    cin >> b;
  sort(birds.begin(), birds.end());
  if (n == 0) {
    cout << (l - 2 * offset) / d + 1 << '\n';
    return;
  }
  int totalBirds = 0;
  for (int i = 0; i <= n; i++) {
    ll start = i == 0 ? offset : birds[i - 1] + d;
    ll end = i == n ? l - offset : birds[i] - d;
    if (start <= end) {
      totalBirds += (end - start) / d + 1;
    }
  }
  cout << totalBirds << '\n';
  return 0;
}

If you found this solution helpful, consider leaving a star!