Question

#1820 Binar
Empowersoft, 2016 Clasele V-VI Binar


Această problemă a fost preluată dintr-un concurs. Rezultatele evaluării pot fi diferite față ale evaluării în concurs.
Enunț
Soluții


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 1000 î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.

Answer 1

Salut, am facut problema in C++. Sa iti fie de folos!

#include <iostream>

using namespace std;

int main()

{

   int n = 19, nr = 3;  //citeste din fisier N si NR

   //Citeste cele N numere de pe linia 2

   int v[n] = {1, 0, -1, 0, -1, 1, 0, -1, 1, 1, -1, 1, 0, 1, -1, 1, 0, 1, -1};

   int ap[100];

   

   //initializam elementele din vectorul de numarare cu 0

   for(int j=0;j<100;j++)

   {

       ap[j] =0;

   }

   //transformam din binare in zecimale

   string nrTemp="";

   for(int i = 0;i<n;i++)

   {

       if(v[i] != -1)

           nrTemp+=v[i];

       else

       {

           

           int cnt = nrTemp.length()-1;

           int nr = 0;

           int pow = 1;

           

           for(int z = nrTemp.length()-1;z>=0;z--)

           {

               pow = 1;

               for(int j =0;j<cnt-z;j++)

                       pow*=2;

                       

               nr+=(int)(nrTemp[z]) * pow;

           }

           ap[nr] ++;

           nrTemp="";

       }

   }

   

   //vedem care este numarul maxim de aparitii

   int maxAparitie=0;

   

   for(int j=100;j>=0;j--)

       {

          if(maxAparitie < ap[j])

               maxAparitie = ap[j];

       }

   

   //Afisam primele nr numere descrescator dupa nr de aparitie si descrescator daca au acelasi nr de aparitie

   int cnt=0;

   for(int i = maxAparitie;i>=1 && cnt<nr;i--)

  {

       for(int j=99;j>=0 && cnt<nr;j--)

       {

          if(ap[j] == i)

          {

               cout<<j<<" "<<ap[j]<<endl;

               cnt++;

          }

       }

   }

   

   return 0;

}