Stretching every streetlight equally

import sys data = sys.stdin.read().split()n, length, k = int(data[0]), int(data[1]), int(data[2])lamps = []  # (p - r, p + r): 늘이기 전에 비추는 구간for i in range(n):    p, r = int(data[3 + 2 * i]), int(data[4 + 2 * i])    lamps.append((p - r, p + r))lamps.sort()  # 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다  def lamps_needed_ok(t):    """모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가."""    need = 0  # 아직 비춘다고 확인하지 못한 가장 왼쪽 점    i = 0    best = -1  # 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝    used = 0    while used < k:        while i < n and lamps[i][0] - t <= need:  # 끝이 닿기만 해도 이어진다(닫힌 구간)            best = max(best, lamps[i][1] + t)            i += 1        if best < need:  # need를 비추는 등이 없다            return False        used += 1        if best >= length:            return True        if best == need:  # 더 나아갈 수 없다            return False        need = best    return False  lo, hi = 0, length  # t = length이면 어느 등 하나로도 [0, length]를 다 비춘다while lo < hi:    mid = (lo + hi) // 2    if lamps_needed_ok(mid):        hi = mid    else:        lo = mid + 1print(lo)

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, length, k] = data;const lamps = []; // [p - r, p + r]: 늘이기 전에 비추는 구간for (let i = 0; i < n; i++) {  const p = data[3 + 2 * i], r = data[4 + 2 * i];  lamps.push([p - r, p + r]);}lamps.sort((x, y) => x[0] - y[0]); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가function canCover(t) {  let need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점  let i = 0;  let best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝  for (let used = 1; used <= k; used++) {    while (i < n && lamps[i][0] - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간)      best = Math.max(best, lamps[i][1] + t);      i++;    }    if (best < need) return false; // need를 비추는 등이 없다    if (best >= length) return true;    if (best === need) return false; // 더 나아갈 수 없다    need = best;  }  return false;} let lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다while (lo < hi) {  const mid = Math.floor((lo + hi) / 2);  if (canCover(mid)) hi = mid;  else lo = mid + 1;}console.log(lo);

import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, length, k] = data;const lamps: [left: number, right: number][] = []; // 늘이기 전에 비추는 구간 [p - r, p + r]for (let i = 0; i < n; i++) {  const p = data[3 + 2 * i], r = data[4 + 2 * i];  lamps.push([p - r, p + r]);}lamps.sort((x, y) => x[0] - y[0]); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가function canCover(t: number): boolean {  let need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점  let i = 0;  let best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝  for (let used = 1; used <= k; used++) {    while (i < n && lamps[i][0] - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간)      best = Math.max(best, lamps[i][1] + t);      i++;    }    if (best < need) return false; // need를 비추는 등이 없다    if (best >= length) return true;    if (best === need) return false; // 더 나아갈 수 없다    need = best;  }  return false;} let lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다while (lo < hi) {  const mid: number = Math.floor((lo + hi) / 2);  if (canCover(mid)) hi = mid;  else lo = mid + 1;}console.log(lo);

