Dados cuatro números enteros A , B , C y D , la tarea es encontrar el número de conjuntos distintos (X, Y y Z) donde X, Y y Z denotan la longitud de los lados que forman un triángulo válido. A ≤ X ≤ B, B ≤ Y ≤ C y C ≤ Z ≤ D.
Ejemplos:
Entrada: A = 2, B = 3, C = 4, D = 5
Salida: 7
Explicación:
La longitud posible del lado de los triángulos es:
{(2, 3, 4), (2, 4, 4), (2, 4, 5), (3, 3, 4), (3, 3, 5), (3, 4, 4) y (3, 4, 5)}
Entrada: A = 1, B = 1, C = 2 , D = 2
Salida: 1
Explicación:
La única longitud posible de los lados que podemos elegir para el triángulo es (1, 2, 2)
Enfoque ingenuo: la observación clave en el problema es que, si X, Y y Z son los lados válidos de un triángulo y X ≤ Y ≤ Z, entonces las condiciones suficientes para que estos lados formen un triángulo válido serán X+Y > Z .
Finalmente, el recuento del posible valor Z para X e Y dados se puede calcular como:
- Si X+Y es mayor que D, para este caso Z se puede elegir entre [C, D], los valores totales posibles de Z serán (D-C+1).
- Si X+Y es menor que D y mayor que C, entonces Z puede elegirse entre [C, X+Y-1].
- Si X+Y es menor o igual que C, entonces no podemos elegir Z ya que estos lados no formarán un triángulo válido.
Complejidad del tiempo: 
Enfoque eficiente: la idea es iterar para todos los valores posibles de A y luego calcular la cantidad de valores posibles de Y y Z para la X dada mediante cálculos matemáticos.
Para un X dado, el valor de X+Y estará en el rango de ![[X+B, X+C]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-6445e5e43500cea90532bfc63e2e3267_l3.png "Procesado por QuickLaTeX.com")
. Si calculamos el número de valores posibles mayores que D, entonces el número total de valores posibles de Y y Z será:
// Number of possible values of Y and Z // If num_greater is the number of possible // Y values which is greater than D
De manera similar, sean R y L el límite superior y el límite inferior de los valores de X+Y en el rango de C y D. Entonces, las combinaciones totales para Y y Z serán:
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count the
// number of possible triangles
// for the given sides ranges
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of
// possible triangles for the given
// sides ranges
int count_triangles(int a, int b,
int c, int d)
{
int ans = 0;
// Iterate for every possible of x
for (int x = a; x <= b; ++x) {
// Range of y is [b, c]
// From this range First
// we will find the number
// of x + y greater than d
int num_greater_than_d = max(d, c + x) - max(d, b + x - 1);
// For x+y greater than d
// we can choose all z from [c, d]
// Total permutation will be
ans += num_greater_than_d * (d - c + 1);
// Now we will find the number
// of x+y in between the [c, d]
int r = min(max(c, c + x), d) - c;
int l = min(max(c, b + x - 1), d) - c;
// [l, r] will be the range
// from total [c, d] x+y belongs
// For any r such that r = x+y
// We can choose z, in the range
// [c, d] only less than r,
// Thus total permutation be
int x1 = (r * (r + 1)) / 2;
int x2 = (l * (l + 1)) / 2;
ans += x1 - x2;
}
return ans;
}
// Driver Code
int main()
{
int a = 2, b = 3, c = 4, d = 5;
cout << count_triangles(a, b, c, d)
<< endl;
return 0;
}
Java
// Java implementation to count the
// number of possible triangles
// for the given sides ranges
import java.util.Scanner;
import java.util.Arrays;
class GFG{
// Function to count the number of
// possible triangles for the given
// sides ranges
public static int count_triangles(int a, int b,
int c, int d)
{
int ans = 0;
// Iterate for every possible of x
for(int x = a; x <= b; ++x)
{
// Range of y is [b, c]
// From this range First
// we will find the number
// of x + y greater than d
int num_greater_than_d = Math.max(d, c + x) -
Math.max(d, b + x - 1);
// For x+y greater than d
// we can choose all z from [c, d]
// Total permutation will be
ans += num_greater_than_d * (d - c + 1);
// Now we will find the number
// of x+y in between the [c, d]
int r = Math.min(Math.max(c, c + x), d) - c;
int l = Math.min(Math.max(c, b + x - 1), d) - c;
// [l, r] will be the range
// from total [c, d] x+y belongs
// For any r such that r = x+y
// We can choose z, in the range
// [c, d] only less than r,
// Thus total permutation be
int x1 = (r * (r + 1)) / 2;
int x2 = (l * (l + 1)) / 2;
ans += x1 - x2;
}
return ans;
}
// Driver Code
public static void main(String args[])
{
int a = 2, b = 3, c = 4, d = 5;
System.out.println(count_triangles(a, b, c, d));
}
}
// This code is contributed by SoumikMondal
Python3
# Python3 implementation to count # the number of possible triangles # for the given sides ranges # Function to count the number of # possible triangles for the given # sides ranges def count_triangles(a, b, c, d): ans = 0 # Iterate for every possible of x for x in range(a, b + 1): # Range of y is [b, c] # From this range First # we will find the number # of x + y greater than d num_greater_than_d = (max(d, c + x) - max(d, b + x - 1)) # For x+y greater than d we # can choose all z from [c, d] # Total permutation will be ans = (ans + num_greater_than_d * (d - c + 1)) # Now we will find the number # of x+y in between the [c, d] r = min(max(c, c + x), d) - c; l = min(max(c, b + x - 1), d) - c; # [l, r] will be the range # from total [c, d] x+y belongs # For any r such that r = x+y # We can choose z, in the range # [c, d] only less than r, # Thus total permutation be x1 = int((r * (r + 1)) / 2) x2 = int((l * (l + 1)) / 2) ans = ans + (x1 - x2) return ans # Driver Code a = 2 b = 3 c = 4 d = 5 print (count_triangles(a, b, c, d), end = '\n') # This code is contributed by PratikBasu
C#
// C# implementation to count the
// number of possible triangles
// for the given sides ranges
using System;
class GFG{
// Function to count the number of
// possible triangles for the given
// sides ranges
public static int count_triangles(int a, int b,
int c, int d)
{
int ans = 0;
// Iterate for every possible of x
for(int x = a; x <= b; ++x)
{
// Range of y is [b, c]
// From this range First
// we will find the number
// of x + y greater than d
int num_greater_than_d = Math.Max(d, c + x) -
Math.Max(d, b + x - 1);
// For x+y greater than d
// we can choose all z from [c, d]
// Total permutation will be
ans += num_greater_than_d * (d - c + 1);
// Now we will find the number
// of x+y in between the [c, d]
int r = Math.Min(Math.Max(c, c + x), d) - c;
int l = Math.Min(Math.Max(c, b + x - 1), d) - c;
// [l, r] will be the range
// from total [c, d] x+y belongs
// For any r such that r = x+y
// We can choose z, in the range
// [c, d] only less than r,
// Thus total permutation be
int x1 = (r * (r + 1)) / 2;
int x2 = (l * (l + 1)) / 2;
ans += x1 - x2;
}
return ans;
}
// Driver Code
public static void Main(String []args)
{
int a = 2, b = 3, c = 4, d = 5;
Console.WriteLine(count_triangles(a, b, c, d));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// JavaScript implementation to count the
// number of possible triangles
// for the given sides ranges
// Function to count the number of
// possible triangles for the given
// sides ranges
function count_triangles(a , b, c , d)
{
var ans = 0;
// Iterate for every possible of x
for(x = a; x <= b; ++x)
{
// Range of y is [b, c]
// From this range First
// we will find the number
// of x + y greater than d
var num_greater_than_d = Math.max(d, c + x) -
Math.max(d, b + x - 1);
// For x+y greater than d
// we can choose all z from [c, d]
// Total permutation will be
ans += num_greater_than_d * (d - c + 1);
// Now we will find the number
// of x+y in between the [c, d]
var r = Math.min(Math.max(c, c + x), d) - c;
var l = Math.min(Math.max(c, b + x - 1), d) - c;
// [l, r] will be the range
// from total [c, d] x+y belongs
// For any r such that r = x+y
// We can choose z, in the range
// [c, d] only less than r,
// Thus total permutation be
var x1 = (r * (r + 1)) / 2;
var x2 = (l * (l + 1)) / 2;
ans += x1 - x2;
}
return ans;
}
// Driver Code
var a = 2, b = 3, c = 4, d = 5;
document.write(count_triangles(a, b, c, d));
// This code contributed by shikhasingrajput
</script>
7
Tiempo Complejidad : O(ba)
Complejidad espacial: O (1), ya que no estamos usando ningún espacio adicional
Publicación traducida automáticamente
Artículo escrito por shivamsinghal1012 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA