Problema 3
McNuggets
mcn.pas, mcn.c, mcn.cpp
Problema
Juanito Come Todo, va a hacer una fiesta en su casa dándole Nuggets de pollo a sus invitados. Juanito sabe exactamente la cantidad de Nuggets que comen cada uno de sus comensales, además sabe que en un restaurante muy famoso (el del payasito), en cada una de las cajas de Nuggets pueden venir 6, 9 o 20 piezas. Tu tarea es ayudarle a calcular la cantidad mínima de paquetes que debe comprar para obtener la cantidad exacta Nuggets.
Por ejemplo si requiere de 38 Nuggets podría comprar una caja con veinte y tres cajas con 6 (en total 4 cajas) o también comprar una caja con 20 y dos con 9 (en total 3 cajas). En caso de que sea imposible deberás indicarlo.
Nota: Los números que se pueden expresar como la suma de 6, 9 y 20 se les llama McNuggets.
Entrada
Un solo número n, la cantidad de McNuggets que quiere comprar. 0 ≤ n ≤ 30000
Salida
Si no puede comprar la cantidad exacta deberás escribir “NO SE PUEDE”.
En caso de que pueda comprar exactamente n Nuggets deberás escribir 3 números a, b y c separados por un espacio, siendo a, b y c la cantidad de cajas con 20, 9 y 6 Nuggets respectivamente, de tal forma a + b + c = n sea mínima. En caso de que existan varias soluciones que den el valor de n, deberás escribir la que tenga mayor cantidad de cajas de 20 Nuggets.
Ejemplo
entrada | salida |
38 | 1 2 0 |
23 | NO SE PUEDE |
Concurso: | ICPC - 7 Concurso Interno de la Universidad Bonaterra. 11/Mayo/2007 |
Propuesto por: | Óscar Dávalos Orozco |
Ayuda: | entradas, salidas, sugerencias |
Soluciones: | mcn.pas, mcn.c, mcn.cpp |