CyM2005, Ronda Nacional, Problema 2

CyM2005, Ronda Nacional, Problema 2

Rodrigo Belfiore 09 Nov 2007 18:03

Con el segundo tuve problemas, primero 1,2,4,8,16,32,64 era solucion ya que todo nro menor que 100 se puede pasar a base 2 con 7 o menos digitos y entonces tendria la manera de pagar. Entonces use 7 for (a,b,c,d,e,f,g) que irian variando segun el valor de la moneda a,b,c,d,e,f,g. Despues para cada precio (array p) podia usarse o no usarse cada una de las 7 monedas, si se podia armar la suma que diera todos los precios (i) entonces sirve=1, sino sirve=0. Despues los conté, pero no me daba el tiempo y tuve que suponer sin razon que a=1 y b=2 y que las demas no superaban los 50. No se como justificar esto o cómo optimizarlo mejor.
El código: http://rodrigobelfiore.com.ar/cym/codigos/?id=2005r3n3e2

Re: CyM2005, Ronda Nacional, Problema 2

pabloh 10 Nov 2007 20:09

Ok, voy a ir por partes para que no me queden tan largos los mensajes :-) (Por cierto, el enunciado puede verse en el archivo de enunciados.)

Primero, el enunciado pide “¿cuál es la menor cantidad de monedas?”, y con un ejemplo mostrás que el mínimo es menor o igual a 7. Por si alguien más lee esto, lo de “base 2” es porque las monedas son potencia de dos, usarla es como multiplicarla por 1 y no usarla es como multiplicarla por 0, por lo tanto toda combinación de monedas (que se usan sin repetir) es como un número en binario.

Bien. Vamos a lo del final, cómo justificar. Si no tenés una moneda que vale 1 centavo, no podés pagar exactamente el precio 1 centavo porque todas las demás monedas valen más de 1 centavo; por lo tanto es necesaria. Con la de 2 centavos es similar: si no la tenés, no podés pagar exactamente el precio 2 centavos, porque aunque tengas la de 1 centavo no la podés repetir.

¿Qué más se puede decir por este camino? Lo que estamos viendo es cómo hacer para pagar exactamente un determinado precio. Para 1 y 2 centavos la única forma es tener esas monedas. Para 3 centavos hay dos opciones: tener una moneda de 3 centavos o hacer 1+2. Para 4 centavos, podemos tener una moneda de 4 centavos, o hacer 1+3. Y así siguiendo. Las potencias de 2 se obtienen si uno trata de elegir siempre la moneda de mayor valor posible: la de 3 se puede formar, así que la salteo; con 1 y 2 no puedo formar 4 centavos, así que la incluyo; con 1,2,4 puedo formar todos los precios hasta 7 centavos inclusive, así que la siguiente moneda es la de 8 centavos; etc.

Intentemos buscar otro conjunto de monedas. Digamos que uso la de 3 centavos.
Con la moneda de 1 centavo puedo formar los precios: 1.
Si además tengo la moneda de 2 centavos, además puedo formar los precios: 2, 1+2=3.
Si además tengo la moneda de 3 centavos, además puedo formar los precios: 3, 1+3=4, 2+3=5, 3+3=6.
Ahora puedo elegir entre las monedas de 4, 5, 6 y 7 centavos, pero no más, porque si no nunca voy a poder pagar exactamente 7 centavos (estoy suponiendo que elijo las monedas en orden creciente).
Digamos que elijo la de 5 centavos, porque me gusta el 5.
Si además tengo la moneda de 5 centavos, además puedo formar los precios: 5, 1+5=6, 2+5=7, 3+5=8, 4+5=9, 1+2+3+5=5+5=10, 6+5=11.

Los dejo seguir a ustedes. :-)

Segunda parte

pabloh 10 Nov 2007 22:59

¿Qué otra relación podemos encontrar?

Supongamos que $m_1, m_2, m_3, \ldots, m_k$ son un conjunto de monedas que permite pagar exactamente todos los precios de 1 a 99 ambos inclusive, usando cada moneda a lo sumo una vez. Supongamos que están ordenadas de menor a mayor.

Entonces obviamente $1 \leq m_1 < m_2 < m_3 < \ldots < m_k \leq 99$. Consideremos ahora la moneda del lugar $j$. Con la moneda $m_j$ y todas las mayores a esa solamente se pueden pagar precios mayores o iguales a esa moneda, $m_j$. Por lo de arriba, cualquier precio menor a $m_j$ se puede pagar exactamente. Y necesariamente eso ha de lograrse usando solamente algunas de las monedas menores a $m_j$, o sea $m_1, m_2, m_3, \ldots, m_{j-1}$. Pero el mayor precio que puede pagarse usando solamente esas monedas es usarlas todas, o sea $m_1 + m_2 + m_3 + \ldots + m_{j-1}$. Por lo tanto

(1)

\begin{align} m_1 + m_2 + m_3 + \ldots + m_{j-1} \geq m_j - 1 \end{align}

(Porque si fuera menor estricto no habría forma de pagar el precio $m_j - 1$.) Esto nos da una cota para el valor de $m_j$. No hace falta que los ciclos for busquen más allá.