1004 - Eureni

Cerinţa

Pentru cadourile pe care Moş Crăciun urmează să le cumpere copiilor cuminţi, Consiliul Polului Nord a alocat suma de S eureni. Ştiind că în comerţul polar se utilizează n+1 tipuri de bancnote de valori 1, e¹ , e², e³,…, eⁿ şi faptul că Moşul trebuie să primească un număr minim de bancnote pentru suma aprobată, să se determine numărul de bancnote din fiecare tip utilizat în plata sumei şi numărul total de bancnote care i s-au alocat.

Date de intrare

Fișierul de intrare eureniin.txt conține pe prima linie numerele naturale S n e.

Date de ieşire

Fișierul de ieșire eureniout.txt va conține mai multe linii: pe fiecare linie va fi scrisă valoare unei bancnote folosită în plata sumei S și numărul de bancnote folosite, separate printr-un spațiu, în ordinea descrescătoare a valorilor bancnotelor folosite. Pe ultima linie se va scrie numai numărul total de bancnote folosite.

Restricții și precizări

• 1 < S < 2 000 000 000
• 1 < n < 10
• 1 < e < 10
• se presupune că există un număr nelimitat de bancnote de fiecare tip

Exemplul 1

eureniin.txt

107 4 5

eureniout.txt

Datele de intrare corespund restrictiilor impuse.
25 4
5 1
1 2
7

Explicație

Sunt 5 tipuri de bancnote, cu valorile: 1, 5, 25, 125, 625 eureni. Pentru a plăti suma de 107 eureni se folosesc 4 bancnote de 25 eureni, 1 bancnotă de 5 eureni și 2 bancnote de 1 euren, în total 7 bancnote.

Exemplul 2

eureniin.txt

grudmgvyem

eureniout.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. Funcția de validare verifică dacă datele de intrare sunt în intervalul specificat

def validare(s_validare, n_validare, e_validare):

   # Verificăm dacă S, n și e sunt în intervalul specificat
   if (s_validare <= 1 or s_validare > 2000000000 or
           n_validare <= 1 or n_validare > 10 or e_validare <= 1 or e_validare > 10):
       raise ValueError  # Ridicăm o eroare dacă S, n sau e nu sunt în intervalul specificat
   file_out.write("Datele de intrare corespund restrictiilor impuse.\n")

def calculeaza_bancnote(s_calc, n_calc, e_calc):

   # Calculăm valorile bancnotelor
   bancnote = [e_calc ** index for index in range(n_calc + 1)]
   # Inițializăm numărul de bancnote din fiecare tip cu 0
   nr_bancnote = [0] * (n_calc+1)
   # Calculăm numărul de bancnote din fiecare tip
   for index in range(n_calc, -1, -1):
       nr_bancnote[index] = s_calc // bancnote[index]
       s_calc %= bancnote[index]
   return nr_bancnote

if __name__ == '__main__':

   file_in = open("eureniin.txt", "r")
   file_out = open("eureniout.txt", "w")

   try:
       # Citim S, n și e
       S_main, n_main, e_main = map(int, file_in.readline().split())
       # Validăm datele de intrare
       validare(S_main, n_main, e_main)
       # Calculăm numărul de bancnote din fiecare tip
       nr_bancnote_main = calculeaza_bancnote(S_main, n_main, e_main)
       # Scriem numărul de bancnote din fiecare tip în fișierul de ieșire
       for i in range(n_main, -1, -1):
           if nr_bancnote_main[i] > 0:
               file_out.write(str(e_main ** i) + ' ' + str(nr_bancnote_main[i]) + '\n')
       # Scriem numărul total de bancnote în fișierul de ieșire
       file_out.write(str(sum(nr_bancnote_main)) + '\n')

   # Dacă datele de intrare nu sunt valide, afișăm un mesaj de eroare
   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse.")
   # Dacă datele de intrare sunt incomplete, afișăm un mesaj de eroare
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>