Se consideră N intervale [Ai,Bi], 1 ≤ i ≤ N disjuncte.

Tuturor intervalelor li se aplică o operație de extindere la ambele capete cu o valoare naturală x, astfel încât după extindere cu valoarea x, intervalul [Ai,Bi] va deveni intervalul [Ai-x,Bi+x], 1 ≤ i ≤ N.

După extindere, spunem că intervalele [Ai,Bi] și [Aj,Bj] aparțin aceluiași grup de intervale dacă ele se intersectează sau dacă există un interval [Ak,Bk] astfel încât [Ai,Bi] se intersectează cu [Ak,Bk] iar intervalele [Ak,Bk], [Aj,Bj] aparțin aceluiași grup de intervale.

Cerința

Să se determine valoarea minimă x cu care vor trebui să fie extinse toate intervalele astfel încât să se formeze un grup cu cel puțin P intervale.

Date de intrare

Fișierul de intrare intervale3.in conține pe prima linie numerele naturale N și P cu semnificația din enunț. Pe următoarele N linii sunt descrise cele N intervale, câte un interval pe linie. Pentru fiecare interval i sunt specificate capetele sale Ai şi Bi.

Date de ieșire

Fișierul de ieșire intervale3.out va conţine pe prima linie numărul natural x ce reprezintă valoarea minimă cu care vor trebui extinse intervalele astfel încât să se obțină cel puțin un grup format din cel minimum P intervale.

Restricții și precizări

2 ≤ N ≤ 100 000
-1 400 000 000 ≤ Ai < Bi ≤ 1 400 000 000
2 ≤ P ≤ N
Două intervale se intersectează dacă au cel puţin un punct comun
Pentru 30% dintre teste N ≤ 10 000

Exemplu

intervale3.in

intervale3.out

Explicație

După extinderea cu 2 a celor 7 intervale se obțin intervalele:
[6,11]
[19,27]
[12,19]
[-1,6]
[26,34]
[33,44]
[98,202]

Se formează astfel 3 grupuri de intervale:

Grupul 1: [-1,6], [6,11]
Grupul 2: [12,19], [19,27], [26,34], [33,44]
Grupul 3: [98,202]

Grupul 2 este format din cel puțin 3 intervale.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Intervale3:

/*
    sol Eugen Nodea - cautare binara
*/
# include <cstdio>
# include <algorithm>
# define NMax 100003
using namespace std;

struct interval
{
    int a, b;
} v[NMax];
int i, N, P;
long long s, d, m;

bool cmp (interval x, interval y)
{
    if (x.a > y.a) return false;
    return true;
}
inline int intersectie(interval x, interval y, long long m)
{

    if ((x.b + m < y.a - m )|| (y.b + m < x.a - m)) return 0;
    return 1;
}
bool este (long long x)
{
    int i, nr = 1;
    for (i = 1; i<N; ++i)
    {
        if (intersectie(v[i], v[i+1], x))
        {
            ++nr;
            if (nr >= P) return true;
        }
        else nr = 1;
    }
    return false;
}
int main()
{
    freopen ("intervale3.in", "r", stdin);
    freopen ("intervale3.out", "w", stdout);

    scanf("%d %d", &N, &P);
    for (i=1; i<=N; ++i)
        scanf("%d %d", &v[i].a, &v[i].b);

    sort(v + 1, v + N + 1, cmp);

    s = 1; d = 1500000000;
    while (s <= d)
    {
        m = s + ((d - s) >> 1);
        if (este(m)) d = m - 1;
                else s = m + 1;
    }

    printf("%lld
", s);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #699 Intervale3

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #699 Intervale3 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #699 Intervale3