3009 - ZTS

Cerință

Fie Z un număr natural în baza 10. Considerăm rkrk-1 … r1r0 scrierea numărului Z în baza 3. Fie T = rkrk−1…r1r0 numărul în baza 10 format cu cifrele rk, rk-1, … r1, r0. Notăm cu S restul împărțirii numărului T la 7. Se dau N numere naturale Z1, Z2, … , ZN. Pentru fiecare dintre numerele Z1, Z2, … , ZN se cere să se calculeze S1, S2, … , SN. (Si reprezintă restul împărțirii la 7 a numărului Ti iar Tireprezintă numărul format cu cifrele scrierii în baza 3 a numărului Zi).

Date de intrare

Programul citește de la tastatură numărul N, iar apoi N numere naturale Z1, Z2, … , ZN, separate prin spații.

Date de ieșire

Programul va afișa pe ecran, pe câte o linie, numerele S1, S2, … , SN.

Restricții și precizări

• 1 ≤ N ≤ 40000
• Z1, Z2, … , ZN vor fi mai mici decât 2^64

Exemplul 1

Intrare

 2
 19 30

Ieșire

 5
 2

Explicatie

S-au citit 2 numere: 19 și 30. Numărul 19 în baza 3 se scrie: 201. Restul împărțirii numărului 201 la 7 este 5. Numărul 30 în baza 3 se scrie: 1010. Restul împărțirii numărului 1010 la 7 este 2.

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line="1" start="1">

def validate_input(N, Z):

   if N < 1 or N > 40000:
       print("Numarul de intrare trebuie sa fie intre 1 si 40000")
       return False
   for z in Z:
       if z >= 2**64:
           print("Numarul ", z, " este prea mare")
           return False
   return True

def calculate_S(Z):

   S = []
   for z in Z:
       base_3 = []
       while z > 0:
           base_3.append(z % 3)
           z //= 3
       T = 0
       for i in range(len(base_3)):
           T += base_3[i] * (3 ** i)
       S.append(T % 7)
   return S

def main():

   # Citim numarul de intrari si numerele Z1, Z2, ..., ZN
   N = int(input())
   Z = list(map(int, input().split()))

   # Validam datele de intrare
   if not validate_input(N, Z):
       return

   # Calculam resturile S1, S2, ..., SN
   S = calculate_S(Z)

   # Afisam rezultatele
   for s in S:
       print(s)

if __name__ == '__main__':

   main()

</syntaxhighlight>

Explicatie

Primul pas în rezolvarea problemei este să citim numărul de intrări și numerele Z1, Z2, ..., ZN de la intrare, iar apoi să le validăm. Pentru a face acest lucru, utilizăm funcția validate_input, care verifică dacă numărul de intrări este între 1 și 40000 și dacă fiecare număr Z este mai mic decât 2^64. Dacă datele de intrare sunt invalide, afișăm un mesaj de eroare și ieșim din program. În caz contrar, continuăm cu calcularea resturilor.

Funcția calculate_S primește un vector de numere întregi Z și calculează vectorul de resturi S. Pentru fiecare număr Z, transformăm numărul în baza 3 utilizând o buclă while. Apoi, calculăm numărul T în baza 10 format cu cifrele scrierii în baza 3 a numărului Z, prin înmulțirea fiecărei cifre cu puterea corespunzătoare a bazei și adunarea rezultatelor. Pentru a calcula restul împărțirii lui T la 7, folosim operatorul % și adăugăm rezultatul la vectorul S.

În funcția main, citim datele de intrare, le validăm și apoi calculăm resturile utilizând funcția calculate_S. În cele din urmă, afișăm vectorul de resturi.