Recuento de recipientes completamente llenos después de un tiempo determinado

Posted on by Rudeus Greyrat

Dados dos números enteros N y T que denotan el número de niveles y el número de segundos respectivamente, la tarea es encontrar el número de recipientes completamente llenos después de T segundos bajo condiciones dadas:
 

  • Una estructura de vasos de N niveles es tal que el número de vasos en cada nivel es igual al número de nivel, es decir , 1, 2, 3,… hasta N.
  • Cada recipiente puede almacenar un máximo de 1 unidad de agua y cada segundo se vierte 1 unidad de agua de un grifo a un ritmo constante.
  • Si el recipiente se llena, el agua comienza a fluir y se derrama sobre los bordes del recipiente, y se distribuye por igual entre los dos recipientes conectados inmediatamente debajo de él.

Suposiciones:

  1. Todos los objetos están dispuestos simétricamente a lo largo del eje horizontal.
  2. Todos los niveles están igualmente espaciados.
  3. El agua fluye simétricamente sobre ambos bordes del recipiente.

Ejemplos:

Entrada: N = 3, T = 2
Salida: 1
Explicación:
Vista de la Estructura con N = 3 y en un tiempo T = 2 después de abrir el grifo

Entrada: N = 3, T = 4
Salida: 3
Explicación:
Vista de Estructura con N = 3 y en un tiempo T = 4 después de abrir el grifo

Enfoque ingenuo: el enfoque más simple para resolver el problema es verificar si es posible llenar x recipientes por completo en T segundos o no. Si se determina que es cierto, verifique los vasos x+1 y repita así sucesivamente para obtener el valor máximo de x .
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
 

Enfoque eficiente: el enfoque anterior se puede optimizar mediante la programación dinámica . Siga los pasos a continuación para resolver el problema:

  1. Guarde la estructura del recipiente en una Array , digamos M , donde M[i][j] denota el j -ésimo recipiente en el i -ésimo nivel .
  2. Para cualquier vaso M[i][j] , los vasos conectados en un nivel inmediatamente inferior son M[i + 1][j] y M[i + 1][j + 1] .
  3. Inicialmente, ponga toda el agua en el primer recipiente i, e. M[0][0] = t .
  4. Vuelva a calcular el estado de la array en cada incremento de la unidad de tiempo, comenzando desde el vaso superior i, e. M[0][0] = t .
  5. Si la cantidad de agua excede el volumen del recipiente, la cantidad que baja del recipiente se divide en dos partes iguales.
  6. partes que llenan los dos recipientes conectados en el nivel inmediatamente inferior.

C++

// C++ program to implement 
// the above approach 
#include <bits/stdc++.h> 
using namespace std; 
   
int n, t;
   
// Function to find the number of
// completely filled vessels
int FindNoOfFullVessels(int n, int t)
{
       
    // Store the vessels
    double Matrix[n][n];
   
    // Assuming all water is present
    // in the vessel at the first level
    Matrix[0][0] = t * 1.0;
   
    // Store the number of vessel
    // that are completely full
    int ans = 0;
   
    // Traverse all the levels
    for(int i = 0; i < n; i++)
    {
           
        // Number of vessel at each
        // level is j
        for(int j = 0; j <= i; j++)
        {
               
            // Calculate the exceeded
            // amount of water
            double exceededwater = Matrix[i][j] - 1.0;
   
            // If current vessel has
            // less than 1 unit of
            // water then continue
            if (exceededwater < 0)
                continue;
   
            // One more vessel is full
            ans++;
   
            // If left bottom vessel present
            if (i + 1 < n)
                Matrix[i + 1][j] += exceededwater / 2;
   
            // If right bottom vessel present
            if (i + 1 < n && j + 1 < n)
                Matrix[i + 1][j + 1] += exceededwater / 2;
        }
    }
    return ans;
}
   
