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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele de intrare corespund restricțiilor impuse." Programul va afișa pe ecran, pe câte o linie, numerele S1, S2, … , SN. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

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

Datele de intrare corespund restricțiilor impuse.

5

2

Explicație

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

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


if __name__ == '__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):
        print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        print("Datele de intrare corespund restricțiilor impuse.")
        # Calculam resturile S1, S2, ..., SN
        S = calculate_S(Z)
        # Afisam rezultatele
        for s in S:
            print(s)

Explicație

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.