Número de formas de dividir N en trillizos formando un triángulo

Dado un número entero N , la tarea es encontrar el número de formas de dividir N en tripletes ordenados que juntos pueden formar un triángulo.

Ejemplos:

Entrada: N = 15 
Salida: El número total de triángulos posibles es 28

Entrada: N = 9 
Salida: El número total de triángulos posibles es 10 
 

Enfoque: Es necesario hacer la siguiente observación para resolver el problema: 

Si N se divide en 3 números enteros a, b y c, entonces se deben cumplir las siguientes condiciones para que a, b y c formen un triángulo: 

• a + b > c
   
• a + c > b
   
• b + c > un

Por lo tanto, itere sobre el rango [1, N] usando bucles anidados para generar tripletes, y para cada triplete verifique si forma un triángulo o no. 

A continuación se muestra la implementación del enfoque anterior:

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the
// required number of ways
int Numberofways(int n)
{
    int count = 0;
 
    for (int a = 1; a < n; a++) {
 
        for (int b = 1; b < n; b++) {
 
            int c = n - (a + b);
 
            // Check if a, b and c can
            // form a triangle
            if (a + b > c && a + c > b
                && b + c > a) {
                count++;
            }
        }
    }
 
    // Return number of ways
    return count;
}
 
// Driver Code
int main()
{
    int n = 15;
 
    cout << Numberofways(n) << endl;
 
    return 0;
}

// Java Program to implement
// the above approach
import java.io.*;
 
class GFG {
 
    // Function to return the
    // required number of ways
    static int Numberofways(int n)
    {
        int count = 0;
 
        for (int a = 1; a < n; a++) {
 
            for (int b = 0; b < n; b++) {
 
                int c = n - (a + b);
 
                // Check if a, b, c can
                // form a triangle
                if (a + b > c && a + c > b
                    && b + c > a) {
                    count++;
                }
            }
        }
 
        return count;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 15;
 
        System.out.println(Numberofways(n));
    }
}

# Python Program to implement
# the above approach
 
# Function to return the
# required number of ways
def Numberofways(n):
    count = 0
    for a in range(1, n):
        for b in range(1, n):
 
            c = n - (a + b)
 
            # Check if a, b, c can form a triangle
            if(a < b + c and b < a + c and c < a + b):
                count += 1
 
    return count
 
 
# Driver code
n = 15
print(Numberofways(n))

// C# Program to implement
// the above approach
 
using System;
 
class GFG {
 
    // Function to return the
    // required number of ways
    static int Numberofways(int n)
    {
        int count = 0;
        for (int a = 1; a < n; a++) {
            for (int b = 1; b < n; b++) {
                int c = n - (a + b);
 
                // Check if a, b, c can form
                // a triangle or not
                if (a + b > c && a + c > b
                    && b + c > a) {
                    count++;
                }
            }
        }
 
        // Return number of ways
        return count;
    }
 
    // Driver Code
    static public void Main()
    {
        int n = 15;
 
        Console.WriteLine(Numberofways(n));
    }
}

<script>
// Javascript Program to implement
// the above approach
 
// Function to return the
// required number of ways
function Numberofways(n)
{
    var count = 0;
 
    for (var a = 1; a < n; a++)
    {
        for (var b = 1; b < n; b++)
        {
            var c = n - (a + b);
 
            // Check if a, b and c can
            // form a triangle
            if (a + b > c && a + c > b
                && b + c > a)
            {
                count++;
            }
        }
    }
 
    // Return number of ways
    return count;
}
 
// Driver Code
var n = 15;
document.write( Numberofways(n));
 
// This code is contributed by noob2000.
</script>

28

Tiempo Complejidad: O(N ² ) 
Espacio Auxiliar: O(N)