Dado un número N y una unidad de tiempo X , la tarea es encontrar la cantidad de contenedores que se llenan por completo en X unidades si los contenedores están dispuestos en forma de pirámide como se muestra a continuación.
Nota: El siguiente ejemplo es la disposición piramidal para N = 3, donde N denota el número de niveles en la disposición de contenedores en forma de pirámide, de modo que el nivel 1 tiene 1 contenedor, el nivel 2 tiene 2 contenedores y hasta el nivel N. El líquido siempre se vierte en el recipiente superior en el 1er nivel. Cuando el contenedor de un nivel se desborda por ambos lados, los contenedores de los niveles inferiores se llenan. La cantidad de líquido vertido en cada segundo es igual al volumen del recipiente.
Ejemplos:
Entrada: N = 3, X = 5
Salida: 4
Después de 1 segundo, el contenedor en el nivel 1 se llena por completo.
Después de 2 segundos, los 2 contenedores del nivel 2 están medio llenos.
Después de 3 segundos, los 2 contenedores del nivel 2 están completamente llenos.
Después de 4 segundos, de los 3 contenedores en el nivel 3, los 2 contenedores en los extremos están llenos a un cuarto y el contenedor en el centro está lleno a la mitad.
Después de 5 segundos, de los 3 contenedores en el nivel 3, los 2 contenedores en los extremos están medio llenos y el contenedor en el centro está completamente lleno.Entrada: N = 4, X = 8
Salida: 6
Aproximación: Este problema se resuelve utilizando Aproximación codiciosa . A continuación se muestran los pasos:
- Una vez que se llena el recipiente, el líquido se desborda por igual de ambos lados del recipiente y llena los recipientes que se encuentran debajo.
- Considere esta pirámide de contenedores como una array. Entonces, cont[i][j] es el líquido en el j- ésimo contenedor de la i -ésima fila .
- Entonces, cuando ocurre un desbordamiento, el líquido fluye hacia cont[i+1][j] y cont[i+1][j+1] .
- Como el líquido se vierte durante X segundos, la cantidad total de líquido vertido es X unidades.
- Entonces, el valor máximo que se puede verter en un contenedor puede ser X unidades y el valor mínimo que se puede verter para llenarlo por completo es 1 unidad.
Como el líquido siempre se vierte en el recipiente superior, deje que el recipiente superior tenga un valor máximo, es decir, X unidades.
Los pasos para el algoritmo son los siguientes:
- Inicie el bucle exterior de 1 a N para n contenedores en cada nivel. Dentro de este ciclo, inicie otro ciclo de 1 a i , para cada contenedor de cada fila. También declare un contador, count = 0 , para contar los contenedores que se están llenando.
- Si el valor de cont[i][j] es mayor o igual a 1 (significa que está lleno), el conteo se incrementa en 1 y luego en cont[i+1][j] & g[i+1 ][j+1] se vierte el líquido y su valor aumenta en el valor de (g[i][j]-1)/2 respectivamente, porque el líquido se divide por la mitad en ambos.
- De esta manera continúa el ciclo e incrementa el conteo por cada contenedor lleno. Cuando finalice el ciclo, nuestro conteo será la respuesta requerida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above problem
#include <bits/stdc++.h>
using namespace std;
// matrix of containers
double cont[1000][1000];
// function to find the number
// of containers that will be
// filled in X seconds
void num_of_containers(int n,
double x)
{
int count = 0;
// container on top level
cont[1][1] = x;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
// if container gets filled
if (cont[i][j] >= (double)1) {
count++;
// dividing the liquid
// equally in two halves
cont[i + 1][j]
+= (cont[i][j]
- (double)1)
/ (double)2;
cont[i + 1][j + 1]
+= (cont[i][j]
- (double)1)
/ (double)2;
}
}
}
cout << count;
}
// driver code
int main()
{
int n = 3;
double x = 5;
num_of_containers(n, x);
return 0;
}
Java
// Java program for the above problem
import java.util.*;
class GFG{
// Matrix of containers
static double cont[][] = new double[1000][1000];
// Function to find the number
// of containers that will be
// filled in X seconds
static void num_of_containers(int n, double x)
{
int count = 0;
// Container on top level
cont[1][1] = x;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
// If container gets filled
if (cont[i][j] >= (double)1)
{
count++;
// Dividing the liquid
// equally in two halves
cont[i + 1][j] += (cont[i][j] -
(double)1) /
(double)2;
cont[i + 1][j + 1] += (cont[i][j] -
(double)1) /
(double)2;
}
}
}
System.out.print(count);
}
// Driver code
public static void main(String[] args)
{
int n = 3;
double x = 5;
num_of_containers(n, x);
}
}
// This code is contributed by jrishabh99
Python3
# Python3 program for the above problem # Matrix of containers cont = [[ 0 for i in range(1000)] for j in range(1000)] # Function to find the number # of containers that will be # filled in X seconds def num_of_containers(n, x): count = 0 # Container on top level cont[1][1] = x for i in range(1, n + 1): for j in range(1, i + 1): # If container gets filled if (cont[i][j] >= 1): count += 1 # Dividing the liquid # equally in two halves cont[i + 1][j] += (cont[i][j] - 1) / 2 cont[i + 1][j + 1] += (cont[i][j] - 1) / 2 print(count) # Driver code n = 3 x = 5 num_of_containers(n, x) # This code is contributed by yatinagg
C#
// C# program for the above problem
using System;
class GFG{
// Matrix of containers
static double [,]cont = new double[1000, 1000];
// Function to find the number
// of containers that will be
// filled in X seconds
static void num_of_containers(int n, double x)
{
int count = 0;
// Container on top level
cont[1, 1] = x;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= i; j++)
{
// If container gets filled
if (cont[i, j] >= (double)1)
{
count++;
// Dividing the liquid
// equally in two halves
cont[i + 1, j] += (cont[i, j] -
(double)1) /
(double)2;
cont[i + 1, j + 1] += (cont[i, j] -
(double)1) /
(double)2;
}
}
}
Console.Write(count);
}
// Driver code
public static void Main(String[] args)
{
int n = 3;
double x = 5;
num_of_containers(n, x);
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above problem
// function to find the number
// of containers that will be
// filled in X seconds
function num_of_containers(n, x)
{
var cont = new Array(100);
var i;
var j;
for (i=0;i<cont.length;i++)
cont[i] = new Array(100);
for(i=0;i<cont.length;i++){
for (j=0;j<cont[i].length;j++)
cont[i][j] = 0;
}
var count = 0;
// container on top level
cont[1][1] = x;
for (i = 1; i <= n; i++) {
for (j = 1; j <= i; j++) {
// if container gets filled
if (cont[i][j] >= 1) {
count += 1;
// dividing the liquid
// equally in two halves
cont[i + 1][j]
+= (cont[i][j]
- 1)
/ 2;
cont[i + 1][j + 1]
+= (cont[i][j]
- 1)
/ 2;
}
}
}
document.write(count);
}
// driver code
var n = 3;
var x = 5;
num_of_containers(n, x);
</script>
4
Complejidad temporal: O(N 2 )
Complejidad espacial auxiliar: O(N 2 )
Publicación traducida automáticamente
Artículo escrito por IshwarGupta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA