Pentru a converti un număr din zecimal în binar îl vom împărți la 2 în mod repetat, până ce obținem câtul zero. Apoi vom colecta resturile obținute de la ultimul către primul. Aceste resturi sunt cifrele din reprezentarea binară a numărului dat, de la stânga la dreapta. De exemplu, 13(10) = 1101(2).

Cerința

Scrieți un program care, pentru un șir dat de n numere naturale, rezolvă următoarele cerințe:

Pentru a converti un număr din zecimal în binar îl vom împărți la 2 în mod repetat, până ce obținem câtul zero. Apoi vom colecta resturile obținute de la ultimul către primul. Aceste resturi sunt cifrele din reprezentarea binară a numărului dat, de la stânga la dreapta. De exemplu, 13(10) = 1101(2).

Cerința

Scrieți un program care, pentru un șir dat de n numere naturale, rezolvă următoarele cerințe:
1) Determină cel mai mare dintre cele n numere date ce are număr maxim de valori de 1 în reprezentarea binară.
2) Determină cea mai lungă secvență de numere care au număr egal de valori de 1 în reprezentarea binară. Dacă sunt mai multe astfel de secvențe de lungime maximă, se va alege cea mai din stânga. O secvență este un subșir de numere care apar pe poziții consecutive în șirul inițial.

Date de intrare

Fișierul de intrare binar.in conţine pe prima linie numărul C reprezentând cerința (1 sau 2), pe a doua linie numărul natural n, iar pe a treia linie n numere naturale separate prin câte un spațiu.

Date de ieșire

Dacă C = 1, atunci pe prima linie a fișierului de ieșire binar.out se va scrie numărul ce reprezintă răspunsul la cerința 1. Dacă C = 2, atunci pe prima linie a fișierului de ieșire binar.out se vor scrie, separate printr-un spațiu, lungimea maximă a secvenței determinate și poziția primului termen din secvență (se consideră că primul număr din cele n numere date se găsește pe poziția 1).

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• Valorile din șirul de intrare sunt numere naturale de cel mult nouă cifre.
• Pentru 30% din teste cerința va fi C = 1.
• În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru testele din enunț.

Exemplul 1:

binar.in

1
7
16 12 3 5 14 13 11

binar.out

14

Explicație

16(10) = 10000(2); 12(10) = 1100(2);
3(10) = 11(2); 5(10) = 101(2); 14(10) = 1110(2); 13(10) = 1101(2); 11(10) = 1011(2);
Cel mai mare număr de valori de 1 dintr-o reprezentare binară este 3; cel mai mare număr ce are 3 de 1 în reprezentarea binară este 14.

Exemplul 2:

binar.in

2
7
16 12 3 5 14 13 11

binar.out

3 2

Explicație

Sunt două secvențe de lungime maximă de numere care au număr egal de valori de 1 în reprezentarea binară: 12 3 5 și 14 13 11. O vom alege pe cea mai din stânga, care are lungimea 3 și începe la poziția 2.

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

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

int n , a[1000001] , b[1000001];

int binar(int x)
{
    int cnt = 0;
    while(x)
    {
        if(x%2)
            cnt++;
        x/=2;
    }
    return cnt;
}

int main()
{
    int t;
    cin >> t >> n;
    for(int i = 1 ; i <= n ; ++i)
    {
        cin >> a[i];
        b[i]=binar(a[i]);
    }
    int max=0 , max1 = 0;
    for(int i = 1 ; i <= n ; ++i)
        if(b[i] > max)
            max = b[i];
    for(int i = 1 ; i <= n ; ++i)
        if(b[i]==max && a[i] > max1)
            max1=a[i];
    if(t==1)
        cout << max1;
    else
    {
        int l = 1 , lmax = 1 , start = 1;
        for(int i = 2 ; i <= n ; ++i)
        {
            if(b[i]==b[i-1])
            {
                l++;
                if(l > lmax)
                    lmax = l , start=i-lmax+1;
            }
            else
                l=1;
        }
        cout << lmax << ' ' << start;
    }
    return 0;
}