1820 - Binar

Cerinta

Ionel a învăţat recent la Informatică reprezentarea numerelor în baza 2. Pentru a-și aprofunda cunoştinţele, profesorul său a inventat următoarea problemă: Dintr-un fişier text se citeşte un şir de N valori de 1, 0 şi -1. Valoarea -1 are semnificaţia de terminare a unui număr, iar valorile de 0 şi 1 reprezintă cifrele în baza 2 a câte unui număr natural. Să se determine primele NR valori codificate, cu numerele de apariţii cât mai mari.

Date de intrare

Fişierul binarin.txt cu următoarea structura:

• pe prima linie numerele N şi NR cu semnificaţia din enunţ.
• pe a doua linie N valori de 1, 0 sau -1.

Date de iesire

Fişierul binarout.txt va conţine perechi distincte de numere X, AP cu semnificaţia X – valoarea codificata în baza 10, AP – numărul de apariţii ale valorii X, pe fiecare linie câte o pereche despărţită printr-un spaţiu. Perechile vor fi afişate în ordinea descrescătoare a valorii AP, iar la valori egale, în ordinea descrescătoare a valorii lui X.

Restrictii si precizari

• 10 ⩽ N ⩽ 100.000.
• 1 ⩽ NR ⩽ 3.
• Înaintea fiecărei valori de -1 se găseşte cel putin o valoare de 0 sau 1.
• Numerele codificate astfel sunt mai mici decat 10000 în baza 10.
• Se poate ca la stânga unui număr codificat să fie doar valori de 0.
• În şir sunt codificate cel puţin 3 valori distincte.
• Şirul de valori se incheie cu o valoare de -1.

Exemplul 1

binarin.txt

19 3

1 0 -1 1 -1 1 0 -1 1 1 -1 1 0 1 -1 1 0 1 -1

binarout.txt

Datele introduse corespund restrictiilor impuse

5 2

2 2

3 1

Exemplul 2

binarin.txt

10 5

-1 1 1 0 0 8 3 -10 0 8

binarout.txt

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def binar_to_decimal(binar):

   # Convertirea unui număr binar în decimal
   decimal = 0
   for bit in binar:
       decimal = decimal * 2 + int(bit)
   return decimal

def verifica_rezultat(input_file, output_file):

   # Citire date de intrare
   with open(input_file, "r") as f:
       N, NR = map(int, f.readline().split())
       sir_binar = list(map(int, f.readline().split()))

   # Initializare dicționar pentru frecvențe
   frecvente = {}

   # Parcurgere șir binar
   i = 0
   while i < N:
       numar_binar = []
       while i < N and sir_binar[i] != -1:
           numar_binar.append(str(sir_binar[i]))
           i += 1

       numar_decimal = binar_to_decimal(numar_binar)
       if numar_decimal in frecvente:
           frecvente[numar_decimal] += 1
       else:
           frecvente[numar_decimal] = 1

       i += 1

   # Sortare și scriere rezultat în fișierul de ieșire
   rezultate_sortate = sorted(frecvente.items(), key=lambda x: (-x[1], -x[0]))

   # Citire rezultat așteptat
   with open(output_file, "r") as g:
       rezultat_asteptat = [tuple(map(int, linie.split())) for linie in g.readlines()]

   # Verificare rezultat
   if rezultate_sortate[:NR] == rezultat_asteptat:
       print("Rezultat corect!")
   else:
       print("Rezultat incorect!")
       print("Rezultat așteptat:")
       print(rezultat_asteptat)
       print("Rezultat obținut:")
       print(rezultate_sortate[:NR])

1. Citire date de intrare

with open("binarin.txt", "r") as f:

   N, NR = map(int, f.readline().split())
   sir_binar = list(map(int, f.readline().split()))

1. Initializare dicționar pentru frecvențe

frecvente = {}

1. Parcurgere șir binar

i = 0 while i < N:

   numar_binar = []
   while i < N and sir_binar[i] != -1:
       numar_binar.append(str(sir_binar[i]))
       i += 1

   numar_decimal = binar_to_decimal(numar_binar)
   if numar_decimal in frecvente:
       frecvente[numar_decimal] += 1
   else:
       frecvente[numar_decimal] = 1

   i += 1

1. Sortare și scriere rezultat în fișierul de ieșire

rezultate_sortate = sorted(frecvente.items(), key=lambda x: (-x[1], -x[0]))

with open("binarout.txt", "w") as g:

   for valoare, aparitii in rezultate_sortate[:NR]:
       g.write(f"{valoare} {aparitii}\n")

1. Apelare funcție de verificare

verifica_rezultat("binarin.txt", "binarout.txt")

</syntaxhighlight>

Explicatie

Numerele codificate sunt: 1 apare odată, 2 apare de 2 ori, 3 apare odată şi 5 apare de 2 ori. Sunt afişate primele 3 în ordinea descrescătoare a numărului de apariţii. Numerele 2 şi 5 care au acelaşi număr de apariţii se afișează în ordinea descrescătoare a valorii lor.