// Driver Code
int main()
{
       
    // Number of levels
    int N = 3;
   
    // Number of seconds
    int T = 4;
   
    // Function call
    cout << FindNoOfFullVessels(N, T) << endl;
       
    return 0;
}
   
// This code is contributed by sanjoy_62

C

// C program to implement
 
#include <stdio.h>
 
int n, t;
 
// Function to find the number of
// completely filled vessels
int FindNoOfFullVessels(int n, int t)
{
     
    // Store the vessels
    double Matrix[n][n];
 
    // Assuming all water is present
    // in the vessel at the first level
    Matrix[0][0] = t * 1.0;
 
    // Store the number of vessel
    // that are completely full
    int ans = 0;
 
    // Traverse all the levels
    for(int i = 0; i < n; i++)
    {
         
        // Number of vessel at each
        // level is j
        for(int j = 0; j <= i; j++)
        {
             
            // Calculate the exceeded
            // amount of water
            double exceededwater = Matrix[i][j] - 1.0;
 
            // If current vessel has
            // less than 1 unit of
            // water then continue
            if (exceededwater < 0)
                continue;
 
            // One more vessel is full
            ans++;
 
            // If left bottom vessel present
            if (i + 1 < n)
                Matrix[i + 1][j] += exceededwater / 2;
 
            // If right bottom vessel present
            if (i + 1 < n && j + 1 < n)
                Matrix[i + 1][j + 1] += exceededwater / 2;
        }
    }
    return ans;
}
 
// Driver Code
int main()
{
     
    // Number of levels
    int N = 3;
 
    // Number of seconds
    int T = 4;
 
    // Function call
    printf("%d", FindNoOfFullVessels(N, T));
     
    return 0;
}
 
// This code is contributed by allwink45.

Java

// Java Program to implement
// the above approach
   
import java.io.*;
import java.util.*;
   
class GFG {
   
    static int n, t;
   
    // Function to find the number of
    // completely filled vessels
    public static int
    FindNoOfFullVessels(int n, int t)
    {
        // Store the vessels
        double Matrix[][]
            = new double[n][n];
   
        // Assuming all water is present
        // in the vessel at the first level
        Matrix[0][0] = t * 1.0;
   
        // Store the number of vessel
        // that are completely full
        int ans = 0;
   
        // Traverse all the levels
        for (int i = 0; i < n; i++) {
   
            // Number of vessel at each
            // level is j
            for (int j = 0; j <= i; j++) {
   
                // Calculate the exceeded
                // amount of water
                double exceededwater
                    = Matrix[i][j] - 1.0;
   
                // If current vessel has
                // less than 1 unit of
                // water then continue
                if (exceededwater < 0)
                    continue;
   
                // One more vessel is full
                ans++;
   
                // If left bottom vessel present
                if (i + 1 < n)
                    Matrix[i + 1][j]
                        += exceededwater / 2;
   
                // If right bottom vessel present
                if (i + 1 < n && j + 1 < n)
                    Matrix[i + 1][j + 1]
                        += exceededwater / 2;
            }
        }
   
        return ans;
    }
   
    // Driver Code
    public static void main(String[] args)
    {
        // Number of levels
        int N = 3;
   
        // Number of seconds
        int T = 4;
   
        // Function call
        System.out.println(
            FindNoOfFullVessels(N, T));
    }
}

Python3

# Python3 program to implement    
# the above approach    
      
# Function to find the number of    
# completely filled vessels    
def FindNoOfFullVessels(n, t) :    
         
    # Store the vessels    
    Matrix = [[0 for i in range(n)] for j in range(n)]   
      
    # Assuming all water is present    
    # in the vessel at the first level    
    Matrix[0][0] = t * 1.0    
      
    # Store the number of vessel    
    # that are completely full    
    ans = 0    
      
    # Traverse all the levels    
    for i in range(n) :   
             
        # Number of vessel at each    
        # level is j    
        for j in range(i + 1) :   
                 
            # Calculate the exceeded    
            # amount of water    
            exceededwater = Matrix[i][j] - 1.0    
      
            # If current vessel has    
            # less than 1 unit of    
            # water then continue    
            if (exceededwater < 0) :   
                continue   
      
            # One more vessel is full    
            ans += 1    
      
            # If left bottom vessel present    
            if (i + 1 < n) :    
                Matrix[i + 1][j] += exceededwater / 2   
      
            # If right bottom vessel present    
            if (i + 1 < n and j + 1 < n) :   
                Matrix[i + 1][j + 1] += exceededwater / 2    
    return ans   
      
         
