#include<stdio.h>
int main()
{
int l,n,i,t,j,k;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&t);
int a[t][t];
int sum[t];
for(j=0;j<t;j++)
{
for(k=0;k<j+1;k++)
{
scanf("%d",&a[j][k]);
}
}
for(k=0;k<t;k++)
{
sum[k]=0;
}
int g=1;
for(k=0;k<t;k++)
{
j=t-g;
for(l=t-1;l>=0;l–)
{
if(j<0)
{
j++;
}
sum[k]=sum[k]+a[l][j];
j–;
}
g++;
}
int largest=sum[0];
for(k=0;k<t;k++)
{
if(largest<sum[k])
{
largest=sum[k];
}
}
printf("%d\n",largest);
}
return 0;
}
Explain the logic ?
I have taken a two-dimensional array to make the triangle.First, I have taken n number of test cases then in each test case t number of lines are taken i.e the number of rows in each array would be t.Then I have taken input in such a way that the values get entered in a triangle.
NOW, for output I have taken a variable sum which is a array,and I made the values of all its elements zero.Then I started finding the sum form the last element of the last row in each triangle to the first element of the first row then from second last element to the first element and so on till the last element of first row to the first element of first row.
For example,
Consider the value of t=3
since g=1;
this implies,j=2;
then for k=0,the value of l starts form 2 to 0,
for j=2 and l=2
sum[0]= 0 + a[2][2]
then for j-- and l–,j=1,l=1
sum[0]=a[2][2]+a[1][1]
then j=0,l=0
sum[0]= a[2][2]+a[1][1]+a[0][0]
now,for g++,j=1
Then similarly for k=1
when we have j=0 and we have to do j–,the value of j will become -1,so I have considered that if j<0,j=j+1,so that the value of j will be zero and I will get the desired value.
i.e for k=1, I would have
sum[1]=a[2][1]+a[1][0]+a[0][0]
then for k=2,j=0
sum[2]=a[2][0]+a[1][0]+a[0][0]
now we have a array of sum of all the paths in the triangle.
Then I found the largest of them.
My code is running very well on my pc and is giving the right answer,but i don’t know why code chef is giving me wrong answer…please check whether my code is correct or not.
Thank you…
I have explained it below in the answer.
Did u consider this case? 00->11->21
Question says:
on each path the next number is located on the row below, more precisely either directly below or below and one place to the right;
According to your logic the test cases give correct answer but consider – if 3rd row 2nd element was 5.then path would be 1->1->5=7
Now I have modified my code but its still not working…
please help…!!
http://www.codechef.com/viewsolution/4202484 my code is here on this link. Please check whats wrong in it. The logic is same as that of earlier but the change is that the paths which I was not taking earlier, I have taken another loop for them. Please check my code once…because I am not getting whats wrong now.