Cod sursa(job #3196824)

Utilizator valentin50517Vozian Valentin valentin50517 Data 24 ianuarie 2024 20:38:14
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>

using namespace std;

int N, M;

int ramura(int x) {
    long long l = 1, r = 1e9;
    while (r - l >= 5) {
        long long m = (l + r) / 2;
        if (m * (m + 1) < x) {
            l = m + 1;
        } else {
            r = m;
        }
    }

    for (long long i = l; i <= r; i++) {
        if (i * (i + 1) >= x) {
            return i;
        }
    }
}

void rezolvaN(int N) {
    int r = ramura(N);

    int mijloc_jos = r * (r + 1);
    int mijloc = mijloc_jos - r;

    cout << r << ' ';

    if (N == mijloc_jos || N == mijloc) {
        cout << "centru" << '\n';
    } else if (N < mijloc) {
        cout << "stang" << '\n';
    } else {
        cout << "drept" << '\n';
    }
}

bool prim(int x) {
    if (x < 2) {
        return false;
    }
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

void rezolvaM(int M) {
    int r = ramura(M);
    int mijloc_jos = r * (r + 1);
    int dreapta = mijloc_jos - 1;
    int stanga = mijloc_jos - 2 * r + 1;
    int raspuns = 0;

    for (int i = stanga; i <= dreapta; i++) {
        if (prim(i)) {
            raspuns++;
        }
    }

    cout << raspuns << '\n';
}

int main() {
    cin >> N >> M;
    rezolvaN(N);
    rezolvaM(M);

    return 0;
}