Cerința

După dezastrul cauzat de hackerul Gigel ( #Suprasolicitare ), administratorul rețelei s-a decis să ia măsuri.

Acesta este responsabil de o rețea cu n*n calculatoare dispuse sub forma unei matrice cu n linii și n coloane, în care fiecare calculator este conectat la calculatoarele adiacente(sus, dreapta, stânga, jos), fiecare calculator de pe rândul n este conectat la calculatorul de pe rândul 1 și aceeași coloană, și fiecare calculator de pe de pe coloana n este conectat la cel de pe coloana 1 și aceeași linie.

În această rețea, există calculatoare criptate, care nu pot primi pachete de date corupte. Calculatoarele necriptate pot primi pachete corupte dar nu le pot prelucra. Comportamentul lor este unul aparte: când un calculator necriptat primește un pachet de date, îl transmite mai departe la următorul calculator pe aceeași direcție până întâlnesc un calculator criptat. Calculatorul care conține pachetul de date corupt poate primi apoi o comandă prin care să îl transmită mai departe în altă direcție.

Rețeaua devine suprasolicitată dacă pachetul corupt ajunge pe o linie sau coloană care conține numai calculatoare necriptate, putându-se astfel să se transmită la infinit.

Hackerul Gigel a profitat de această slăbiciune a rețelei și a reușit dea comenzi prin terminalele calculatoarelor astfel încât pachetul de date să se transmită la infinit între ele, suprasolicitând rețeaua, (vezi problema #Suprasolicitare ).

Administratorul rețelei a decis să cripteze suficiente calculatoare pentru a evita orice posibilitate de suprasolicitare a rețelei. Deoarece criptarea unui singur calculator ia mult timp, administratorul dorește să afle numărul minim de calculatoare care trebuie criptate astfel încât hackerul Gigel să nu se mai poată distra cu rețeaua.

Date de intrare

Fișierul de intrare criptare.in conține pe prima linie numărul n, urmat de n rânduri cu n numere. Valoarea 1 reprezentă un calculator deja criptat, iar valoarea 0 un calculator necriptat.

Date de ieșire

Fișierul de ieșire criptare.out va conține pe prima linie numărul Sol, reprezentând numărul minim de calculatoare ce necesită a fi criptate, iar pe următoarele Sol rânduri o pereche de numere x și y reprezentând că pe linia x și coloana y calculatorul trebuie criptat.

Restricții și precizări

1 ≤ n ≤ 1000
Orice soluție cu număr minim de calculatoare criptate este corectă.
Pentru afișarea doar a lui Sol, se acordă 20% din punctaj.
Pentru teste în valoare de 40 de puncte, n ≤ 10.

Exemplu

criptare.in

criptare.out

2
1 1
5 3

Explicație

După criptarea calculatoarelor (1,1) și (5,3), hackerul Gigel nu mai poate trimite pachetul la infinit pe linia 1, respectiv linia 5

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

#include <fstream>
using namespace std;

ifstream fin ("criptare.in");
ofstream fout ("criptare.out");

const int N = 1005;

int h[N], v[N], n, solx, soly;

int main() {
    fin >> n;
    for (int i = 1; i <= n; ++i)
        for (int x, j = 1; j <= n; ++j) {
            fin >> x;
            h[i] |= x;
            v[j] |= x;
        }
    for (int i = 1; i <= n; ++i) {
        solx += h[i];
        soly += v[i];
    }
    fout << n - min(solx, soly) << "\n";
    int i = 1, j = 1;
    while (i <= n && j <= n) {
        while (h[i] && i <= n)
            i++;
        while (v[j] && j <= n)
            j++;
        if (i <= n && j <= n) {
            fout << i << " " << j << "\n";
            i++, j++;
        }
    }
    while (i <= n) {
        while (h[i] && i <= n)
            i++;
        if (i <= n) {
            fout << i << " 1\n";
            i++;
        }
    }
    while (j <= n) {
        while (v[j] && j <= n)
            j++;
        if (j <= n) {
            fout << "1 " << j << "\n";
            j++;
        }
    }

}

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 #961 Criptare

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