Dado un triángulo equilátero formado por puntos ( . ) unidos para formar un triángulo y un número entero n que representa la longitud de los lados del triángulo. La tarea es contar el número de rectángulos que se pueden inscribir en el triángulo dado tal que:
- Los bordes horizontales deben ser paralelos a la base del triángulo dado.
- El rectángulo solo debe formarse uniendo los puntos, es decir, los cuatro bordes del rectángulo deben tocar los puntos del triángulo.
- Solo se deben contar los rectángulos distintos.
Ejemplos:
Input: N = 3
Output: 1
.
. .
. . .
. . . .
The only triangle possible has the top edges
at the two points of the second row and bottom edges
at the 2nd and the 3rd points in the last row.
Input: N = 5
Output: 11
Enfoque: de la figura anterior, está claro que el nivel n y n – 1 no contribuye a formar ningún rectángulo, por lo que comenzamos a contar el rectángulo desde el nivel n – 2 . Cuando n es impar y el nivel en el que estamos calculando, digamos, i también es impar, entonces la diferencia será par, por lo que la dividiremos entre 2. Esto nos dará el número de niveles verticales entre el nivel n e i que se pueden usar para hacer rectángulos y esto es lo mismo si ambos son pares como la diferencia de números pares es par.
Pero cuando uno de ellos es impar, la diferencia será impar y, por lo tanto , n – 1 nivel contribuirá a seleccionar niveles verticales.n – 1 nivel se utiliza en el cálculo. Para calcular el número de formas en que se pueden seleccionar los dos puntos en el nivel horizontal, podemos usar la fórmula para la suma de n números naturales porque N C 2 = 1 + 2 + 3 + … + (N – 1) . Ahora multiplicamos el número de formas de elegir dos puntos en un nivel por el número de puntos en el nivel vertical. Este será nuestro resultado para ese nivel en particular, por lo que repetiremos estos pasos hasta el final y sumaremos todos los valores.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Function to return the count of
// rectangles when n is odd
int countOdd(int n)
{
int coun = 0, m, j, i;
for (i = n - 2; i >= 1; i--) {
if (i & 1) {
// Calculating number of dots
// in vertical level
m = (n - i) / 2;
// Calculating number of ways
// to select two points in the
// horizontal level i
j = (i * (i + 1)) / 2;
// Multiply both to obtain the number of
// rectangles formed at that level
coun += j * m;
}
else {
// Calculating number of dots
// in vertical level
m = ((n - 1) - i) / 2;
// Calculating number of ways
// to select two points in the
// horizontal level i
j = (i * (i + 1)) / 2;
// Multiply both to obtain the number of
// rectangles formed at that level
coun += j * m;
}
}
return coun;
}
// Function to return the count of
// rectangles when n is even
int countEven(int n)
{
int coun = 0, m, j, i;
for (i = n - 2; i >= 1; i--) {
if (i & 1) {
m = ((n - 1) - i) / 2;
j = (i * (i + 1)) / 2;
coun += j * m;
}
else {
m = (n - i) / 2;
j = (i * (i + 1)) / 2;
coun += j * m;
}
}
return coun;
}
// Driver code
int main()
{
int n = 5;
// If n is odd
if (n & 1)
cout << countOdd(n);
else
cout << countEven(n);
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
class GFG {
// Function to return the count of
// rectangles when n is odd
static int countOdd(int n)
{
int coun = 0, m, j, i;
for (i = n - 2; i >= 1; i--) {
if (i >= 1) {
// Calculating number of dots
// in vertical level
m = (n - i) / 2;
// Calculating number of ways
// to select two points in the
// horizontal level i
j = (i * (i + 1)) / 2;
// Multiply both to obtain the number of
// rectangles formed at that level
coun += j * m;
}
else {
// Calculating number of dots
// in vertical level
m = ((n - 1) - i) / 2;
// Calculating number of ways
// to select two points in the
// horizontal level i
j = (i * (i + 1)) / 2;
// Multiply both to obtain the number of
// rectangles formed at that level
coun += j * m;
}
}
return coun;
}
// Function to return the count of
// rectangles when n is even
static int countEven(int n)
{
int coun = 0, m, j, i;
for (i = n - 2; i >= 1; i--) {
if (i >= 1) {
m = ((n - 1) - i) / 2;
j = (i * (i + 1)) / 2;
coun += j * m;
}
else {
m = (n - i) / 2;
j = (i * (i + 1)) / 2;
coun += j * m;
}
}
return coun;
}
// Driver code
public static void main(String[] args)
{
int n = 5;
// If n is odd
if (n >= 1)
System.out.println(countOdd(n));
else
System.out.println(countEven(n));
}
}
// This code is contributed by Tushil..
Python3
# Python 3 implementation of the approach # Function to return the count of # rectangles when n is odd def countOdd(n): coun = 0 i = n - 2 while (i >= 1): if (i & 1): # Calculating number of dots # in vertical level m = int((n - i) / 2) # Calculating number of ways # to select two points in the # horizontal level i j = int((i * (i + 1)) / 2) # Multiply both to obtain the number of # rectangles formed at that level coun += j * m else: # Calculating number of dots # in vertical level m = int(((n - 1) - i) / 2) # Calculating number of ways # to select two points in the # horizontal level i j = int((i * (i + 1)) / 2) # Multiply both to obtain the number of # rectangles formed at that level coun += j * m i -= 1 return coun # Function to return the count of # rectangles when n is even def countEven(n): coun = 0 i = n - 2 while(i >= 1): if (i & 1): m = int(((n - 1) - i) / 2) j = int((i * (i + 1)) / 2) coun += j * m else: m = int((n - i) / 2) j = (i * (i + 1)) // 2 coun += j * m return coun # Driver code if __name__ == '__main__': n = 5 # If n is odd if (n & 1): print(countOdd(n)) else: print(countEven(n)) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG {
// Function to return the count of
// rectangles when n is odd
static int countOdd(int n)
{
int coun = 0, m, j, i;
for (i = n - 2; i >= 1; i--) {
if (i >= 1) {
// Calculating number of dots
// in vertical level
m = (n - i) / 2;
// Calculating number of ways
// to select two points in the
// horizontal level i
j = (i * (i + 1)) / 2;
// Multiply both to obtain the number of
// rectangles formed at that level
coun += j * m;
}
else {
// Calculating number of dots
// in vertical level
m = ((n - 1) - i) / 2;
// Calculating number of ways
// to select two points in the
// horizontal level i
j = (i * (i + 1)) / 2;
// Multiply both to obtain the number of
// rectangles formed at that level
coun += j * m;
}
}
return coun;
}
// Function to return the count of
// rectangles when n is even
static int countEven(int n)
{
int coun = 0, m, j, i;
for (i = n - 2; i >= 1; i--) {
if (i >= 1) {
m = ((n - 1) - i) / 2;
j = (i * (i + 1)) / 2;
coun += j * m;
}
else {
m = (n - i) / 2;
j = (i * (i + 1)) / 2;
coun += j * m;
}
}
return coun;
}
// Driver code
static public void Main()
{
int n = 5;
// If n is odd
if (n >= 1)
Console.Write(countOdd(n));
else
Console.Write(countEven(n));
}
}
// This code is contributed by Tushil..
PHP
<?php
// PHP implementation of the approach
// Function to return the count of
// rectangles when n is odd
function countOdd($n)
{
$coun = 0;
for ($i = $n - 2; $i >= 1; $i--)
{
if ($i & 1)
{
// Calculating number of dots
// in vertical level
$m = ($n - $i) / 2;
// Calculating number of ways
// to select two points in the
// horizontal level i
$j = ($i * ($i + 1)) / 2;
// Multiply both to obtain the number of
// rectangles formed at that level
$coun += $j * $m;
}
else
{
// Calculating number of dots
// in vertical level
$m = (($n - 1) - $i) / 2;
// Calculating number of ways
// to select two points in the
// horizontal level i
$j = ($i * ($i + 1)) / 2;
// Multiply both to obtain the number of
// rectangles formed at that level
$coun += $j * $m;
}
}
return $coun;
}
// Function to return the count of
// rectangles when n is even
function countEven($n)
{
$coun = 0;
for ($i = $n - 2; $i >= 1; $i--)
{
if ($i & 1)
{
$m = (($n - 1) - i) / 2;
$j = ($i * ($i + 1)) / 2;
$coun += $j * $m;
}
else
{
$m = ($n - $i) / 2;
$j = ($i * ($i + 1)) / 2;
$coun += $j * $m;
}
}
return $coun;
}
// Driver code
$n = 5;
// If n is odd
if ($n & 1)
echo countOdd($n);
else
echo countEven($n);
// This code is contributed by Arnab Kundu
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to return the count of
// rectangles when n is odd
function countOdd(n)
{
let coun = 0, m, j, i;
for (i = n - 2; i >= 1; i--) {
if (i >= 1) {
// Calculating number of dots
// in vertical level
m = parseInt((n - i) / 2, 10);
// Calculating number of ways
// to select two points in the
// horizontal level i
j = parseInt((i * (i + 1)) / 2, 10);
// Multiply both to obtain the number of
// rectangles formed at that level
coun += j * m;
}
else {
// Calculating number of dots
// in vertical level
m = parseInt(((n - 1) - i) / 2, 10);
// Calculating number of ways
// to select two points in the
// horizontal level i
j = parseInt((i * (i + 1)) / 2, 10);
// Multiply both to obtain the number of
// rectangles formed at that level
coun += j * m;
}
}
return coun;
}
// Function to return the count of
// rectangles when n is even
function countEven(n)
{
let coun = 0, m, j, i;
for (i = n - 2; i >= 1; i--) {
if (i >= 1) {
m = parseInt(((n - 1) - i) / 2, 10);
j = parseInt((i * (i + 1)) / 2, 10);
coun += j * m;
}
else {
m = parseInt((n - i) / 2, 10);
j = parseInt((i * (i + 1)) / 2, 10);
coun += j * m;
}
}
return coun;
}
let n = 5;
// If n is odd
if (n >= 1)
document.write(countOdd(n));
else
document.write(countEven(n));
</script>
Producción:
11
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)