0
279
VistasAgregar agua a la pila de vasos
Siempre quise saber si existe alguna aplicación real del triángulo de Pascal además de los coeficientes de la expansión binomial.
Traté de resolver este problema:
Pero, ¿qué sucede si estoy agregando K unidades de agua y quiero encontrar un vaso que tenga la menor cantidad de agua?
Donde, Glass se encontrará como: c -th glass en r -th fila
Y yo creo. Si pudiéramos encontrar esto, entonces no sería difícil para nosotros encontrar la cantidad de agua en cualquier vaso para el cual {i<r and j<c}
Problema:
Entrada Agua añadida- K unidades y capacidad de cada vaso como 1- unidad
Salida esperada :
cth vaso enrfila que tiene menos agua en él.
Traté de resolver el problema tomando nota de la capacidad de cada fila cuando comienza a desbordarse: y quiero saber cómo continuar con este método.
1 max = 1, cap = 1 1 1 max = 1, sum(coefficients)=2**1 = 2, cap = 2/1 1 2 1 max = 2, sum = 2**2, cap = 4/2 = 2 units 1 3 3 1 max = 3, sum = 2**3, cap = 8/3 units 1 4 6 4 1 max = 6, sum = 2**4, cap = 16/6 units#No estoy seguro, pero así me parece por la tasa @a la que se le está agregando agua.
1 1/2 1/2 1/4 2/4 1/4 1/8 3/8 3/8 1/8 1/16 4/16 6/16 4/16 1/16¿Debo usar la lista 2-D y definir como:
Δ1, Δ2 = 0, 0 if g(n-1, k)>1 and k <= n-1: Δ1 = g(n-1, k) -1 if g(n-1, k-1)>1 and k-1 <= n-1: Δ2 = g(n-1, k-1) - 1 g(n, k) = Δ1/2 + Δ2/2 g(n,k) = g(n-1, k-1) + g(n-1, k)
g = [[0]*(i+1) for i in range(11)] def f(g, K): g[1][1] += 1 K = K-1 d1, d2 = 0, 0 for n in range(2, 10): for k in range(1, n+1): if k ==1: g[n][k] = g[n-1][k]/2 if k == n: g[n][k] = g[n-1][k-1]/2 else: if g[n-1][k-1]>1: d1 = g[n-1][k-1] -1 if g[n-1][k] > 1: d2 = g[n-1][k] -1 g[n][k] = d1/2 + d2/2 return g, K k = int(input()) while k: g, k = f(g, k) for x in g: print(x)no se que falta?
2 Respuestas
Responde la pregunta0
Para una restricción K tan pequeña, el llenado simple fila por fila es suficiente (solo podemos almacenar dos filas, aquí se usa la lista 2D por simplicidad)
def fillGlasses(k, row, col): gl = [[k]] level = 1 overflow_occured = True while overflow_occured: # also can stop when at needed row print(gl[level-1]) #before overflow level += 1 overflow_occured = False gl.append([0]*level) for i in range(level - 1): t = gl[level-2][i] - 1 if t > 0: gl[level-1][i] += t/2 gl[level-1][i+1] += t/2 gl[level-2][i] = 1 overflow_occured = True #print(gl) #after all return gl[row-1][col-1] print(fillGlasses(21,8,4)) [21] [10.0, 10.0] [4.5, 9.0, 4.5] [1.75, 5.75, 5.75, 1.75] [0.375, 2.75, 4.75, 2.75, 0.375] [0, 0.875, 2.75, 2.75, 0.875, 0] [0, 0, 0.875, 1.75, 0.875, 0, 0] [0, 0, 0, 0.375, 0.375, 0, 0, 0] 0.3750
Supuse que estaba haciendo exactamente esta pregunta de juez en línea, o una muy similar: https://practice.geeksforgeeks.org/problems/champagne-overflow2636/1
Si es así, en realidad las restricciones para R y C son solo 500 y cualquier simulación podría funcionar. Un pequeño inconveniente es que puede haber agua en una fila, incluso la fila anterior no está completamente llena. Puede considerar pequeños casos de prueba y simular para averiguar, por ejemplo, K = 6 , las gafas se verán así:
1 1, 1 0.75, 1, 0.75 0, 0.25, 0.25, 0 // Notice previous row is not fully filled, makes sense as "middle" glasses will overflow fasterCreo que en cuanto a la implementación, es similar para el enfoque de arriba hacia abajo y de abajo hacia arriba. Aquí está mi código aceptado de arriba hacia abajo que simplemente simula el proceso de vertido y desbordamiento de agua, con C ++, el mismo algoritmo se puede implementar en cualquier idioma:
class Solution { public: double cups[505][505]; void pourWaterAt(double K, int R, int C, int targetR){ if(R > targetR) return; cups[R][C] += K; if(cups[R][C] > 1){ double overflow = cups[R][C] - 1; cups[R][C] = 1; pourWaterAt(overflow/2.0f, R+1, C, targetR); pourWaterAt(overflow/2.0f, R+1, C+1, targetR); } } double waterOverflow(int K, int R, int C) { memset(cups, 0, sizeof(cups)); pourWaterAt(K, 1, 1, R); return cups[R][C]; } }; Después de la simulación, puede escanear cups[R][C] y encontrar el positivo más pequeño (y su índice) para obtener la respuesta.