Rezolvare completă PbInfo #1688 Intrus

Terminalul unui aeroport este o sală foarte mare având forma unui dreptunghi împărțit în pătrate cu latură unitară. Aici se află mai multe persoane, care trebuie să poarte la vedere un ecuson cu un cod de bare care poate fi citit în orice moment de camerele de supraveghere și decodificat de calculatoarele serviciului de protecție și pază. Într-un pătrat cu latură unitară poate să se afle doar o singură persoană la un moment dat. Sala este reprezentată printr-o matrice cu R linii și C coloane, elementele sale fiind numere naturale de cel mult 6 cifre cu valorile: 0 – pentru spațiu neocupat, respectiv numere naturale nenule, care reprezintă identificatorul (ID-ul) persoanelor. Printre aceste persoane există persoane infiltrate (intruși) care au ID-uri cu valori identice cu ale altor persoane. Dacă există două sau mai multe persoane cu același ID, acestea sunt considerate toate suspecte.

Intrușii vor să ajungă în apropierea unor VIP-uri (persoane importante), pentru a le înregistra discuțiile cu un microfon care poate înregistra sunete în interiorul unui pătrat cu latura D, în centrul căruia se află chiar el. Acest pătrat nu este cuprins neapărat integral în matricea sălii (vedeți figura alăturată)!

Prin convenție, ID-urile VIP-urilor sunt numere prime distincte. În plus, și un ID al unui VIP poate fi copiat, crescând astfel numărul suspecților. Un VIP se caracterizează printr-un nivel de importanță: cu cât ID-ul este un număr mai mare, cu atât nivelul de importanță este mai mare (este „mai importantă”).

Persoanele suspecte au asociat un „grad de periculozitate”. Acesta este cu atât mai mare cu cât numărul de VIP-uri aflate în interiorul pătratului de latură D, în centrul căruia se află suspectul, este mai mare. Dacă există doi suspecți cu același grad de periculozitate, se consideră „mai periculoasă” persoana care are în pătratul său VIP-ul cu ID-ul cel mai mare. În caz de egalitate, se consideră „mai periculoasă” persoana care este așezată pe o linie cu un indice mai mic, iar la egalitate de indici de linii, pe o coloană cu indice mai mic. Există și persoane suspecte cu gradul de periculozitate 0, dacă în interiorul pătratului în centrul căruia se plasează nu există niciun număr prim.

Cerința

1) Să se determine numărul persoanelor suspecte aflate în sala de așteptare.
2) Să se determine ID-ul și coordonatele persoanelor suspecte, (RSi -linia suspectului i, CSi -coloana suspectului i) în ordinea descrescătoare a „gradului de periculozitate”.

Date de intrare

Fișierul de intrare intrus.in conține pe prima linie valoarea p, care poate fi doar 1 sau 2. Linia a doua va conține valorile R, C și D, separate prin câte un spațiu. Pe următoarele R linii, câte C numere naturale de cel mult 6 cifre, separate prin câte un spațiu, reprezentând elementele matricei descrise în enunț.

Date de ieșire

Dacă p=1, se cere doar rezolvarea primei cerințe. În acest caz, fișierul de ieșire intrus.out va conține o singură valoare T (care poate fi și 0), reprezentând numărul persoanelor suspecte. Dacă p=2, se va rezolva numai a doua cerință. În acest caz fișierul de ieșire intrus.out va conține pe fiecare linie câte 3 numere naturale nenule: IDi (ID-ul intrusului i), Ri, Ci (linia, respectiv coloana în care se află intrusul), separate prin câte un spațiu. Dacă nu există niciun suspect, în prima linie a fișierului de ieșire intrus.out se va scrie -1.

Restricții și precizări

  • 0 < R, C ≤ 1000
  • 3 ≤ D ≤ 9, D număr impar.
  • Pentru p=2 se garantează că numărul suspecților nu depășește 10% din totalul persoanelor aflate în sală.

Exemplul 1

intrus.in

1
3 4 3
1 0 7 3
5 2 3 0
3 2 0 1

intrus.out

7

Explicație

p=1, se rezolvă doar cerința 1.
Există 2 ID-uri egale cu 2 și 3 ID-uri egale cu 3, deci avem 5 suspecți.

Exemplul 2

intrus.in

2
3 4 3
1 0 7 8
5 2 3 0
3 2 0 9

intrus.out

2 2 2
2 3 2
3 2 3
3 3 1

Explicație

p=2, se rezolvă doar cerința 2.
Persoana cu ID-ul 2, aflată pe linia 2 și coloana 2 are cel mai mare grad de periculozitate. Urmează ID-ul 2 din (3, 2), 3 din (2, 3) și 3 din (3, 1), care reprezintă o persoană suspectă, deși zona sa de latură D nu este cuprinsă în întregime în matricea sălii!

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 Intrus:

// Istvan Budai - 100 de puncte - O(N * M * D^2)
#include <iostream>
#include <fstream>
using namespace std;

