1820 - Binar

From Bitnami MediaWiki
Revision as of 09:52, 16 December 2023 by Mesarosdenisa (talk | contribs) (Pagină nouă: == 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....)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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 binar.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 binar.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

Intrare
19 3
1 0 -1 1 -1 1 0 -1 1 1 -1 1 0 1 -1 1 0 1 -1
Iesire
Datele introduse corespund restrictiilor impuse
5 2
2 2
3 1

Exemplul 2

Intrare
10 5
-1 1 1 0 0 8 3 -10 0 8
Iesire
Datele introduse nu corespund restrictiilor impuse


Rezolvare

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

   numar = 0
   putere = 0
   for cifra in reversed(binar):
       numar += int(cifra) * (2 ** putere)
       putere += 1
   return numar

def main():

   # Citirea datelor de intrare
   with open("binar.txt", "r") as file:
       N, NR = map(int, file.readline().split())
       valori = list(map(int, file.readline().split()))
   # Decodificarea și numărarea aparițiilor
   frecventa = {}
   index = 0
   while index < N:
       if valori[index] == -1:
           index += 1
           continue
       cod_binar = []
       while index < N and valori[index] in {0, 1}:
           cod_binar.append(str(valori[index]))
           index += 1
       numar_decodificat = decodeaza_binar(cod_binar)
       frecventa[numar_decodificat] = frecventa.get(numar_decodificat, 0) + 1
   # Sortarea și scrierea în fișierul de ieșire
   with open("binar.txt", "w") as file_out:
       for x, ap in sorted(frecventa.items(), key=lambda item: (-item[1], -item[0])):
           file_out.write(f"{x} {ap}\n")

if __name__ == "__main__":

   main()

</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.