1083 - Sir 5

Sursa: [1]

---

Cerinţa

Se generează un şir de numere naturale ai cărui primi termeni sunt, în ordine:1, 12, 21, 123, 231, 312, 1234, 2341, 3412, 4123, 12345, 23451,...
Deduceţi regula după care sunt generaţi termenii şirului şi scrieţi un program care să citească numerele naturale k, x, a şi b şi care să determine: a) ultima cifră a sumei tuturor termenilor şirului care sunt formaţi din cel mult k cifre; b) succesorul termenului x în şirul dat, x fiind un termen al şirului; c) numărul de termeni ai şirului care au cifra cea mai semnificativă egală cu a şi nu conţin în scrierea lor cifra b.

Date de intrare

Fișierul de intrare sir5.in conţine o singură linie pe care sunt scrise cele patru numere naturale k, x, a şi b, separate prin câte un spaţiu.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi, fișierul de ieșire sir5.out va conține 3 linii: pe prima linie se va scrie un număr natural reprezentând ultima cifră a sumei tuturor termenilor şirului care sunt formaţi din cel mult k cifre; pe a doua linie se va scrie un număr natural reprezentând succesorul termenului x în şirul dat; pe a treia linie se va scrie un număr natural reprezentând numărul de termeni ai şirului care au cifra cea mai semnificativă egală cu a şi nu conţin în scrierea lor cifra b. În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse."'.

Restricţii şi precizări

• Numerele k, x, a şi b sunt naturale nenule
• 1 ≤ k ≤ 9
• x este un termen al şirului din enunţ şi are succesor în şir
• succesorul termenului x în şir este termenul care urmează imediat după x (de exemplu, dacă x=2341 atunci succesorului lui x în şir este 3412)
• 1 ≤ x < 900000000
• 1 ≤ a ≤ 9; 1 ≤ b ≤ 9; a ≠ b'
• cifra cea mai semnificativă a unui număr natural este prima cifră din scrierea sa, de la stânga la dreapta (de exemplu cifra cea mai semnificativă a numărului 32156 este 3)

Exemple

Exemplul 1

sir5.in

3 45123 3 6

Ecran

Datele sunt introduse corect.

sir5.out

0

51234

3

Rezolvare

# 1083

def genereazaSir(n):
    sir = [1]
    while len(sir) < n:
        lastTerm = sir[-1]
        newTerm = int(str(lastTerm)[::-1])
        for i in range(len(str(lastTerm))):
            if newTerm % 10 == 1:
                newTerm //= 10
            else:
                break
        sir.append(newTerm)
    return sir


def sumaTermeniMici(n, k):
    sir = genereazaSir(n)
    suma = 0
    for termen in sir:
        if termen <= 10 ** k - 1:
            suma += termen
    return suma % 10


def succesorulTermenului(x):
    sir = genereazaSir(x + 1)
    return sir[x]


def numaraTermeniCuA(a, b):
    sir = genereazaSir(10 ** 3)  # putem opri la 10^3 deoarece cel mai mare termen are 9 cifre
    numara = 0
    for termen in sir:
        if str(termen)[0] == str(a) and str(b) not in str(termen):
            numara += 1
    return numara


def main():
    with open("sir5.in", "r") as f:
        k, x, a, b = map(int, f.readline().split())
        if not (1 <= k <= 9 and 1 <= x < 900000000 and 1 <= a <= 9 and 1 <= b <= 9 and a != b):
            print("Datele nu corespund restricțiilor impuse.")
            return
    print("Datele sunt introduse corect.")
    with open("sir5.out", "w") as f:
        f.write(str(sumaTermeniMici(len(genereazaSir(100)), k)) + "\n")
        f.write(str(succesorulTermenului(x)) + "\n")
        f.write(str(numaraTermeniCuA(a, b)) + "\n")


if __name__ == "__main__":
    main()

Explicație rezolvare

  Funcția genereazaSir(n) generează un șir numeric de lungime n conform regulii specificate în enunțul problemei. Regula de generare presupune că primul termen al șirului este 1, iar fiecare termen nou se obține prin inversarea cifrelor ultimului termen până la prima apariție a cifrei 1 în acel termen. Termenii din șir sunt stocați într-o listă sir, care este returnată de funcție.
   Funcția sumaTermeniMici(n, k) primește ca argumente numărul n și numărul k și returnează suma termenilor din primii n termeni ai șirului care au cel mult k cifre. Șirul numeric este generat utilizând funcția genereazaSir(n). Funcția parcurge lista de termeni și adaugă la suma toți termenii care au cel mult k cifre.
   Funcția succesorulTermenului(x) primește ca argument un index x și returnează al x-lea termen din șirul numeric generat utilizând funcția genereazaSir(n). Pentru a găsi al x-lea termen, funcția apelează genereazaSir(x+1) și returnează elementul de pe poziția x din lista returnată.
   Funcția numaraTermeniCuA(a, b) primește ca argumente două cifre a și b și numără numărul de termeni din primii 1000 de termeni ai șirului care încep cu cifra a și nu conțin cifra b. Pentru a număra termenii care respectă această condiție, funcția parcurge lista de termeni și numără termenii care îndeplinesc condițiile impuse.
   Funcția main() citește datele din fișierul "sir5.in" și verifică dacă acestea respectă condițiile impuse. Dacă datele sunt corecte, funcția calculează răspunsurile la cele trei probleme și le scrie în fișierul "sir5.out".