Hay algunos vasos con capacidad igual a 1 litro. Los vasos se mantienen de la siguiente manera:
1
2 3
4 5 6
7 8 9 10
Puedes poner agua en el único vaso superior. Si pone más de 1 litro de agua en el primer vaso, el agua se desborda y llena por igual el segundo y el tercer vaso. El vaso 5 obtendrá agua tanto del segundo vaso como del tercero y así sucesivamente.
Si tienes X litros de agua y la pones en un vaso superior, ¿cuánta agua contendrá el j-ésimo vaso en una i-ésima fila?
Ejemplo. Si vas a poner 2 litros encima.
1° – 1 litro
2° – 1/2 litro
3° – 1/2 litro
El enfoque es similar al Método 2 del Triángulo de Pascal . Si echamos un vistazo más de cerca al problema, el problema se reduce al Triángulo de Pascal .
1 ---------------- 1
2 3 ---------------- 2
4 5 6 ------------ 3
7 8 9 10 --------- 4
Cada vaso contribuye a los dos vasos del vaso. Inicialmente, ponemos toda el agua en el primer vaso. Luego mantenemos 1 litro (o menos de 1 litro) y movemos el resto del agua a dos vasos. Seguimos el mismo proceso para los dos vasos y todos los demás vasos hasta la i-ésima fila. Habrá i*(i+1)/2 vasos hasta la i-ésima fila.
C++
// Program to find the amount of water in j-th glass
// of i-th row
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Returns the amount of water in jth glass of ith row
float findWater(int i, int j, float X)
{
// A row number i has maximum i columns. So input
// column number must be less than i
if (j > i)
{
printf("Incorrect Inputn");
exit(0);
}
// There will be i*(i+1)/2 glasses till ith row
// (including ith row)
float glass[i * (i + 1) / 2];
// Initialize all glasses as empty
memset(glass, 0, sizeof(glass));
// Put all water in first glass
int index = 0;
glass[index] = X;
// Now let the water flow to the downward glasses
// till the row number is less than or/ equal to i (given row)
// correction : X can be zero for side glasses as they have lower rate to fill
for (int row = 1; row <= i ; ++row)
{
// Fill glasses in a given row. Number of
// columns in a row is equal to row number
for (int col = 1; col <= row; ++col, ++index)
{
// Get the water from current glass
X = glass[index];
// Keep the amount less than or equal to
// capacity in current glass
glass[index] = (X >= 1.0f) ? 1.0f : X;
// Get the remaining amount
X = (X >= 1.0f) ? (X - 1) : 0.0f;
// Distribute the remaining amount to
// the down two glasses
glass[index + row] += X / 2;
glass[index + row + 1] += X / 2;
}
}
// The index of jth glass in ith row will
// be i*(i-1)/2 + j - 1
return glass[i*(i-1)/2 + j - 1];
}
// Driver program to test above function
int main()
{
int i = 2, j = 2;
float X = 2.0; // Total amount of water
printf("Amount of water in jth glass of ith row is: %f",
findWater(i, j, X));
return 0;
}
Java
// Program to find the amount
/// of water in j-th glass
// of i-th row
import java.lang.*;
class GFG
{
// Returns the amount of water
// in jth glass of ith row
static float findWater(int i, int j,
float X)
{
// A row number i has maximum i
// columns. So input column
// number must be less than i
if (j > i)
{
System.out.println("Incorrect Input");
System.exit(0);
}
// There will be i*(i+1)/2 glasses
// till ith row (including ith row)
int ll = Math.round((i * (i + 1) ));
float[] glass = new float[ll + 2];
// Put all water in first glass
int index = 0;
glass[index] = X;
// Now let the water flow to the
// downward glasses till the row
// number is less than or/ equal
// to i (given row)
// correction : X can be zero for side
// glasses as they have lower rate to fill
for (int row = 1; row <= i ; ++row)
{
// Fill glasses in a given row. Number of
// columns in a row is equal to row number
for (int col = 1;
col <= row; ++col, ++index)
{
// Get the water from current glass
X = glass[index];
// Keep the amount less than or
// equal to capacity in current glass
glass[index] = (X >= 1.0f) ? 1.0f : X;
// Get the remaining amount
X = (X >= 1.0f) ? (X - 1) : 0.0f;
// Distribute the remaining amount
// to the down two glasses
glass[index + row] += X / 2;
glass[index + row + 1] += X / 2;
}
}
// The index of jth glass in ith
// row will be i*(i-1)/2 + j - 1
return glass[(int)(i * (i - 1) /
2 + j - 1)];
}
// Driver Code
public static void main(String[] args)
{
int i = 2, j = 2;
float X = 2.0f; // Total amount of water
System.out.println("Amount of water in jth " +
"glass of ith row is: " +
findWater(i, j, X));
}
}
// This code is contributed by mits
Python3
# Program to find the amount
# of water in j-th glass of
# i-th row
# Returns the amount of water
# in jth glass of ith row
def findWater(i, j, X):
# A row number i has maximum
# i columns. So input column
# number must be less than i
if (j > i):
print("Incorrect Input");
return;
# There will be i*(i+1)/2
# glasses till ith row
# (including ith row)
# and Initialize all glasses
# as empty
glass = [0]*int(i *(i + 1) / 2);
# Put all water
# in first glass
index = 0;
glass[index] = X;
# Now let the water flow to
# the downward glasses till
# the row number is less
# than or/ equal to i (given
# row) correction : X can be
# zero for side glasses as
# they have lower rate to fill
for row in range(1,i):
# Fill glasses in a given
# row. Number of columns
# in a row is equal to row number
for col in range(1,row+1):
# Get the water
# from current glass
X = glass[index];
# Keep the amount less
# than or equal to
# capacity in current glass
glass[index] = 1.0 if (X >= 1.0) else X;
# Get the remaining amount
X = (X - 1) if (X >= 1.0) else 0.0;
# Distribute the remaining
# amount to the down two glasses
glass[index + row] += (X / 2);
glass[index + row + 1] += (X / 2);
index+=1;
# The index of jth glass
# in ith row will
# be i*(i-1)/2 + j - 1
return glass[int(i * (i - 1) /2 + j - 1)];
# Driver Code
if __name__ == "__main__":
i = 2;
j = 2;
X = 2.0;
# Total amount of water
res=repr(findWater(i, j, X));
print("Amount of water in jth glass of ith row is:",res.ljust(8,'0'));
# This Code is contributed by mits
C#
// Program to find the amount
// of water in j-th glass
// of i-th row
using System;
class GFG
{
// Returns the amount of water
// in jth glass of ith row
static float findWater(int i, int j,
float X)
{
// A row number i has maximum i
// columns. So input column
// number must be less than i
if (j > i)
{
Console.WriteLine("Incorrect Input");
Environment.Exit(0);
}
// There will be i*(i+1)/2 glasses
// till ith row (including ith row)
int ll = (int)Math.Round((double)(i * (i + 1)));
float[] glass = new float[ll + 2];
// Put all water in first glass
int index = 0;
glass[index] = X;
// Now let the water flow to the
// downward glasses till the row
// number is less than or/ equal
// to i (given row)
// correction : X can be zero
// for side glasses as they have
// lower rate to fill
for (int row = 1; row <= i ; ++row)
{
// Fill glasses in a given row.
// Number of columns in a row
// is equal to row number
for (int col = 1;
col <= row; ++col, ++index)
{
// Get the water from current glass
X = glass[index];
// Keep the amount less than
// or equal to capacity in
// current glass
glass[index] = (X >= 1.0f) ?
1.0f : X;
// Get the remaining amount
X = (X >= 1.0f) ? (X - 1) : 0.0f;
// Distribute the remaining amount
// to the down two glasses
glass[index + row] += X / 2;
glass[index + row + 1] += X / 2;
}
}
// The index of jth glass in ith
// row will be i*(i-1)/2 + j - 1
return glass[(int)(i * (i - 1) /
2 + j - 1)];
}
// Driver Code
static void Main()
{
int i = 2, j = 2;
float X = 2.0f; // Total amount of water
Console.WriteLine("Amount of water in jth " +
"glass of ith row is: " +
findWater(i, j, X));
}
}
// This code is contributed by mits
PHP
<?php
// Program to find the amount
// of water in j-th glass of
// i-th row
// Returns the amount of water
// in jth glass of ith row
function findWater($i, $j, $X)
{
// A row number i has maximum
// i columns. So input column
// number must be less than i
if ($j > $i)
{
echo "Incorrect Input\n";
return;
}
// There will be i*(i+1)/2
// glasses till ith row
// (including ith row)
// and Initialize all glasses
// as empty
$glass = array_fill(0, (int)($i *
($i + 1) / 2), 0);
// Put all water
// in first glass
$index = 0;
$glass[$index] = $X;
// Now let the water flow to
// the downward glasses till
// the row number is less
// than or/ equal to i (given
// row) correction : X can be
// zero for side glasses as
// they have lower rate to fill
for ($row = 1; $row < $i ; ++$row)
{
// Fill glasses in a given
// row. Number of columns
// in a row is equal to row number
for ($col = 1;
$col <= $row; ++$col, ++$index)
{
// Get the water
// from current glass
$X = $glass[$index];
// Keep the amount less
// than or equal to
// capacity in current glass
$glass[$index] = ($X >= 1.0) ?
1.0 : $X;
// Get the remaining amount
$X = ($X >= 1.0) ?
($X - 1) : 0.0;
// Distribute the remaining
// amount to the down two glasses
$glass[$index + $row] += (double)($X / 2);
$glass[$index + $row + 1] += (double)($X / 2);
}
}
// The index of jth glass
// in ith row will
// be i*(i-1)/2 + j - 1
return $glass[(int)($i * ($i - 1) /
2 + $j - 1)];
}
// Driver Code
$i = 2;
$j = 2;
$X = 2.0; // Total amount of water
echo "Amount of water in jth " ,
"glass of ith row is: ".
str_pad(findWater($i, $j,
$X), 8, '0');
// This Code is contributed by mits
?>
Javascript
<script>
// Program to find the amount
/// of water in j-th glass
// of i-th row
// Returns the amount of water
// in jth glass of ith row
function findWater(i , j, X)
{
// A row number i has maximum i
// columns. So input column
// number must be less than i
if (j > i)
{
document.write("Incorrect Input");
}
// There will be i*(i+1)/2 glasses
// till ith row (including ith row)
var ll = Math.round((i * (i + 1) ));
glass = Array.from({length: ll+2}, (_, i) => 0.0);
// Put all water in first glass
var index = 0;
glass[index] = X;
// Now let the water flow to the
// downward glasses till the row
// number is less than or/ equal
// to i (given row)
// correction : X can be zero for side
// glasses as they have lower rate to fill
for (row = 1; row <= i ; ++row)
{
// Fill glasses in a given row. Number of
// columns in a row is equal to row number
for (col = 1;
col <= row; ++col, ++index)
{
// Get the water from current glass
X = glass[index];
// Keep the amount less than or
// equal to capacity in current glass
glass[index] = (X >= 1.0) ? 1.0 : X;
// Get the remaining amount
X = (X >= 1.0) ? (X - 1) : 0.0;
// Distribute the remaining amount
// to the down two glasses
glass[index + row] += X / 2;
glass[index + row + 1] += X / 2;
}
}
// The index of jth glass in ith
// row will be i*(i-1)/2 + j - 1
return glass[parseInt((i * (i - 1) /
2 + j - 1))];
}
// Driver Code
var i = 2, j = 2;
var X = 2.0; // Total amount of water
document.write("Amount of water in jth " +
"glass of ith row is: " +
findWater(i, j, X));
// This code is contributed by 29AjayKumar
</script>
Producción:
Amount of water in jth glass of ith row is: 0.500000
Complejidad de tiempo: O(i*(i+1)/2) o O(i^2)
Espacio auxiliar: O(i*(i+1)/2) o O(i^2)
Este artículo fue compilado por Rahul y revisado por el equipo de GeeksforGeeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Método 2 (usando BFS transversal)
discutiremos otro enfoque para este problema. Primero, agregamos un triplete (fila, col, rem-agua) en la cola que indica el valor inicial del primer elemento y llena 1 litro de agua. Luego, simplemente aplicamos bfs, es decir, y agregamos triplete izquierdo (fila + 1, col-1, rem-water) y Triplet derecho (fila + 1, col + 1, rem-water) en la cola con la mitad del agua restante en primer triplete y otra mitad en el siguiente triplete.
A continuación se muestra la implementación de esta solución.
C++
// CPP program for above approach
#include<bits/stdc++.h>
using namespace std;
// Program to find the amount
// of water in j-th glass
// of i-th row
void findWater(float k, int i, int j)
{
// stores how much amount of water
// present in every glass
float dp[i+1][2*i + 1];
bool vis[i+1][2*i + 1];
// initialize dp and visited arrays
for(int n=0;n<i+1;n++)
{
for(int m=0;m<(2*i+1);m++)
{
dp[n][m] = 0;
vis[n][m] = false;
}
}
// store Triplet i.e curr-row , curr-col
queue<pair<int,int>>q;
dp[0][i] = k;
// we take the center of the first row for
// the location of the first glass
q.push({0,i});
vis[0][i] = true;
// this while loop runs unless the queue is not empty
while(!q.empty())
{
// First we remove the pair from the queue
pair<int,int>temp = q.front();
q.pop();
int n = temp.first;
int m = temp.second;
// as we know we have to calculate the
// amount of water in jth glass
// of ith row . so first we check if we find solutions
// for the every glass of i'th row.
// so, if we have calculated the result
// then we break the loop
// and return our answer
if(i == n)
break;
float x = dp[n][m];
if(float((x-1.0)/2.0) < 0)
{
dp[n+1][m-1] += 0;
dp[n+1][m+1] += 0;
}
else
{
dp[n+1][m-1] += float((x-1.0)/2.0);
dp[n+1][m+1] += float((x-1.0)/2.0);
}
if(vis[n+1][m-1]==false)
{
q.push({n+1,m-1});
vis[n+1][m-1] = true;
}
if(vis[n+1][m+1]==false)
{
q.push({n+1,m+1});
vis[n+1][m+1] = true;
}
}
if(dp[i-1][2*j-1]>1)
dp[i-1][2*j-1] = 1.0;
cout<<"Amount of water in jth glass of ith row is: ";
// print the result for jth glass of ith row
cout<<fixed<<setprecision(6)<<dp[i-1][2*j-1]<<endl;
}
// Driver Code
int main()
{
//k->water in litres
float k;
cin>>k;
//i->rows j->cols
int i,j;
cin>>i>>j;
// Function Call
findWater(k,i,j);
return 0;
}
// This code is contributed by Sagar Jangra and Naresh Saharan
Java
// Program to find the amount
/// of water in j-th glass
// of i-th row
import java.io.*;
import java.util.*;
// class Triplet which stores curr row
// curr col and curr rem-water
// of every glass
class Triplet
{
int row;
int col;
double rem_water;
Triplet(int row,int col,double rem_water)
{
this.row=row;this.col=col;this.rem_water=rem_water;
}
}
class GFG
{
// Returns the amount of water
// in jth glass of ith row
public static double findWater(int i,int j,int totalWater)
{
// stores how much amount of water present in every glass
double dp[][] = new double[i+1][2*i+1];
// store Triplet i.e curr-row , curr-col, rem-water
Queue<Triplet> queue = new LinkedList<>();
// we take the center of the first row for
// the location of the first glass
queue.add(new Triplet(0,i,totalWater));
// this while loop runs unless the queue is not empty
while(!queue.isEmpty())
{
// First we remove the Triplet from the queue
Triplet curr = queue.remove();
// as we know we have to calculate the
// amount of water in jth glass
// of ith row . so first we check if we find solutions
// for the every glass of i'th row.
// so, if we have calculated the result
// then we break the loop
// and return our answer
if(curr.row == i)
break;
// As we know maximum capacity of every glass
// is 1 unit. so first we check the capacity
// of curr glass is full or not.
if(dp[curr.row][curr.col] != 1.0)
{
// calculate the remaining capacity of water for curr glass
double rem_water = 1-dp[curr.row][curr.col];
// if the remaining capacity of water for curr glass
// is greater than then the remaining capacity of total
// water then we put all remaining water into curr glass
if(rem_water > curr.rem_water)
{
dp[curr.row][curr.col] += curr.rem_water;
curr.rem_water = 0;
}
else
{
dp[curr.row][curr.col] += rem_water;
curr.rem_water -= rem_water;
}
}
// if remaining capacity of total water is not equal to
// zero then we add left and right glass of the next row
// and gives half capacity of total water to both the
// glass
if(curr.rem_water != 0)
{
queue.add(new Triplet(curr.row + 1,curr.col -
1,curr.rem_water/2.0));
queue.add(new Triplet(curr.row + 1,curr.col +
1,curr.rem_water/2.0));
}
}
// return the result for jth glass of ith row
return dp[i-1][2*j-1];
}
// Driver Code
public static void main (String[] args)
{
int i = 2, j = 2;
int totalWater = 2; // Total amount of water
System.out.print("Amount of water in jth glass of ith row is:");
System.out.format("%.6f", findWater(i, j, totalWater));
}
}
// this code is contributed by Naresh Saharan and Sagar Jangra
Python3
# Program to find the amount
# of water in j-th glass of i-th row
# class Triplet which stores curr row
# curr col and curr rem-water
# of every glass
class Triplet:
def __init__(self, row, col, rem_water):
self.row = row
self.col = col
self.rem_water = rem_water
# Returns the amount of water
# in jth glass of ith row
def findWater(i, j, totalWater):
# stores how much amount of water present in every glass
dp = [[0.0 for i in range(2*i+1)] for j in range(i+1)]
# store Triplet i.e curr-row , curr-col, rem-water
queue = []
# we take the center of the first row for
# the location of the first glass
queue.append(Triplet(0,i,totalWater))
# this while loop runs unless the queue is not empty
while len(queue) != 0:
# First we remove the Triplet from the queue
curr = queue.pop(0)
# as we know we have to calculate the
# amount of water in jth glass
# of ith row . so first we check if we find solutions
# for the every glass of i'th row.
# so, if we have calculated the result
# then we break the loop
# and return our answer
if curr.row == i:
break
# As we know maximum capacity of every glass
# is 1 unit. so first we check the capacity
# of curr glass is full or not.
if dp[curr.row][curr.col] != 1.0:
# calculate the remaining capacity of water for curr glass
rem_water = 1-dp[curr.row][curr.col]
# if the remaining capacity of water for curr glass
# is greater than then the remaining capacity of total
# water then we put all remaining water into curr glass
if rem_water > curr.rem_water:
dp[curr.row][curr.col] += curr.rem_water
curr.rem_water = 0
else:
dp[curr.row][curr.col] += rem_water
curr.rem_water -= rem_water
# if remaining capacity of total water is not equal to
# zero then we add left and right glass of the next row
# and gives half capacity of total water to both the
# glass
if curr.rem_water != 0:
queue.append(Triplet(curr.row + 1,curr.col - 1,(curr.rem_water/2)))
queue.append(Triplet(curr.row + 1,curr.col + 1,(curr.rem_water/2)))
# return the result for jth glass of ith row
return dp[i - 1][2 * j - 1]
i, j = 2, 2
totalWater = 2 # Total amount of water
print("Amount of water in jth glass of ith row is:", end = "")
print("{0:.6f}".format(findWater(i, j, totalWater)))
# This code is contributed by decode2207.
C#
// Program to find the amount
/// of water in j-th glass
using System;
using System.Collections.Generic;
class GFG {
// class Triplet which stores curr row
// curr col and curr rem-water
// of every glass
class Triplet {
public int row, col;
public double rem_water;
public Triplet(int row, int col, double rem_water)
{
this.row = row;
this.col = col;
this.rem_water = rem_water;
}
}
// Returns the amount of water
// in jth glass of ith row
public static double findWater(int i, int j, int totalWater)
{
// stores how much amount of water present in every glass
double[,] dp = new double[i+1,2*i+1];
// store Triplet i.e curr-row , curr-col, rem-water
List<Triplet> queue = new List<Triplet>();
// we take the center of the first row for
// the location of the first glass
queue.Add(new Triplet(0,i,totalWater));
// this while loop runs unless the queue is not empty
while(queue.Count > 0)
{
// First we remove the Triplet from the queue
Triplet curr = queue[0];
queue.RemoveAt(0);
// as we know we have to calculate the
// amount of water in jth glass
// of ith row . so first we check if we find solutions
// for the every glass of i'th row.
// so, if we have calculated the result
// then we break the loop
// and return our answer
if(curr.row == i)
break;
// As we know maximum capacity of every glass
// is 1 unit. so first we check the capacity
// of curr glass is full or not.
if(dp[curr.row,curr.col] != 1.0)
{
// calculate the remaining capacity of water for curr glass
double rem_water = 1-dp[curr.row,curr.col];
// if the remaining capacity of water for curr glass
// is greater than then the remaining capacity of total
// water then we put all remaining water into curr glass
if(rem_water > curr.rem_water)
{
dp[curr.row,curr.col] += curr.rem_water;
curr.rem_water = 0;
}
else
{
dp[curr.row,curr.col] += rem_water;
curr.rem_water -= rem_water;
}
}
// if remaining capacity of total water is not equal to
// zero then we add left and right glass of the next row
// and gives half capacity of total water to both the
// glass
if(curr.rem_water != 0)
{
queue.Add(new Triplet(curr.row + 1,curr.col -
1,curr.rem_water/2.0));
queue.Add(new Triplet(curr.row + 1,curr.col +
1,curr.rem_water/2.0));
}
}
// return the result for jth glass of ith row
return dp[i - 1, 2 * j - 1];
}
static void Main() {
int i = 2, j = 2;
int totalWater = 2; // Total amount of water
Console.Write("Amount of water in jth glass of ith row is:");
Console.Write(findWater(i, j, totalWater).ToString("0.000000"));
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Program to find the amount
/// of water in j-th glass
// of i-th row
// class Triplet which stores curr row
// curr col and curr rem-water
// of every glass
class Triplet
{
constructor(row,col,rem_water)
{
this.row=row;
this.col=col;
this.rem_water=rem_water;
}
}
// Returns the amount of water
// in jth glass of ith row
function findWater(i,j,totalWater)
{
// stores how much amount of water present in every glass
let dp = new Array(i+1);
for(let k=0;k<dp.length;k++)
{
dp[k]=new Array((2*i)+1);
for(let l=0;l<dp[k].length;l++)
{
dp[k][l]=0;
}
}
// store Triplet i.e curr-row , curr-col, rem-water
let queue = [];
// we take the center of the first row for
// the location of the first glass
queue.push(new Triplet(0,i,totalWater));
// this while loop runs unless the queue is not empty
while(queue.length!=0)
{
// First we remove the Triplet from the queue
let curr = queue.shift();
// as we know we have to calculate the
// amount of water in jth glass
// of ith row . so first we check if we find solutions
// for the every glass of i'th row.
// so, if we have calculated the result
// then we break the loop
// and return our answer
if(curr.row == i)
break;
// As we know maximum capacity of every glass
// is 1 unit. so first we check the capacity
// of curr glass is full or not.
if(dp[curr.row][curr.col] != 1.0)
{
// calculate the remaining capacity of water for curr glass
let rem_water = 1-dp[curr.row][curr.col];
// if the remaining capacity of water for curr glass
// is greater than then the remaining capacity of total
// water then we put all remaining water into curr glass
if(rem_water > curr.rem_water)
{
dp[curr.row][curr.col] += curr.rem_water;
curr.rem_water = 0;
}
else
{
dp[curr.row][curr.col] += rem_water;
curr.rem_water -= rem_water;
}
}
// if remaining capacity of total water is not equal to
// zero then we add left and right glass of the next row
// and gives half capacity of total water to both the
// glass
if(curr.rem_water != 0)
{
queue.push(new Triplet(curr.row + 1,curr.col -
1,(curr.rem_water/2)));
queue.push(new Triplet(curr.row + 1,curr.col +
1,(curr.rem_water/2)));
}
}
// return the result for jth glass of ith row
return dp[i-1][2*j-1];
}
// Driver Code
let i = 2, j = 2;
let totalWater = 2; // Total amount of water
document.write("Amount of water in jth glass of ith row is:");
document.write(findWater(i, j, totalWater).toFixed(6));
// This code is contributed by rag2127
</script>
Producción
Amount of water in jth glass of ith row is:0.500000
Complejidad del tiempo: O(2^i)
Complejidad espacial: O(i^2)
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA