Los sistemas monetarios terrícolas suelen ser de tipo canónico. Eso significa que dada una cantidad de dinero a devolver, el algoritmo voraz que consiste en elegir primero la moneda de mayor valor posible que sea menor o igual que la cantidad a devolver, y aplicar el mismo algoritmo a la cantidad restante, iterativamente, nos da el mínimo número de monedas con el que podemos devolver la cantidad.

Contrariamente a lo que la mayoría de la gente piensa, en Marte hay vida inteligente. Tienen una sociedad altamente desarrollada, pero un curioso sistema monetario. Tienen monedas y billetes, como nosotros. El billete más pequeño es el papelín. Y sus monedas tienen cinco denominaciones. La más pequeña es la china, y un papelín vale 100 chinas. El resto de monedas son:

• 1 guijarro = 3 chinas
• 1 piedra = 11 chinas
• 1 pedrusco = 22 chinas
• 1 menhir = 47 chinas

Monedero marciano con chinas, guijarros y piedras

Por ejemplo, el mínimo número de monedas con valor igual a un papelín es cuatro: dos menhires y dos guijarros.

La entrada del problema consiste en una o más líneas. Cada línea contiene el precio de un artículo en chinas, comprendido entre 1 y 100, ambos incluidos. Para cada artículo el programa debe escribir una línea que describa el mínimo número de monedas necesarias para devolver el cambio, si se paga el artículo con un papelín.

Ejemplo de entrada:

77
34
99
57
13

Ejemplo de salida:

0 menhires, 1 pedrusco, 0 piedras, 0 guijarros, 1 china
0 menhires, 3 pedruscos, 0 piedras, 0 guijarros, 0 chinas
0 menhires, 0 pedruscos, 0 piedras, 0 guijarros, 1 china
0 menhires, 1 pedrusco, 1 piedra, 3 guijarros, 1 china
1 menhir, 1 pedrusco, 1 piedra, 2 guijarros, 1 china

Marciano arruinado

Fuente: aquí (fuente “desaparecida”; accesible en la waybackmachine)