New York

Aceasta este de asemenea o problema interesanta de pe pbinfo de dificultate medie cu numarul #3738.

Doru s-a mutat în New York și își caută o nouă locuință specială în perimetrul străzilor numerotate cu numerele distincte de la 1 la n. Fiind pasionat de matematică, el vrea să se mute pe strada în care cel mai mare divizor comun (cmmdc) al înălțimilor clădirilor este maxim.

În plus, alegerea clădirii nu este una ușoară, el dorind să se mute doar într-o clădire perfectă. Numim o clădire perfectă o clădire care are cea mai mare înălțime număr prim de pe strada pe care se află.

Fiind ocupat cu împachetatul, Doru vă roagă pe voi să găsiți clădirea perfectă.

Problema are mai multe restrictii si precizari utile in dezvoltarea si implementarea algoritmului.

• Pe fiecare stradă există cel puțin o clădire.
• Dacă pe strada cu cmmdc-ul maxim sunt mai multe clădiri perfecte, se va afișa cea mai din dreapta.
• Dacă sunt mai multe străzi cu aceeași clădire perfectă, se va afișa cea care are numărul străzii cel mai mare.

Algoritmul trebuie rezolvat folosindu-se citirea datelor dintr-un fisier de intrare si tiparirea datelor de iesire intr-un fisiere de iesire.

#include <fstream>
using namespace std;
ifstream cin("nyk.in");
ofstream cout("nyk.out");
bool isPrim(int x)
{
    if (x == 2)
    {
        return true;
    }
    if (x < 2 || x % 2 == 0)
    {
        return false;
    }
    for (int d = 3; d * d <= x; d += 2)
    {
        if (x % d == 0)
        {
            return false;
        }
    }
    return true;
}
int main()
{
    int n, rand, coloana, cmmdcMax = 0, inaltimeMax = -1;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int m, inaltime = -1, pos;
        cin >> m;
        int a;
        cin >> a;
        if (isPrim(a))
        {
            inaltime = a;
            pos = 1;
        }
        for (int j = 2; j <= m; j++)
        {
            int b;
            cin >> b;
            if (b >= inaltime && isPrim(b))
            {
                inaltime = b;
                pos = j;
            }
            while (b)
            {
                int r = a % b;
                a = b;
                b = r;
            }
        }
        if (a > cmmdcMax || (a == cmmdcMax && inaltime >= inaltimeMax))
        {
            cmmdcMax = a;
            inaltimeMax = inaltime;
            rand = i;
            coloana = pos;
        }
    }
    if (inaltimeMax == -1)
    {
        cout << "Nu am gasit casa!";
    }
    else
    {
        cout << rand << " " << coloana << '\n'
             << inaltimeMax;
    }
    return 0;
}

Dupa cum se poate vedea foarte usor din liniile de cod, algoritmul citeste datele de intrare dupa care cauta cel mai mare divizor comun intre toate cladirile de pe o anumita strada. Pe fiecare strada trebuie determinata si valoarea numar prim a tuturor inaltimilor cladirilor. Aceasta valoare trebuie memorata pentru a afisa cerintele finale.

 

O alta solutie ar putea fi aceasta:

#include<fstream>
using namespace std;

ifstream cin("nyk.in");
ofstream cout("nyk.out");

bool verifprim(int nr)
{
    if(nr < 2)
        return false;
    if(nr == 2)
        return true;
    if(nr % 2 == 0)
        return false;
    for(int d = 3; d * d <= nr; d += 2)
        if(nr % d == 0)
            return false;
    return true;
}

int main()
{
    int n, x, y;
    int blmax = -1;
    int cmmdcmax = 0;
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        int a, b, r, m, bmax = -1, cnt;
        cin>>m;
        cin>>a;
        if(bmax <= a && verifprim(a))
        {
            bmax = a;
            cnt = 1;
        }
        for(int j=1; j<m; j++)
        {
            cin>>b;
            if(bmax <= b && verifprim(b))
            {
                bmax = b;
                cnt = j + 1;
            }

            while(b != 0)
            {
                r = a % b;
                a = b;
                b = r;
            }
        }
        if(a > cmmdcmax)
        {
            cmmdcmax = a;
            blmax = bmax;
            x = cnt;
            y = i;
        }
        else if(a == cmmdcmax && blmax <= bmax)
        {
            cmmdcmax = a;
            blmax = bmax;
            x = cnt;
            y = i;
        }
    }
    if(blmax==-1)
        cout<<"Nu am gasit casa!";
    else
        cout<<y<<" "<<x<<'\n'<<blmax;
    return 0;
}

Va asteptam cu drag comentariile si codurile scrise de voi la aceasta problema!