Hello there, today we are going to solve Sums in a Triangle CodeChef Solution whose Problem Code is SUMTRIAN.
👊 Table of ContentsTask
Let's consider a triangle of numbers in which a number appears in the first line, two numbers appear in the second line, three in the third line, etc. Develop a program which will compute the largest of the sums of numbers that appear on the paths starting from the top towards the base, so that:
- 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;
- the number of rows is strictly positive, but less than 100
- all numbers are positive integers between 0 and 99.
Input
In the first line integer n - the number of test cases (equal to about 1000). Then n test cases follow. Each test case starts with the number of lines which is followed by their content.
Output
For each test case write the determined value in a separate line.
Example
Sample Input:
2 3 1 2 1 1 2 3 4 1 1 2 4 1 2 2 3 1 1
Sample Output:
5
9
Solution - Sums in a Triangle - CodeChef Solution
Python 3
#Solution Provided by Sloth Coders
T = int(input())
for i in range(T):
l = []
m = int(input())
for j in range(m):
n = list(map(int, input().split()))
l.append(n)
for j in range(m - 2, -1, -1):
for k in range(0, j+1):
l[j][k] += max(l[j+1][k], l[j+1][k+1])
print(l[0][0])
C++
#include <iostream>
#include <cmath>
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
int a[n][n];
for(int i=0;i<n;i++)
{
for(int j=0;j<=i;j++)
{
cin>>a[i][j];
}
}
for(int i=n-2;i>=0;i--)
{
for(int j=0;j<n-1;j++)
{
a[i][j]=a[i][j]+max(a[i+1][j],a[i+1][j+1]);
}
}
cout<<a[0][0]<<endl;
}
return 0;
}
C
#include <stdio.h> int max(int a,int b){ if(a > b){ return a; } return b; } int main(void) { int t, n; scanf("%d",&t); for(int test=1;test<=t;test++){ scanf("%d",&n); int a[n][n]; for(int i=0;i<n;i++){ for(int j=0;j<=i;j++){ scanf("%d",&(a[i][j])); } } for(int i=n-2;i>=0;i--){ for(int j=0;j<=i;j++){ a[i][j] += max(a[i+1][j],a[i+1][j+1]); } } printf("%d\n",a[0][0]); } return 0; }
Java
import java.util.*;
class Codechef
{
public static void main (String[] args)
{
try{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0){
int n=sc.nextInt();
int arr[][]=new int [n][n];
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
arr[i][j]=sc.nextInt();
} }
for(int i=n-2;i>=0;i--){
for(int j=0;j<=i;j++){
if((arr[i][j]+arr[i+1][j])>(arr[i][j]+arr[i+1][j+1])){
arr[i][j]=arr[i][j] + arr[i+1][j]; }
else{
arr[i][j]=arr[i][j] + arr[i+1][j+1]; }
} }
System.out.println(arr[0][0]);
} }
catch(Exception e){ }
} }
Disclaimer: The above Problem (Sums in a Triangle) is generated by CodeChef but the Solution is provided by Sloth Coders.
Also Read:
- Primality Test - CodeChef Solution
- Total Expense - CodeChef Solution
- World Record - CodeChef Solution
- Valid Pair - CodeChef Solution
- Fit Squares in Triangles - CodeChef Solution