import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer; public class Main {    static int n, k;    static long length;    static long[][] lamps; // {p - r, p + r}: 늘이기 전에 비추는 구간. p + r + t는 30억까지라 long     // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가    static boolean canCover(long t) {        long need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점        int i = 0;        long best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝        for (int used = 1; used <= k; used++) {            while (i < n && lamps[i][0] - t <= need) { // 끝이 닿기만 해도 이어진다(닫힌 구간)                best = Math.max(best, lamps[i][1] + t);                i++;            }            if (best < need) return false; // need를 비추는 등이 없다            if (best >= length) return true;            if (best == need) return false; // 더 나아갈 수 없다            need = best;        }        return false;    }     public static void main(String[] args) throws IOException {        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));        StringTokenizer st = new StringTokenizer(in.readLine());        n = Integer.parseInt(st.nextToken());        length = Long.parseLong(st.nextToken());        k = Integer.parseInt(st.nextToken());        lamps = new long[n][];        for (int i = 0; i < n; i++) {            st = new StringTokenizer(in.readLine());            long p = Long.parseLong(st.nextToken());            long r = Long.parseLong(st.nextToken());            lamps[i] = new long[] {p - r, p + r};        }        // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다        Arrays.sort(lamps, (x, y) -> Long.compare(x[0], y[0]));         long lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다        while (lo < hi) {            long mid = (lo + hi) / 2;            if (canCover(mid)) hi = mid;            else lo = mid + 1;        }        System.out.println(lo);    }}

using System; class Program{    static int n, k;    static long length;    static (long left, long right)[] lamps; // 늘이기 전에 비추는 구간 [p - r, p + r]. p + r + t는 30억까지라 long     // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가    static bool CanCover(long t)    {        long need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점        int i = 0;        long best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝        for (int used = 1; used <= k; used++)        {            while (i < n && lamps[i].left - t <= need) // 끝이 닿기만 해도 이어진다(닫힌 구간)            {                best = Math.Max(best, lamps[i].right + t);                i++;            }            if (best < need) return false; // need를 비추는 등이 없다            if (best >= length) return true;            if (best == need) return false; // 더 나아갈 수 없다            need = best;        }        return false;    }     static void Main()    {        string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);        n = int.Parse(first[0]);        length = long.Parse(first[1]);        k = int.Parse(first[2]);        lamps = new (long left, long right)[n];        for (int i = 0; i < n; i++)        {            string[] w = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);            long p = long.Parse(w[0]), r = long.Parse(w[1]);            lamps[i] = (p - r, p + r);        }        // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다        Array.Sort(lamps, (x, y) => x.left.CompareTo(y.left));         long lo = 0, hi = length; // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다        while (lo < hi)        {            long mid = (lo + hi) / 2;            if (CanCover(mid)) hi = mid;            else lo = mid + 1;        }        Console.WriteLine(lo);    }}

#include <algorithm>#include <iostream>#include <utility>#include <vector> int n, k;long long length;std::vector<std::pair<long long, long long>> lamps;  // (p - r, p + r): 늘이기 전에 비추는 구간. p + r + t는 30억까지라 long long // 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있는가bool canCover(long long t) {    long long need = 0;  // 아직 비춘다고 확인하지 못한 가장 왼쪽 점    int i = 0;    long long best = -1;  // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝    for (int used = 1; used <= k; used++) {        while (i < n && lamps[i].first - t <= need) {  // 끝이 닿기만 해도 이어진다(닫힌 구간)            best = std::max(best, lamps[i].second + t);            i++;        }        if (best < need) return false;  // need를 비추는 등이 없다        if (best >= length) return true;        if (best == need) return false;  // 더 나아갈 수 없다        need = best;    }    return false;} int main() {    std::ios::sync_with_stdio(false);    std::cin.tie(nullptr);    std::cin >> n >> length >> k;    lamps.resize(n);    for (auto& lamp : lamps) {        long long p, r;        std::cin >> p >> r;        lamp = {p - r, p + r};    }    std::sort(lamps.begin(), lamps.end());  // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다     long long lo = 0, hi = length;  // t = length이면 어느 등 하나로도 [0, length]를 다 비춘다    while (lo < hi) {        long long mid = (lo + hi) / 2;        if (canCover(mid)) hi = mid;        else lo = mid + 1;    }    std::cout << lo << '\n';    return 0;}

#include <stdio.h>#include <stdlib.h> #define MAXN 10000 typedef struct {    long long left, right; /* 늘이기 전에 비추는 구간 [p - r, p + r]. p + r + t는 30억까지라 long long */} Lamp; static Lamp lamps[MAXN];static int n, k;static long long length; static int byLeft(const void* a, const void* b) {    long long x = ((const Lamp*)a)->left, y = ((const Lamp*)b)->left;    return (x > y) - (x < y); /* x - y를 int로 돌려주면 넘칠 수 있다 */} /* 모든 등을 t만큼 늘였을 때 k개 이하로 [0, length]를 다 비출 수 있으면 1 */static int canCover(long long t) {    long long need = 0; /* 아직 비춘다고 확인하지 못한 가장 왼쪽 점 */    long long best = -1; /* 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝 */    int i = 0;    for (int used = 1; used <= k; used++) {        while (i < n && lamps[i].left - t <= need) { /* 끝이 닿기만 해도 이어진다(닫힌 구간) */            if (lamps[i].right + t > best) best = lamps[i].right + t;            i++;        }        if (best < need) return 0; /* need를 비추는 등이 없다 */        if (best >= length) return 1;        if (best == need) return 0; /* 더 나아갈 수 없다 */        need = best;    }    return 0;} int main(void) {    if (scanf("%d %lld %d", &n, &length, &k) != 3) return 0;    for (int i = 0; i < n; i++) {        long long p, r;        scanf("%lld %lld", &p, &r);        lamps[i].left = p - r;        lamps[i].right = p + r;    }    qsort(lamps, n, sizeof lamps[0], byLeft); /* 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 */     long long lo = 0, hi = length; /* t = length이면 어느 등 하나로도 [0, length]를 다 비춘다 */    while (lo < hi) {        long long mid = (lo + hi) / 2;        if (canCover(mid)) hi = mid;        else lo = mid + 1;    }    printf("%lld\n", lo);    return 0;}

// 모든 등을 t만큼 늘였을 때 k개 이하로 [0, 길이]를 다 비출 수 있는가비출수있나(lamps, 길이, k, t){    need = 0; // 아직 비춘다고 확인하지 못한 가장 왼쪽 점    i = 0;    best = -1; // 왼쪽 끝이 need 이하인 등 가운데 가장 멀리 가는 오른쪽 끝    for (used = 1; used <= k; used++)    {        while (i < lamps.Count && lamps[i][0] - t <= need)        {            best = Mathf.Max(best, lamps[i][1] + t);            i++;        }        if (best < need)        {            return false;        }        if (best >= 길이)        {            return true;        }        if (best == need)        {            return false;        }        need = best;    }    return false;} 왼쪽끝순(앞, 뒤){    return 앞[0] - 뒤[0];} 첫줄 = Console.ReadNumbers();n = 첫줄[0];길이 = 첫줄[1];k = 첫줄[2];lamps = []; // [p - r, p + r]: 늘이기 전에 비추는 구간for (j = 0; j < n; j++){    등 = Console.ReadNumbers();    lamps.Add([등[0] - 등[1], 등[0] + 등[1]]);}lamps.Sort(왼쪽끝순); // 모두 같은 t만큼 늘어나니 왼쪽 끝의 차례는 t와 상관없이 같다 lo = 0;hi = 길이; // t = 길이이면 어느 등 하나로도 [0, 길이]를 다 비춘다while (lo < hi){    mid = Mathf.Quot(lo + hi, 2);    if (비출수있나(lamps, 길이, k, mid))    {        hi = mid;    }    else    {        lo = mid + 1;    }}Console.WriteLine(lo);