Problema Numere

Mircea este pasionat de programare. El a inceput sa rezolve probleme din ce in ce mai grele. Astfel a ajuns la o problema, care are ca date de intrare un tablou patratic cu n linii si n coloane, componente tabloului fiind toate numerele naturale distincte de la 1 la n2.

Pentru a verifica programul pe care l-a scris ii trebuie un fisier care sa contina tabloul respectiv. Dupa ce a creat acest fisier, fratele sau, pus pe sotii ii umbla in fisier si ii schimba cateva numere consecutive, cu numarul 0. Cand se intoarce Mircea de la joaca constata cu stupoare ca nu ii merge programul pentru testul respectiv. Dupa cateva ore de depanare isi da seama ca programul lui este corect si ca fisierul de intrare are probleme.

Cerinta

Scrieti un program care sa-l ajute pe Mircea, gasindu-i cel mai mic si cel mai mare dintre numerele consecutive schimbate de fratele sau.

Date de intrare

In fisierul de intrare numere.in se da pe prima linie valoarea n, iar pe urmatoarele n linii elementele tabloului, cate n elemente pe o linie, separate intre ele prin cate un spatiu, dupa modificarile facute de fratele lui Mircea.

Date de iesire

In fisierul de iesire numere.out se va scrie pe un singur rand cu un singur spatiu intre ele numerele cerute (primul fiind cel mai mic).

Restrictii

• 0<n<=500
• Fratele lui Mircea schimba cel putin un numar in fisier.

• Numerele schimbate de fratele lui Mircea sunt mai mici sau cel mult egale cu 60000.

Solutie

Contrar asteptarilor, nu vom retine numerele intr-o matrice, le vom citi cu ajutorul variabilelor. Putem rezolva aceasta problema calculand suma numerelor „prezente” si numarul de numere „absente” (cele care lipsesc si au fost inlocuite cu 0). Vom calcula si suma totala a numerelor de la 1 la n*n, apoi ne vom baza pe niste observatii.

Notam:

suma  =  suma numerelor de la 1 la n*n

sumb = suma numerelor prezente

a = suma – sumb

b = numarul de numere absente

Si vom aveam urmatoarea relatie: x=(a-(b*b+b)/2)/b

Vom afisa x+1 ” ” si x+b .

#include  <iostream>
#include <fstream>
using namespace std;

#define max 500001

int main()
{
ifstream f("numere.in");
ofstream g("numere.out");
long long i,N,aux,auxi,suma=0,sumb=0,a,b=0,x;
f>>N;
aux=N*N;
if (aux>max) aux=max;
for(i=1;i<=aux;i++)
{
       suma+=i;
       f>>auxi;
       if (auxi) sumb+=auxi;
           else  b++;
}
a=suma-sumb;
x=(a-(b*b+b)/2)/b;
g<<<" "<
f.close();
g.close();
return 0;
}