Pista 1

Cada cantidad final de ingrediente está definida como una potencia de \(2\), es decir:

\(a_i = 2^{b_i}\)

Pista 2

Las potencias de \(2\) tienen la propiedad de que cada valor es único y no puede obtenerse como suma de otras potencias de \(2\) distintas.

Solución

Para cada caso de prueba se construye implícitamente una lista \(A\), donde cada elemento es una potencia de \(2\). El objetivo es determinar si existen dos subarreglos contiguos, no traslapados, cuya suma sea exactamente la misma.

Gracias a la unicidad de las potencias de \(2\), se cumple una propiedad fundamental:

• La suma de un subarreglo está determinada de manera única por los exponentes que contiene.
• Dos subarreglos distintos solo pueden tener la misma suma si contienen exactamente las mismas potencias.

Dado que los subarreglos no se traslapan, esto solo es posible si existe al menos un ingrediente cuya cantidad \(bᵢ\) aparezca más de una vez en la lista original. En ese caso, se pueden formar dos subarreglos de un solo elemento con la misma suma:

\(2^{b_i} = 2^{b_i}\)

Por lo tanto, el problema se reduce a verificar si existe algún valor repetido en la lista \(B\).

Procedimiento

1. Leer las cantidades \(bᵢ\).
2. Contar cuántas veces aparece cada valor.
3. Si algún valor aparece al menos dos veces, el ponche es muy delicioso.
4. En caso contrario, es solo delicioso.

Implementación en C++

Un_Ponche_Muy_Delicioso.cpp

Complejidad

• Tiempo: Para cada caso de prueba, el algoritmo recorre la lista una sola vez, por lo que la complejidad es \(O(N)\). Dado que hay T casos de prueba, la complejidad es \(O(T \cdot N)\).
• Memoria: El uso de memoria es \(O(N)\).