Resto

Resto

Medio

Introduzione

Nel mistico villaggio di Coinholt sei dietro il bancone della tua panetteria e stai sistemando una nuova infornata di pasticcini. La porta si apre cigolando ed entra Denara, una mercante esperta con un occhio attento per la merce di qualità. Dopo un pasto veloce, fa scivolare sul bancone una moneta scintillante, che rappresenta un valore di 100 unità.

Sorridi, prendi la moneta e dai un'occhiata al costo totale del pasto: 88 unità. Questo significa che devi restituire 12 unità di resto.

Denara tende la mano, in attesa. «Dammi solo il minor numero di monete», dice con un sorriso. «La mia borsa è già piena e non voglio rischiare di perderle per strada.»

Sai di avere qualche opzione. «Per il resto abbiamo Lumis (dal valore di 10 unità), Viras (dal valore di 5 unità) e Zenth (dal valore di 2 unità).»

Calcoli rapidamente le possibilità a mente:

  • una Lumis (1 × 10 unità) + uno Zenth (1 × 2 unità) = 2 monete in totale
  • due Viras (2 × 5 unità) + uno Zenth (1 × 2 unità) = 3 monete in totale
  • sei Zenth (6 × 2 unità) = 6 monete in totale

«La scelta migliore è due monete: una Lumis e uno Zenth», dici, porgendole il resto.

Denara sorride, chiaramente impressionata. «Come sempre, ci hai preso.»

Istruzioni

Determina il minor numero di monete da dare a un cliente in modo che la somma dei loro valori sia pari all'importo esatto del resto.

Esempi

  • Un importo di 15 con i valori delle monete disponibili [1, 5, 10, 25, 100] dovrebbe restituire una moneta da 5 e una moneta da 10, ovvero [5, 10].
  • Un importo di 40 con i valori delle monete disponibili [1, 5, 10, 25, 100] dovrebbe restituire una moneta da 5, una moneta da 10 e una moneta da 25, ovvero [5, 10, 25].
Modifica tramite GitHub Il link si apre in una nuova finestra o scheda
OCaml Exercism

Vuoi iniziare Resto?

Iscriviti a Exercism per imparare e padroneggiare OCaml con 60 esercizi e il mentoring di persone reali, tutto gratis.