# PBinfo #1820 – Binar – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Cerința
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.in 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 ieșire
Fişierul binar.out 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.

Restricții și precizări

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.

Exemplu:
binar.in

19 3
1 0 -1 1 -1 1 0 -1 1 1 -1 1 0 1 -1 1 0 1 -1
binar.out

5 2
2 2
3 1
Explicație
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.

## Cod sursă C++

```cpp
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("binar.in");
ofstream fout("binar.out");
long long n,nr, x[10001],i,j,cifra,numar,k;
int y[10001],aparitii[10001],h,aux;
int main()
{
    fin>>n>>nr;
	numar=0;k=0;
    for(i=1;i<=n;i++)
    { 
		fin>>cifra;
        if (cifra==-1)
        { 
			k++;
			x[k]=numar;
            numar=0;
        }
        else numar=numar*2+cifra;
    }
    //for (i=1;i<=k;i++) cout<<x[i]<<" ";
	for(i=1;i<=k-1;i++)
		for(j=i+1;j<=k;j++)
			if(x[i]<x[j])
			{
				aux=x[i];
				x[i]=x[j];
				x[j]=aux;
			}
    h=1;
    for(i=1;i<=k-1;i++)
		if(x[i]==x[i+1])
			aparitii[h]++;
		else
		{
			y[h]=x[i];
			aparitii[h]++;
			h++;
		}
	y[h]=x[k];
	aparitii[h]++;
	for(i=1;i<=h-1;i++)
		for(j=i+1;j<=h;j++)
			if(aparitii[i]<aparitii[j]||((aparitii[i]==aparitii[j])&&(y[i]<y[j])))
			{
				aux=y[i];
				y[i]=y[j];
				y[j]=aux;
				aux=aparitii[i];
				aparitii[i]=aparitii[j];
				aparitii[j]=aux;
			}
	for(i=1;i<=nr;i++)
		fout<<y[i]<<" "<<aparitii[i]<<'\n';
	fin.close();
	fout.close();
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1820)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1820/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1820/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)