Bình luận

• 
  

  0

  

  nug9977  đã bình luận lúc 9, Tháng 10, 2025, 11:28

  N bắt đầu từ 0 hay 1 vậy ạ?

• 
  

  -1

  

  username001  đã bình luận lúc 8, Tháng 10, 2025, 6:42

  Hướng dẫn giải

  include <bits/stdc++.h>

  using namespace std;

  int main() { ios::syncwithstdio(false); cin.tie(nullptr);

  int N, K, R;
  if (!(cin >> N >> K >> R)) return 0;
  vector<int> pos(K);
  for (int i = 0; i < K; ++i) cin >> pos[i];
  
  vector<char> covered(N + 1, 0);               // index 1 … N
  
  // mark intervals of the already existing lamps
  for (int p : pos) {
      int L = max(1, p - R);
      int H = min(N, p + R);
      for (int x = L; x <= H; ++x) covered[x] = 1;
  }
  
  int answer = 0;
  int i = 1;
  while (i <= N) {
      if (covered[i]) {               // already bright
          ++i;
          continue;
      }
  
      // first dark point = i
      int lampPos = min(i + R, N);    // farthest place that still lights i
      int L = max(1, lampPos - R);
      int H = min(N, lampPos + R);
      for (int x = L; x <= H; ++x) covered[x] = 1;
  
      ++answer;
      i = H + 1;                      // everything up to H is now lit
  }
  
  cout << answer << '\n';
  return 0;
  

  }