2213 - Sir Div K

Enunț

Cu ajutorul a trei cifre date a, b, c, unde a > 0, se construieşte următorul şir de numere: a,ab,abc,abca,abcab,abcabc,… . De exemplu, pentru a=1, b=3, c=7, putem construi şirul: 1,13,137, 1371,13713, 137137, 1371371, 13713713, ...

Cerinţa

Scrieţi un program care determină câte numere divizibile cu k se găsesc în primii n termeni ai şirului dat.

Date de intrare

Fișierul de intrare sirdivk.in conține pe prima linie numerele a b c n k.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe urmatorul rand fișierul de ieșire sirdivk.out conţine o singură linie pe care este scris numărul nr de numere divizibile cu k aflate printre primii n termeni ai şirului dat. Î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

• 1 < n < 1000
• 2 ⩽ k < 32000
• 1 ⩽ a ⩽ 9, 0 ⩽ b,c ⩽ 9

Exemplu

sirdivk.in

7 2 1 8 3

sirdivk.out

Datele sunt introduse corect.

2

Explicație

Printre primii 8 termeni ai şirului: 7, 72, 721, 7217, 72172, 721721, 7217217, 72172172,... există doi termeni divizibili cu 3.

Rezolvare

<syntaxhighlight lang="python" line> def validare_date(a, b, c, n, k):

   if not(1 < n < 1000) or not(2 <= k < 32000) or not(0 <= b <= 9) or not(0 <= c <= 9) or not(1 <= a <= 9):
       return False
   else:
       return True

if __name__ == '__main__':

   with open("sirdivk.out", "w") as f_out:
       a, b, c, n, k = map(int, input().split())

       if not validate_date(a, b, c, n, k):
           f_out.write("Datele nu corespund restricțiilor impuse.")
           exit()
       else:
           f_out.write("Datele sunt introduse corect.")

       numar = [a] * n
       for i in range(1, n):
           if i % 3 == 1:
               numar[i] = b
           elif i % 3 == 2:
               numar[i] = c

       rest = 0
       gasite = 0
       for i in range(n):
           rest = rest * 10 + numar[i]
           if rest % k == 0:
               gasite += 1
           rest %= k

       f_out.write(str(gasite))

</syntaxhighlight>

Explicație rezolvare

Acest program primește ca input cinci numere întregi: a, b, c, n și k. Programul verifică dacă aceste valori corespund restricțiilor impuse prin intermediul funcției "validare_date". Dacă valorile nu respectă aceste restricții, programul va scrie în fișierul de ieșire mesajul "Datele nu corespund restricțiilor impuse." și se va opri. În caz contrar, programul va scrie în fișierul de ieșire mesajul "Datele sunt introduse corect.".
În continuare, programul va crea un număr de n cifre, unde n este valoarea citită inițial, având cifra a ca valoare inițială pentru toate cifrele. Acest număr este creat prin intermediul unei liste "numar". În timp ce se crează numărul, pentru fiecare cifră care urmează după prima cifră (poziția 1 în listă), programul va verifica dacă poziția este multiplu de 3. Dacă da, va înlocui valoarea cifrei de la acea poziție cu cifra b, altfel va înlocui cu cifra c.După crearea numărului, programul va parcurge toate cifrele acestuia, de la prima la ultima, și va verifica dacă numărul format din cifrele de la poziția 0 până la poziția curentă este divizibil cu k. Dacă este, programul va incrementa o variabilă numită "gasite". La final, programul va scrie în fișierul de ieșire valoarea variabilei "gasite", adică numărul de subșiruri care sunt divizibile cu k.