02 - Exercícios

ll bits_ativos(ll n){
    ll x = 0, pot = 1, k = 0;
    while (n > x){
        if (num & (pot)){
            x += (pot);
            k++;
        }
        pot *= 2;
    }
    return k;
}

ll bits_ativos(ll n){
return __builtin_popcountll(n);
}

#define MAX_FAC 14
fac = vector<ll>(MAX_FAC + 1);
void pre_processar_fatoriais(){
    ll x = 1;
    for (int i = 1; i <= MAX_FAC; i++){
        x *= i;
        fac[i] = x;
    }
}

void subset_sum_fac(ll x){
if (x == MAX_FAC+1){
    ll sum = 0;
    for (int i = 0; i < subset.size(); i++){
        sum += fac[subset[i]];
    }
    if(fac_sub[sum]!=0)
        fac_sub[sum] = min(fac_sub[sum],subset.size());
    else
        fac_sub[sum] = subset.size();
}
else{
    subset.push_back(x);
    subset_sum_fac(x + 1);
    subset.pop_back();
    subset_sum_fac(x + 1);
    }
}

for (map<ll, ll>:: iterator itr =
fac_sub.begin();itr!=fac_sub.end();++itr)
{
    ll a = itr->first;
    if (a > n) break;
    ll x = n - a; //Quanto falta para a soma 'a' chegar em 'n'
    minimo = min(minimo, bits_ativos(x) + fac_sub[a]);
}

Sit_1 = bits_ativos();

Sit_2 = todas_somas_possiveis_dos_fatoriais
    for(i=0;i<=Sit_2.size();i++)
    Sit_3 = min(Sit_3, Sit_2 [i] + Sit_1 (n - Sit_2 [i]))
k_minimo = min (Sit_1(n) , Sit_3 )

int main() {
    // leitura do tamanho do tabuleiro e alocação da matriz do Sudoku
    while (cin >> n) {
        n *= n;
        sudoku = vector<vector<int>>(n, vector<int>(n));
        // leitura do Sudoku
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                cin >> sudoku[i][j];
        // se o tabuleiro apresentar solução
        if (solve(0, 0)) {
            // imprime a solução
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++)
                    cout << sudoku[i][j] << " ";
            cout << "\n";
            }
        } else
            // caso contrário, imprime que não há solução viável
        cout << "NO SOLUTION\n";
        }
    return 0;
}

bool solve(int row, int col) {
    // verifica se chegou ao final da coluna atual
    if (col == n) {
        // se sim, pula para a linha de baixo e volta para primeira coluna
        col = 0;
        row++;
        // caso passe da última linha, o quebra-cabeças tem solução e 
        // retorna verdadeiro
        if (row == n)
            return true;
    }
    // verifica se a célula atual é uma célula vazia
    if (sudoku[row][col] == 0) {
        // sendo uma célula vazia, vamos tentar inserir valores de 1 
        // até n^2 nela
        for (int i = 1; i <= n; i++) {
            // verificamos se é possível inserir o valor i, respeitando as 
            // regras do jogo
            if (verify(row, col, i)) {
                // em caso afirmativo, alteramos o valor da célula
                sudoku[row][col] = i;
                // e tentamos resolver a próxima casa
                if (solve(row, col + 1))
                    return true;
            }
        }
        // se nenhum valor retornar uma solução válida, esvaziamos a casa
        sudoku[row][col] = 0;
    } else
        // se já é uma célula com valor, avançamos para a próxima 
        // coluna apenas
        return solve(row, col + 1);
    // se o código chegar até aqui, quer dizer que, para o tabuleiro no 
    // estado atual, não tem solução
    // assim, retornamos na recursão, e tentamos achar uma solução para 
    // próxima configuração
    return false;
}

bool verify(int row, int col, int elem) {
    for (int i = 0; i < n; i++) {
        // verifica se existem elementos repetidos na linha
        // caso exista elemento repetido, retorna falso
        if (sudoku[i][col] == elem)
            return false;
        // verifica se existem elementos repetidos na coluna
        else if (sudoku[row][i] == elem)
            return false;
    }
    // determina o inicio da linha e da coluna do subquadrado atual
    int sq, sub_row, sub_col;
    sq = sqrt(n);
    sub_row = row / sq * sq;
    sub_col = col / sq * sq;
    // verificar se existem elementos repetidos no subquadrado
    for (int i = sub_row; i < sub_row + sq; i++) {
        for (int j = sub_col; j < sub_col + sq; j++) {
        // caso exista elemento repetido, retorna falso
            if (sudoku[i][j] == elem)
                return false;
        }
    }
    // se chegou até aqui, todas as especificações foram atendidas e retorna 
    // verdadeiro
    return true;
}