2936 - Amprenta

Sursa: [1]

Cerinţa

Pentru orice număr natural N se asociază o cifră din mulțimea {0,1,2,3,4,5}, numită amprentă, astfel: se calculează diferența pozitivă a sumelor cifrelor de pe pozițiile pare, respectiv impare; dacă această diferență este mai mică decât 10 atunci algoritmul se oprește, în caz contrar algoritmul se aplică în continuare, repetat, asupra diferenței pozitive, până când se va obține o cifră mai mică decât 10, iar dacă cifra este mai mare decât 5, atunci cifrele 6,7,8,9 se vor înlocui respectiv cu 5,4,3,2. De exemplu pentru numărul N = 90 amprenta este 2, iar pentru N = 91909091 amprenta este 1.

1) Se dă un număr natural N şi se cere determinarea amprentei acestuia. 2) Se dau două numere naturale P, Q şi o cifră C din {0,1,2,3,4,5} şi se cere determinarea numărului de valori dintre P şi Q, inclusiv, care au amprenta egală cu C.

Date de intrare

Programul conține pe primul rând numărul T reprezentând tipul cerinței. Dacă T==1, atunci pe al doilea rând se află scris un număr natural N. Dacă T==2, atunci pe al doilea rând se află scrise numerele naturale P, Q şi C, separate prin câte un spațiu.

Date de ieșire

Programul se va scrie pe primul rând un singur număr natural, corespunzător cerinței și cazului T.

Dacă datele sunt introduse corect, programul va rula.

Î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

0 ≤ N ≤ 10^18

0 ≤ P ≤ 10^18

0 ≤ Q ≤ 10^18

Pentru 30% din teste diferența pozitivă dintre P și Q va fi mai mică decât 10.000

Pentru alte 20% din teste diferența pozitivă dintre P și Q va fi mai mică decât 100.000

Exemplul 1

Intrare

1

29

Ieșire

4

Exemplul 2

Intrare

2

1 9 2

Ieșire

2

Rezolvare

<syntaxhighlight lang="python" line>

1. 2936

def calcul_amprenta(n):

   dif = abs(sum(int(c) for i, c in enumerate(str(n)) if i % 2 == 0) - sum(int(c) for i, c in enumerate(str(n)) if i % 2 == 1))
   while dif >= 10:
       dif = abs(sum(int(c) for c in str(dif) if int(c) % 2 == 0) - sum(int(c) for c in str(dif) if int(c) % 2 == 1))
   if dif > 5:
       dif = 5 - (dif - 6)
   return dif

def numara_valori_amprenta(p, q, c):

   count = 0
   for i in range(p, q+1):
       if calcul_amprenta(i) == c:
           count += 1
   return count

1. citire date de intrare

t = int(input()) if t == 1:

   n = int(input())
   print(calcul_amprenta(n))

elif t == 2:

   p, q, c = map(int, input().split())
   print(numara_valori_amprenta(p, q, c))

def validate_input(n, p, q):

   if n < 0 or n > 10**18:
       return False
   if p < 0 or p > 10**18:
       return False
   if q < 0 or q > 10**18:
       return False
   return True

if __name__ == '__main__':

   t = int(input())
   if t == 1:
       n = int(input())
       if not validate_input(n, 0, 0):
           print("Input invalid!")
       else:
           print(calcul_amprenta(n))
   elif t == 2:
       p, q, c = map(int, input().split())
       if not validate_input(0, p, q):
           print("Input invalid!")
       else:
           print(numara_valori_amprenta(p, q, c))

</syntaxhighlight>

Explicatie cod:

Funcția calcul_amprenta(n) primește un număr n și calculează amprenta numerică a acestuia. Amprenta numerică este diferența dintre suma cifrelor de pe pozițiile pare și suma cifrelor de pe pozițiile impare ale numărului n. Dacă diferența este mai mare sau egală cu 10, se repetă procesul de calcul pentru diferență până când diferența devine mai mică decât 10. Dacă diferența finală este mai mare decât 5, atunci amprenta este 5 scăzută cu diferența finală minus 6.

Funcția numara_valori_amprenta(p, q, c) primește trei parametri p, q, c și numără câte numere între p și q au amprenta numerică egală cu c. Se parcurg numerele între p și q și se calculează amprenta numerică a fiecărui număr. Dacă amprenta numerică este egală cu c, atunci se incrementează count. La final, funcția returnează count.

Funcția validate_input(n, p, q) primește trei parametri n, p, q și verifică dacă aceștia se încadrează în intervalele de valori permise (0 ≤ N ≤ 10^18, 0 ≤ P ≤ 10^18, 0 ≤ Q ≤ 10^18). Dacă valorile nu se încadrează în aceste intervale, funcția returnează False. În caz contrar, funcția returnează True.

Blocul de cod if __name__ == '__main__': este un cod care se execută doar dacă acest modul este rulat direct, nu este importat în alt modul. În acest bloc, se citește t, numărul de teste care urmează să fie executate. Dacă t este egal cu 1, se citește numărul n, se validează inputul folosind funcția validate_input(), și dacă inputul este valid, se calculează și se afișează amprenta numerică a lui n. Dacă t este egal cu 2, se citește p, q și c, se validează inputul folosind funcția validate_input(), și dacă inputul este valid, se numără câte numere între p și q au amprenta numerică egală cu c, și se afișează numărul calculat. Dacă inputul nu este valid, se afișează "Input invalid!".