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 ≤ 100000.
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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Binar:

#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;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1820 Binar

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1820 Binar de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1820 Binar