1054 - Galbeni

Cerința

După ce au descoperit ascunzătoarea piratului Spânu, marinarii de pe corabia “Speranţa” au hotărât să ofere sătenilor o parte din comoara acestuia. Întrucât comoara avea un număr nelimitat de bani din aur, numiţi galbeni, singura problemă a marinarilor a fost regula după care să împartă banii.

După îndelungi discuţii au procedat astfel: i-au rugat pe săteni să se aşeze în ordine la coadă şi să vină, pe rând, unul câte unul pentru a-şi ridica galbenii cuveniţi. Primul sătean a fost rugat să îşi aleagă numărul de galbeni, cu condiţia ca acest număr să fie format din exact K cifre. Al doilea sătean va primi un număr de galbeni calculat astfel: se înmulţeşte numărul de galbeni ai primului sătean cu toate cifrele nenule ale acelui număr, rezultatul se înmulţeşte cu 8 şi apoi se împarte la 9 păstrându-se doar ultimele K cifre ale câtului împărţirii. Dacă numărul obţinut are mai puţin de K cifre, atunci acestuia i se adaugă la final cifra 9, până când se completează K cifre.

Pentru a stabili câţi galbeni primeşte al treilea sătean, se aplică aceeaşi regulă, dar pornind de la numărul de galbeni ai celui de-al doilea sătean. Regula se aplică în continuare fiecărui sătean, plecând de la numărul de galbeni primiţi de săteanul care a stat la coadă exact în faţa lui.

Cunoscând numărul de galbeni aleşi de primul sătean, determinaţi numărul de galbeni pe care îl va primi al N-lea sătean.

Date de intrare

Fișierul de intrare galbeni.in conține pe prima linie cele 3 numere naturale nenule S, K, N separate prin câte un spaţiu, unde S reprezintă numărul de galbeni ales de primul sătean, K este numărul de cifre ale numărului S, iar N reprezintă numărul de ordine al săteanului pentru care se cere să determinaţi numărul de galbeni primiţi.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

Pe următorul rând se va afișa un număr natural reprezentând rezultatul determinat.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 2 ≤ N ≤ 1 000 000 000
• 1 ≤ K ≤ 3

• Se garantează că S are exact K cifre.

Exemplu 1

Intrare

51 2 3

Ieșire

Datele de intrare corespund restricțiilor impuse.

77

Explicație

Primul sătean a luat 51 de galbeni. Cel de al doilea sătean va primi 26 de galbeni

(51 se înmulţeşte cu cifrele nenule 51*5*1=255, 255 se înmulţeşte cu 8 =2040. Câtul împărţirii lui 2040 la 9 este 226, ultimele două cifre fiind 26).

Cel de al treilea sătean va primi 77 de galbeni (26 se înmulţeşte cu cifrele nenule 26*2*6=312, 312 se înmulţeşte cu 8 şi obţinem numărul 2496. Câtul împărţirii dintre 2469 şi 9 este 277, ultimele două cifre fiind 77)

Exemplu 2

Intrare

10 2 3

Ieșire

Datele de intrare corespund restricțiilor impuse.

96

Explicație

Primul sătean primeşte 10 galbeni. Pentru a calcula câţi galbeni primeşte al doilea sătean procedăm astfel: înmulţim 10 cu cifele sale nenule: 10*1 = 10, apoi cu 8,

10*8 = 80. Câtul împărţirii lui 80 la 9 este 8. Acest număr având mai puţin de K=2 cifre, se adaugă la finalul său cifra 9 şi se obţine 89.

Pentru al treilea sătean se pleacă de la 89 (89*8*9=6408, 6408*8=51264, câtul împărţirii lui 51264 la 9 este 5696, ultimele două cifre sunt 96)

Exemplu 3

Intrare

1234 4 4

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

#1054 Galbeni

def conditii(prim_satean, cifre_prim_satean, nth_satean):
    restrictii = (
        len(str(prim_satean)) == cifre_prim_satean,
        1 <= cifre_prim_satean <= 3,
        2 <= nth_satean <= 1_000_000_000
    )

    return all(restrictii)


def calcul_galbeni(s, cifre_s):
    # Extragem din s toate cifrele nenule
    cifre_nenule = [int(x) for x in list(str(s)) if int(x) > 0]
    # Le înmulțim cu s și apoi cu 8, după care le împărțim la 9, conform enunțului
    produs = s
    for cif in cifre_nenule:
        produs *= cif
    produs *= 8
    cat = produs // 9
    # Adăugăm suficienți "9" la finalul variabile 'cat' până când acesta are cifre_s cifre
    while len(str(cat)) < cifre_s:
        cat = str(cat)+"9"
    # Secționăm string-ul și returnăm ultimele cifre_s cifre
    return int(str(cat)[-cifre_s:])


def galbeni(prim_satean, cifre_prim_satean, nth_satean):
    suma = prim_satean
    # Pentru fiecare sătean (până la al n-lea sătean), calculăm suma galbenilor
    for i in range(nth_satean - 1):
        suma = calcul_galbeni(suma, cifre_prim_satean)

    # Ultima sumă calculată (la ieșirea din for loop) este suma de galbeni pe care am vrut să o determinăm
    print(suma)


if __name__ == "__main__":
    prim_satean, cifre_prim_satean, nth_satean = [int(x) for x in input().split()]

    if not conditii(prim_satean, cifre_prim_satean, nth_satean):
        print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        print("Datele de intrare corespund restricțiilor impuse.")
        galbeni(prim_satean, cifre_prim_satean, nth_satean)