Rezolvare PBinfo #1820

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.