tap17/k.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#define dprint(v) cerr << #v"=" << v << endl

using namespace std;
#define MAXN 100000
#define forr(i,a,b) for(int i=(a); i<(b); i++)
#define forn(i,n) forr(i,0,n)
#define pb push_back
typedef long long ll;

int persona[MAXN];

int n, k, m, v;
ll suma;
#define INF 1000000

int lastbit0(ll v){
    int rta = 1;
    v /= 2;
    while (v % 2){
        rta++;
        v /= 2;
    }
    return rta;
}

vector <int> p; // Pares
vector <int> im; // Impares

int main(){
    cin >> n;
    forn (i,n) {cin >> v;
    if (v % 2){
        im.pb(lastbit0(v));
    }
    else{
        p.pb(lastbit0(v));
    }
   }
    sort (im.begin(), im.end());
    sort (p.begin(), p.end());

    m = im.size();
    int mpares = p.size();

    int mini = INF;
    if (mpares) mini = min (mini, p[0]);
    if (m) mini = min (mini, im[0]);

    int rta = m+1;
    if (mini <= m || !m) rta = m; // Lema: La respuesta es menor que m+1 sii existe un a[i] con un bit en 0 entre (1 y m)

    int aux = m;
    int i = 0;
    if (rta == m) // Si existe aplico el greedy
        while (m){
            if (im[i] < aux){
                aux -= im[i] + 1;
                i++;
            }
            else break;

        }
    cout << rta - i << endl;

    return 0;
}