004 Diagonale

[•wefgef]

Aici puteţi discuta despre problema Diagonale.

[•Dianna22]

unde pot gasi solutia?   multumesc

[•wefgef]

Calculezi suma pe fiecare diagonala si afisezi maximul? Ai grija cum initializezi variabila in care retii maximul pentru ca e posibil ca raspunsul sa fie negativ. Deasemnea, ai grija sa folosesti variabile pe 64 de biti (long long).

[•laurion]

Diana, se vor posta solutiile de la concurs aici, desi nu era problema de idee, ci doar trebuia sa parcurgi matricea si sa tii maximul pentru fiecare diagonala (eu am facut separat pentru cele || cu cea principala si pentru cele || cu cea secundara). Pentru fiecare element, aduni ce e in stanga sus pentru diagonalele asa "\" si ce e in dreapta sus pentru diagonalele asa "/". Ai grija sa lucrezi pe long long 

[•luci94]

Cum puteai face sa se incadreze in 1000 de linii si coloane + variabile longint daca rezolvai in pascal ? Pt ca imi aparea stack overflow daca puneam valori asa mari. Inca un lucru : m-am uitat si in regulament si n-am gasit de unde vin defapt punctele de penalizare:)

[•klamathix]

http://infoarena.ro/monthly-2012/format

[•laurion]

Cum puteai face sa se incadreze in 1000 de linii si coloane + variabile longint daca rezolvai in pascal ? Pt ca imi aparea stack overflow daca puneam valori asa mari. Inca un lucru : m-am uitat si in regulament si n-am gasit de unde vin defapt punctele de penalizare:)

Nu-s bun la Pascal (personal te sfatuiesc sa treci mai departe) dar daca primesti stack overflow si crezi ca e de la declararea matricei (apropo, matricea din input poate fi int) atunci probabil ca declari in interiorul functiei, declara global 

[•tzipleatud]

Nu ai nevoie de matrice, poti citi cu doar o variabila pe care o aduni la suma corespunzatoare diagonalei pe care se afla. (aceste sume le retii in 2 vectori). Bafta!

[•idomiralin]

Am avut grija la cazuri, am initializat variabilele cu long long, am initializat maximul cu - 10^9 si nu stiu unde gresesc, pentru ca iau incorrect la ultimul test. Poate ma poate ajuta cineva.

[•andunhill]

@Idomir: Pai vezi ca nu e bine  . Ai pe o diagonala maxim N elemente care sunt in  modul mai mici decat 10^9; Cand faci suma lor  obtii un maxim de 1000 * 10^9. Deci initializeaza maximul cu -2^63 .

[•tzipleatud]

@Idomir: Pai vezi ca nu e bine  . Ai pe o diagonala maxim N elemente care sunt in  modul mai mici decat 10^9; Cand faci suma lor  obtii un maxim de 1000 * 10^9. Deci initializeaza maximul cu -2^63 .

Nu e neaparat ca asta sa fie problema deoarece elementele din colturi sunt mai mari decat -10^9. Eu am luat 100 chiar si cu maximul initializat cu -9.99999999*10^8.

[•andunhill]

@Tiplea: Eu luam 0 cand initializam cu 10^9. Cand am schimbat cu 2^63 am luat 100 

[•darkseeker]

Eu am initializat cu -7-10^9 si am luat 100.

[•noobakaflo]

^^Cum faceti  initializarile cu valorile astea mari ? 2^63 ?Vad ca nu intra in long double,are mai mult de 18 cifre..

[•PlayLikeNeverB4]

E bun orice numar mai mic sau egal cu -N * 10⁹.

[•laurion]

^^Cum faceti  initializarile cu valorile astea mari ? 2^63 ?Vad ca nu intra in long double,are mai mult de 18 cifre..

Trebuie sa folosesti long long, nu double... este pe 64 de biti deci maximul este 2^63 - 1 (ultimul bit este pentru semn, daca nu folosesti unsigned long long). De asemenea, ai grija cand initializezi, sa folosesti 1LL, nu doar 1 (constantele by default sunt int).

[•wefgef]

Puteti sa initializati maximul cu A[1][1]

[•marius23]

Imi da incorect pe ultimul test ](*,)Stie cnv care ar putea fi problema ?

[•gabitzish1]

S-ar putea sa nu iei in considerare suma maxima negativa, sau sa nu initializezi maximul cu o valoare corecta.

[•marius23]

Am initializat si cu -2^63 si -10^9 si am obtinut acelas rezultat.La ce te referi prin suma maxima negativa ? 

[•PlayLikeNeverB4]

Adica toata matricea e formata din numere negative.

Ok, m-am uitat la sursa ta. Noi cand scriem 10^9 sau 2^63 ne referim la operatia de ridicare la putere, pe cand daca tu scrii aia intr-un program C, el va face operatia XOR pe biti. Deci in loc sa scrii -10^9 poti scrie explicit -1000000000.

[•marius23]

Multumesc.Am luat 100 acum.

[•Andrei.Xwe]

Eu pic vreo 4 teste din cauza ca e gresit, dar eu am verificat si programul imi calculeaza corect sumele.Ma puteti ajuta?

Cod:

#include<fstream>
using namespace std;
#include<values.h>
long long a[1001][1001];
int main()
{
	ifstream fcin("diagonale.in");
	ofstream fcout("diagonale.out");
	int i,j,n;
	long long s,max=-LONG_LONG_MAX;
	fcin>>n;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			fcin>>a[i][j];
	//diagonala principala
	s=0;
	for(i=1;i<=n;i++)
		s+=a[i][i];
	if(s>max)
		max=s;
	//parelelele de deasupra diagonalei principale
	for(i=2;i<=n;i++)
	{
		s=0;
		for(j=i;j<=n;j++)
			s+=a[j-i+1][j];
		if(s>max)
			max=s;
	}
	//parelelele de dedesubtul diagonalei principale
	for(i=2;i<=n;i++)
	{
		s=0;
		for(j=2;j<=n;j++)
			s+=a[j][j-i+1];
		if(s>max)
			max=s;
	}
	//diagonala secundara
	s=0;
	for(i=1;i<=n;i++)
		s+=a[i][n-i+1];
	if(s>max)
		max=s;
	//parelelele de deasupra diagonalei secundare
	for(i=1;i<n;i++)
	{
		s=0;
		for(j=1;j<=i;j++)
			s+=a[j][i-j+1];
		if(s>max)
			max=s;
	}
	//paralelele de deasubtul diagonalei secundare
	for(i=2;i<=n;i++)
	{
		s=0;
		for(j=i;j<=n;j++)
			s+=a[j][n-j+i];
		if(s>max)
			max=s;
	}
	fcout<<max;
	return 0;
}

[•PlayLikeNeverB4]

Nu cred ca e bine la "parelelele de dedesubtul diagonalei principale".

[•Andrei.Xwe]

Da, acolo era problema, si bineinteles, "greaseala de tipar"  (pusesem intr-un for j=2 in loc de j=i...i care la inceput avea valoarea 2 si probabil de aia). Oricum, multumesc pentru ajutor.