004 Diagonale

[•reking]

Ma puteti ajuta si pe mine? 
Chiar nu inteleg ce are sursa mea ... pe toate testele iau incorect.

Cod:

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("diagonale.in");
ofstream g("diagonale.out");
int a[1001][1001],n;
int calculeaza (int x)
{
    int i,y,sum1=0,sum2=0,k=x;
    y=1;
    while (x<=n && y<=n)
    {
        sum1=sum1+a[x][y];
        x++;
        y++;
    }
    x=k;
    while (x<=n && 1<=y)
    {
        sum2=sum2+a[x][y];
        x++;
        y--;
    }
    if (sum1>sum2) return sum1;
    else return sum2;
}
int main ()
{
    int i,j,summax,sum;
    f>>n;
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            f>>a[i][j];
    summax=a[n][1];
    for (i=n;i>=1;i--)
    {
        sum=calculeaza(i);
        if (summax<sum) summax=sum;
    }
    for (i=2;i<=n-1;i++)
    {
        sum=calculeaza(i);
        if (summax<sum) summax=sum;
    }
    g<<summax<<'\n';
}

"Prin diagonala, pe langa diagonala principala si cea secundara a matricei, ne vom referi la orice set de elemente situat pe o dreapta paralela cu una dintre acestea." - SET DE ELEMENTE, deci o diagonala are cel putin 2 elemente, nu???

[•klamathix]

Nu. Un set/o multime poate avea un singur element.

[•reking]

Mda...m-am lamurit
Mersi!

[•FearDotCom]

#include <stdio.h>
 
#define INPUT "diagonale.in"
#define OUTPUT "diagonale.out"
 
long long maxParaleleP (int n, long long a[1001][1001]){ //calculeaza suma maxima a liniilor paralele cu diagonala princpala
    int i,j,k;
    long long s,max=a[0][0];
    for (k=0; k<n-1; k++){
        s=0;
        for (i=0; i<n; i++)
            for (j=0; j<n; j++)
                if (i-j==k)
                    s=s+a[j];
        if (s>max)
            max=s;
    }
    return max;
}
 
long long maxParaleleS (int n, long long a[1001][1001]){  //calculeaza suma maxima a liniilor paralele cu diagonala secundara
    int i,j,k;
    int s,max=max=a[0][0];
    for (k=(n-1)*2; 0<k; k--){
        s=0;
        for (i=0; i<n; i++)
            for (j=0; j<n; j++)
                if (i+j==k)
                    s=s+a[j];
        if (s>max)
            max=s;
    }
    return max;
}
 
int main(){
    int n;
    long long a[1001][1001];
 
    freopen(INPUT,"r",stdin);
    freopen(OUTPUT,"w",stdout);
    scanf("%d",&n);
 
 
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            scanf("%lld",&a[j]);
 
    if (maxParaleleP(n,a) > maxParaleleS(n,a))
        printf("%lld",maxParaleleP(n,a));
    else
        printf("%lld",maxParaleleS(n,a));
    return 0;
}

de ce imi da stack overflow ? si cu [1000][1000] merge ? cum se face ca depasesc memoria si timpul si celelalte surse de le`am vazut nu depasesc ?

[•FearDotCom]

am rezolvat cu stack overflow dar memoria si timpul trece cu mult peste

[•PlayLikeNeverB4]

Algoritmul tau e O(N^3) fiindca gasesti prea ineficient diagonalele. Poate te ajuta articolul cu solutii: http://www.infoarena.ro/monthly-2012/runda-2/solutii.

[•FearDotCom]

#include <stdio.h>

#define INPUT "diagonale.in"
#define OUTPUT "diagonale.out"


int main(){
   int n,i,j;
   long long x;
   long long dp[2000], ds[2000];
   long long maxp,maxs;

   freopen(INPUT,"r",stdin);
   freopen(OUTPUT,"w",stdout);
   
   scanf("%d",&n);

   for (i=0; i<2*n-1; i++){
      dp=0;
      ds=0;
   }

   for (i=0; i<n; i++)
      for (j=0; j<n; j++){
         scanf("%lld",&x);
         dp[n+i-j]=dp[n+i-j]+x;
         ds[i+j]=ds[i+j]+x;
      }

      maxp=-1000000000;
      maxs=-1000000000;

   for (i=0; i<2*n-1; i++){
      if (dp>maxp)
         maxp=dp;
      if (ds>maxs)
         maxs=ds;
   }

   if (maxp>maxs)
      printf("%lld",maxp);
   else
      printf("%lld",maxs);

}


cum de iau incorect la ultimul test?

[•PlayLikeNeverB4]

Gresesti la indici. Vezi ca in articol se lucreaza cu 1..n iar tu lucrezi cu 0..n-1. Si daca mai postezi cod, foloseste tagul code.

[•FearDotCom]

imi cer scuze sunt nou pe site, dar nu vad care este problema cu indicii ca ii notez eu 0 n-1 ca ii notez 1 n pana la urma suma de pe diagonale tot aia e nu ?

[•romyk]

initializeaza  maxp si maxs cu 12 zerouri, adica -1000000000000

[•PlayLikeNeverB4]

Nu e nevoie de -10^12, deoarece maximul va fi tot timpul cel putin -10^9.

Suma tot aceeasi e, dar trebuie sa iti adaptezi formulele. Daca ai indicii 0..n-1 atunci 0 <= i+j <= 2*n-2 si 1 <= n+i-j <= 2*n-1. Deci probabil trebuie sa pui doar un -1.

[•FearDotCom]

Cod:

#include <stdio.h>
 
#define INPUT "diagonale.in"
#define OUTPUT "diagonale.out"
 
 
int main(){
    int n,i,j;
    long long x;
    long long dp[2000], ds[2000];
    long long maxp,maxs;
 
    freopen(INPUT,"r",stdin);
    freopen(OUTPUT,"w",stdout);
     
    scanf("%d",&n);
 
    for (i=1; i<=2*n-1; i++){
        dp[i]=0;
        ds[i]=0;
    }
 
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++){
            scanf("%lld",&x);
            dp[n+i-j]=dp[n+i-j]+x;
            ds[i+j]=ds[i+j]+x;
        }
 
        maxp=-1000000000;
        maxs=-1000000000;
 
    for (i=1; i<=2*n-1; i++){
        if (dp[i]>maxp)
            maxp=dp[i];
        if (ds[i]>maxs)
            maxs=ds[i];
    }
 
    if (maxp>maxs) 
        printf("%lld",maxp);
    else
        printf("%lld",maxs);
 
}

am incercat si cu indicii si tot nu ia ultimu test  

[•FearDotCom]

La indici era problema, am rezolvat, multumesc frumos !

[•mitza23]

Poate pune cineva, va rog, niste fisiere de test?