# Number of levels    
N = 3   
      
# Number of seconds    
T = 4   
      
# Function call    
print(FindNoOfFullVessels(N, T))
 
# This code is contributed by divyesh072019

C#

// C# program to implement 
// the above approach 
using System; 
   
class GFG{
   
//static int n, t;
   
// Function to find the number of
// completely filled vessels
public static int FindNoOfFullVessels(int n, 
                                      int t)
{
       
    // Store the vessels
    double[,] Matrix = new double[n, n];
   
    // Assuming all water is present
    // in the vessel at the first level
    Matrix[0, 0] = t * 1.0;
   
    // Store the number of vessel
    // that are completely full
    int ans = 0;
   
    // Traverse all the levels
    for(int i = 0; i < n; i++)
    {
   
        // Number of vessel at each
        // level is j
        for(int j = 0; j <= i; j++) 
        {
   
            // Calculate the exceeded
            // amount of water
            double exceededwater = Matrix[i, j] - 1.0;
   
            // If current vessel has
            // less than 1 unit of
            // water then continue
            if (exceededwater < 0)
                continue;
   
            // One more vessel is full
            ans++;
   
            // If left bottom vessel present
            if (i + 1 < n)
                Matrix[i + 1, j] += exceededwater / 2;
   
            // If right bottom vessel present
            if (i + 1 < n && j + 1 < n)
                Matrix[i + 1, j + 1] += exceededwater / 2;
        }
    }
    return ans;
}
   
// Driver Code
public static void Main()
{
       
    // Number of levels
    int N = 3;
   
    // Number of seconds
    int T = 4;
   
    // Function call
    Console.WriteLine(FindNoOfFullVessels(N, T));
}
}
   
// This code is contributed by sanjoy_62

Javascript

<script>
 
// JavaScript program to implement 
// the above approach 
   
var n, t;
   
// Function to find the number of
// completely filled vessels
function FindNoOfFullVessels(n, t)
{
       
    // Store the vessels
    var Matrix = Array.from(Array(n), ()=> Array(n).fill(0));
   
    // Assuming all water is present
    // in the vessel at the first level
    Matrix[0][0] = t * 1.0;
   
    // Store the number of vessel
    // that are completely full
    var ans = 0;
   
    // Traverse all the levels
    for(var i = 0; i < n; i++)
    {
           
        // Number of vessel at each
        // level is j
        for(var j = 0; j <= i; j++)
        {
               
            // Calculate the exceeded
            // amount of water
            var exceededwater = Matrix[i][j] - 1;
   
            // If current vessel has
            // less than 1 unit of
            // water then continue
            if (exceededwater < 0)
                continue;
   
            // One more vessel is full
            ans++;
   
            // If left bottom vessel present
            if (i + 1 < n)
                Matrix[i + 1][j] += (exceededwater / 2);
   
            // If right bottom vessel present
            if (i + 1 < n && j + 1 < n)
                Matrix[i + 1][j + 1] += (exceededwater / 2);
        }
    }
    return ans;
}
   
// Driver Code
// Number of levels
var N = 3;
 
// Number of seconds
var T = 4;
 
// Function call
document.write( FindNoOfFullVessels(N, T));
 
 
</script>

Producción: 

3

Complejidad temporal: O(N 2 )
Complejidad espacial: O(N 2 )
 

Publicación traducida automáticamente

Artículo escrito por Kingash y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *