Cerința

Se dau două numere n și m. Aflați care este numărul minim și numărul maxim de noduri izolate într-un graf neorientat cu n noduri și m muchii în care nu există un muchie de la un nod la el însuși și între oricare două noduri diferite există cel mult o muchie.

Date de intrare

Programul citește de la tastatură numerele n m.

Date de ieșire

Programul va afișa pe ecran numerele a și b, reprezentând numărul minim, respectiv numărul maxim de noduri izolate într-un graf neorientat cu n noduri și m muchii în care nu există un muchie de la un nod la el însuși și între oricare două noduri diferite există cel mult o muchie.

Restricții și precizări

1 ≤ n ≤ 100.000
\( 0 \leq m \leq \frac{n*(n-1)}{2} \)

Exemplu

Intrare

4 2

Ieșire

0 1

Explicație

Se poate construi un graf fără noduri izolate, cu muchiile (1,2) și (3,4). Pentru a obține un nod izolat, putem construi un graf cu muchiile (1,2) și (1,3).

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 Noduri Izolate:

#include<bits/stdc++.h>

using namespace std;

long long a, b;

int main()
{
    cin >> a >> b;
    if(b == 0)
    {
        cout << a << " " << a << '\n';
        return 0;
    }
    int sol = a;
    for(long long i = 1; i <= b; ++i)
    {
        if(sol >= 2)
            sol -= 2;
        else
            --sol;
        if(sol == 0)
            break;
    }
    cout << sol << " ";
    long long gauss = 1;
    while(gauss * (gauss-1) / 2 < b)
        ++gauss;
    cout << max(0LL, a - gauss);
    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 #2636 Noduri Izolate

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2636 Noduri Izolate 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 #2636 Noduri Izolate