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

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")

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.