asswecan.cpp

#include <iostream>
#include <cmath>
#include <cstdio>

using namespace std;

bool check(int *a, int n);
bool asswecan1(int l, int *a, int n, int k);
bool asswecan2(int l, int *a, int n, int k);
int bs(int l, int r, int *a, int n);

int main(){
    int n, a[100000];
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    cout << bs(-1, n*8, a, n) << endl;

    return 0;
}

int bs(int l, int r, int *a, int n){
    int m;
    while (l + 1 < r){
        m = (l + r) / 2;
        if (asswecan1(m, a, n, 0) || asswecan2(m, a, n, 0))
            r = m;
        else
            l = m;
    }
    return r;
}

bool asswecan1(int l, int *a, int n, int k){
    if (check(a, n))
        return true;
    if (l == 0 || k == n)
        return false;
    int *b = new int[n];
    for (int j = 0; j < n; j++)
            b[j] = a[j];
    for (int i = 0; i < l; i++){
        b[k] /= 2;
        if (asswecan1(l - i - 1, b, n, k + 1))
            return true;
        if (asswecan2(l - i - 1, b, n, k + 1))
            return true;
    }
    return false;
}

bool asswecan2(int l, int *a, int n, int k){
    if (check(a, n))
        return true;
    if (l == 0 || k == n)
        return false;
    int *b = new int[n];
    for (int j = 0; j < n; j++)
            b[j] = a[j];
    for (int i = 0; i <= l; i++){
        if (asswecan1(l, b, n, k + 1))
            return true;
        if (asswecan2(l, b, n, k + 1))
            return true;
        b[k] *= 2;
    }
    return false;
}

bool check(int *a, int n){
    bool dowe = true;
    for (int i = 1; i < n && dowe; i++)
        dowe &= a[i] == a[i - 1];
    return dowe;
}