Editing 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 &les; N &les; 100.000.
*1 &les; NR &les; 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])


# 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()))

# 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]))

with open("binarout.txt", "w") as g:
    for valoare, aparitii in rezultate_sortate[:NR]:
        g.write(f"{valoare} {aparitii}\n")

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