Ronda 1ª-2: Juego de monedas

Enunciado original

En resumen el problema trata de lo siguiente: tenemos un número de monedas (K) que podemos distribuir en una cantidad de botes (N) de la manera que queramos. Sabiendo cuántas monedas metimos en cada bote pero sin saber en qué botes las metimos se trata de saber el número mínimo de veces que tendremos que meter la mano en los botes (P) para sacar una cantidad de monedas (C) obviamente menor que la cantidad de monedas totales. A este problema se le asignaron 20 puntos. Es también un problema sencillo y en el que prácticamente con la explicación de los ejemplos te dan muchas pistas sobre la estrategia a seguir.

El número de movivimientos (P) serán la suma de los movimientos correctos, o sea en los que encontremos moneda en el bote, que serán C, es decir las monedas a sacar, más los movimientos incorrectos, o sea en los que no encontremos moneda en el bote.

Así que se trata de minimizar el número de veces que podemos fallar.

Podremos fallar tantas veces como botes haya con menos monedas que el que más tenga porque no vamos a fallar más de una vez en cada bote ni vamos a intentar sacar más monedas de un bote que las que hay en el bote que más tenga. Así que la idea es dejar el mayor número de botes con las mismas monedas (en estos botes no fallaremos nunca) y unos pocos con menos.

Se pueden seguir muchas estrategias pero la que yo elegí es repartir las monedas entre los botes (r=K/N). Recordad que en la división de enteros r*N<=K, es decir no redondea el resultado sino que lo trunca. Es lo mismo que si hiciéramos la división a mano, vamos.

Si meto r*N>=C puedo meter r o más monedas en cada bote y al sacarlas no fallar nunca porque en cuanto sacase r monedas de un bote pasaría al siguiente. En este caso, como el número de fallos es cero, el número de movimientos es igual al número de monedas a sacar (C).

Si no tengo tantas monedas la mejor solución es meter en cada bote r+1 monedas. El número de botes que puedo llenar con r+1 monedas será K/(r+1). Estos serán los botes en los que no fallo, así que podré fallar en los restantes botes. Así que el número de movimientos será C+(N-K/(r+1)).

Como se ve un problema más de lógica que de programación.

Alguien, al leer la anterior argumentación, podría objetar que si el resto de la división K/N fuera cero no sería bueno repartir r+1 monedas en cada bote sino r, y estaría en lo cierto. Lo que ocurre es que si el resto de la división es cero r*N=K y como K>=C entonces r*N>=C y estaríamos en el primer caso contemplado.

Aunque sea extremadamente simple aquí está el listado completo del programa y aquí el fichero de datos propuesto en el concurso.