3009 - ZTS

From Bitnami MediaWiki
Revision as of 16:44, 7 May 2023 by Cuceu Andrei (talk | contribs) (Pagină nouă: ==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 '''reprezi...)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.