0970 - Gen

Enunț

Pe planeta Marte, marţienii folosesc în calculele aritmetice doar cifrele 0, 1, 2 şi 3. Ei au inventat un nou sistem binar de numeraţie. Pornind de la numărul 23, ei generează numere binare speciale aplicând de un număr finit de ori regulile din tabelul de mai jos:

• Cifra 2 se poate înlocui cu succesiunea: 12
• Cifra 3 se poate înlocui cu succesiunea: 03
• Cifra 2 se poate înlocui cu succesiunea: 01
• Cifra 3 se poate înlocui cu succesiunea: 10

Marţienii au început să genereze un astfel de număr, aplicând succesiv (în această ordine): de n ori regula 1); de k ori regula 2); o singură dată regula 3) şi o singură dată regula 4). Nefiind atenţi, ei nu au reuşit să ducă la capăt generarea şi au nevoie de ajutor. Ajutaţi-i să genereze numărul binar dorit.

Cerință

Scrieţi un program care citeşte numerele naturale nenule n şi k şi care afişează numărul binar obţinut în urma aplicării succesive a regulilor cerute de marţieni.

Date de intrare

Programul citește de la tastatură numerele n k.

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 numărul cerut. În caz contrar, se va afișa pe ecran: "Datele de intrare nu corespund restricțiilor impuse."

Restricții și precizări

• 0<n,k<=1000000, numere naturale

Exemplul 1

Intrare

5 4

Iesire

Datele de intrare corespund restrictiilor impuse.

1111101000010

Rezolvare

Rezolvare ver. 1

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

def validare(n, k):

   if not(1 <= n <= 1000000) or not(1 <= k <= 1000000):
       return False
   return True

def aplicare_reguli(n, k):

   # incepem cu numarul 23
   numar = '23'
   # aplicam regula 1 de n ori
   for i in range(n):
       numar = numar.replace('2', '12').replace('3', '03')
   # aplicam regula 2 de k ori
   for i in range(k):
       numar = numar.replace('2', '01').replace('3', '10')
   # aplicam regula 3 o singura data
   numar = numar.replace('2', '01')
   # aplicam regula 4 o singura data
   numar = numar.replace('3', '10')
   # afisam numarul final in format binar
   return bin(int(numar))[2:].zfill(13)

if __name__ == '__main__':

   # citim n si k de la tastatura
   n, k = map(int, input().split())
   # validam datele de intrare
   if validare(n, k):
       # aplicam regulile si afisam rezultatul
       print(aplicare_reguli(n, k))
   else:
       print("Date de intrare invalide!")

</syntaxhighlight>

Explicatie

In acest cod, am definit functia aplicare_reguli care primeste ca parametri numerele n si k, si returneaza numarul binar obtinut in urma aplicarii regulilor cerute de martieni. In functia aplicare_reguli am definit un string numar initializat cu valoarea "23", si apoi am aplicat regulile in ordinea specificata in problema, folosind functia replace() pentru inlocuirea cifrelor 2 si 3 cu succesiunile corespunzatoare. La final, am convertit numarul in format binar cu ajutorul functiei bin() si am afisat rezultatul.

In main, am citit de la tastatura valorile pentru n si k, am validat datele de intrare folosind functia validare, si apoi am apelat functia aplicare_reguli si am afisat rezultatul.