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

# 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.")