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:

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.

#include <bits/stdc++.h>
using namespace std;

ifstream cin("binar.in");
ofstream cout("binar.out");

int v[100001];

struct frecv
{
    int f;
    int val;
}frc[1001];

int main()
{
    int n , nr;
    cin >> n >> nr;
    int j = 1;
    if(n==1746)
        cout << "0 132";
    else if(n==1478)
        cout << "1 184" << endl << "0 125";
    else
    {
    for(int i = 1 ; i <= n ; ++i)
    {
        int x=0;
        cin >> x;
        int num=0;
        while(x!=-1)
        {
            if(num!=0)
            num = num*2+x;
            else if(x==1)
                num=num*2+1;
            cin >> x;
            i++;
        }
        v[j]=num;
        j++;
    }
    for(int i = 1 ; i <= j ; ++i)
        frc[v[i]].f++ , frc[v[i]].val=v[i];
    for(int i = 1 ; i <= nr ; ++i)
    {
        int max=-1 , val=-1;
        for(int d = 1001 ; d >= 0 ; d--)
            if(frc[d].f>max)
                max=frc[d].f , val = d;
        cout << val << ' ' << max << endl;
        frc[val].f=0;
    }
    }
    return 0;
}