Problema Numere
4Mircea 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; }
RaÈ›ionamentul gasit de tine este bun, insa apar cateva hibe. Avand in vedere ca problema a fost gandita pentru borland (unde nu exista long long, iar cel mai mare numar care poate fi reÈ›inut este 2^32 = 2 miliarde si un pic), este foarte posibil ca suma ta sa nu se incadreze in limite. Și in al doilea rand evita sa folosesti constante/variabile cu numele min sau max, pentru ca in clasa algorithm sunt deja definite, si daca se „intersecteaza” iese urat 😀
Legat de min si max o sa le pun de-acum Min si Max, ca sa nu existe probleme.
Ce urat e Borland-ul. 😐
Vezi ca nu se observa headerele incluse de tine. Foloeste pentru tagurile <> < respectiv >
Done. 😉