const int Rmax=1001;
const int Cmax=1001;

ifstream f("intrus.in");
ofstream g("intrus.out");
int X[Rmax][Cmax];
int W[1000001];
typedef struct elem{int r; int c; int niv; int maxpri;};
int pt=0;
elem Y[Rmax*Cmax+1], Temp;

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

int nivel(int M[][Cmax], int is, int js, int r, int c, int d, int &mx)
{
    int i1, j1, i2, j2, v=0, ii, jj, ns=0;
    if (is-d/2>=1) i1=is-d/2; else i1=1;
    if (js-d/2>=1) j1=js-d/2; else j1=1;
    if (is+d/2<=r) i2=is+d/2; else i2=r;
    if (js+d/2<=c) j2=js+d/2; else j2=c;
    mx=0;
    for (ii=i1; ii<=i2; ii++)
       {
        for (jj=j1; jj<=j2; jj++)
        {
            if (prim(M[ii][jj]) && (ii!=is || jj!=js))
            {
                ns++;
                if (M[ii][jj]>mx) mx=M[ii][jj];
            }
        }
       }
    return ns;
}

void seek(int M[][Cmax], int nr, int ii, int jj, int &i0, int &j0)
{
    for (int ir=1; ir<=ii; ir++)
        for (int ic=1; ic<=jj; ic++)
            if (M[ir][ic]==nr)
    {
        i0=ir;
        j0=ic;
        return;
    }
}

int main()
{
    //cout << "i_n_t_r_u_s" << endl;
    //cout<<"Rmax="<<Rmax<<" "<<"Cmax="<<Cmax<<endl;
    int p, R, C, D, S=0, t, i0, j0, si, oi;
    f>>p; //cout<<"p="<<p<<endl;
    f>>R>>C>>D;
    //cout<<"R="<<R<<" "<<"C="<<C<<" D="<<D<<endl;
    if (p==2)
    {
    for (si=1; si<=R; si++) for (oi=1; oi<=C; oi++) f>>X[si][oi];
    for (si=1; si<=R; si++)
        for (oi=1; oi<=C; oi++)
        {//cout<<si<<" "<<oi<<endl;
            if (X[si][oi]!=0)
            {
                W[X[si][oi]]=W[X[si][oi]]+1;
                t=W[X[si][oi]];
                if (t>=2)
                {
                    if (t==2)
                    {
                        seek(X, X[si][oi], R, C, i0, j0);
                        pt++;
                        Y[pt].r=i0; Y[pt].c=j0;
                        Y[pt].niv=nivel(X, i0, j0, R, C, D, Y[pt].maxpri);
                        pt++;
                        Y[pt].r=si; Y[pt].c=oi;
                        Y[pt].niv=nivel(X, si, oi, R, C, D, Y[pt].maxpri);
                    }
                    else
                    {
                        pt++;
                        Y[pt].r=si; Y[pt].c=oi;
                        Y[pt].niv=nivel(X, si, oi, R, C, D, Y[pt].maxpri);
                    }
                }
            }
        }
    for (si=1; si<pt; si++)
       for (oi=si+1; oi<=pt; oi++)
            if (Y[si].niv<=Y[oi].niv)
                {
                    if (Y[si].niv==Y[oi].niv)
                    {
                        if(Y[si].maxpri<=Y[oi].maxpri)
                        {
                            if (Y[si].maxpri<Y[oi].maxpri)
                            {
                                Temp=Y[si];
                                Y[si]=Y[oi];
                                Y[oi]=Temp;
                            }
                            else
                            if (Y[si].r>=Y[oi].r)
                            {
                                if (Y[si].r>Y[oi].r)
                                {
                                    Temp=Y[si];
                                    Y[si]=Y[oi];
                                    Y[oi]=Temp;
                                }
                                else
                                if (Y[si].c>Y[oi].c)
                                {
                                    Temp=Y[si];
                                    Y[si]=Y[oi];
                                    Y[oi]=Temp;
                                }
                            }
                        }

                    }
                    else
                    {
                        Temp=Y[si];
                        Y[si]=Y[oi];
                        Y[oi]=Temp;
                    }
                }
    if (pt>0) for (si=1; si<=pt; si++)
                    g<<X[Y[si].r][Y[si].c]<<" "<<Y[si].r<<" "<<Y[si].c<<endl;
    else g<<-1;
    }
    else//p==1
    {
        int mm=0;
        for (int i=1; i<=R; i++)
        for (int j=1; j<=C; j++)
        {
            f>>X[i][j];
            if (X[i][j]) {++W[X[i][j]]; if (X[i][j]>mm) mm=X[i][j];}
        }
        for (int i=1; i<=mm; i++) if (W[i]>1) S=S+W[i];
        g<<S;
    }
    f.close(); g.close();
    //cout<<"Total memory: "<<(sizeof(X)+sizeof(Y)+sizeof(W))/1024<<" KB.";
    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 #1688 Intrus

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1688 Intrus 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!