Uma empresa possui n funcionários, onde cada funcionário i tem uma habilidade representada por um número inteiro positivo a_i. O projeto requer exatamente ⌈n/2⌉ funcionários, com a soma das habilidades ≥ x. Determine o número de combinações viáveis.

Entrada: Múltiplos conjuntos de dados. Cada conjunto inclui n (1≤n≤16), x (1≤x≤2×10⁴) e uma lista de n hbailidades (1≤a_i≤10³). Saída: número de combinações para cada conjunto.

import java.util.Scanner;

public class SolucaoAlocacao {
    private static int contador;

    public static void main(String[] args) {
        Scanner leitor = new Scanner(System.in);
        int casos = leitor.nextInt();
        for (int caso = 0; caso < casos; caso++) {
            int n = leitor.nextInt();
            int limiar = leitor.nextInt();
            int[] habilidades = new int[n];
            for (int i = 0; i < n; i++) {
                habilidades[i] = leitor.nextInt();
            }
            contador = 0;
            explorarCombinacoes(habilidades, n, 0, limiar, 0, 0);
            System.out.println(contador);
        }
    }

    private static void explorarCombinacoes(int[] dados, int total, int selecionados, int meta, int inicio, int somaAtual) {
        int necessario = (total + 1) / 2;
        if (selecionados == necessario) {
            if (somaAtual >= meta) contador++;
            return;
        }
        for (int idx = inicio; idx < dados.length; idx++) {
            explorarCombinacoes(dados, total, selecionados + 1, meta, idx + 1, somaAtual + dados[idx]);
        }
    }
}

Problema 2: Correção de Equação

Dada uma equação com números inteiros positivos, '+', '*', e '=', verifique se é possível enserir no máximo um dígito (0-9) em qualuqer posição para torná-la válida. Se já for válida, considere como válida.

Entrada: T (1≤T≤10) equações. Saída: "Sim" ou "Não" para cada caso.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class SolucaoEquacao {
    public static void main(String[] args) {
        Scanner leitor = new Scanner(System.in);
        int qtd = leitor.nextInt();
        for (int i = 0; i < qtd; i++) {
            String expressao = leitor.next();
            if (podeCorrigir(expressao)) {
                System.out.println("Sim");
            } else {
                System.out.println("Não");
            }
        }
    }

    private static boolean podeCorrigir(String expr) {
        StringBuilder sb = new StringBuilder(expr);
        for (int pos = 0; pos <= sb.length(); pos++) {
            for (char digito = '0'; digito <= '9'; digito++) {
                sb.insert(pos, digito);
                String[] partes = sb.toString().split("=");
                if (avaliarExpressao(partes[0]) == avaliarExpressao(partes[1])) {
                    return true;
                }
                sb.deleteCharAt(pos);
            }
        }
        return false;
    }

    private static int avaliarExpressao(String s) {
        Deque<integer> pilha = new ArrayDeque<>();
        char operadorAnterior = '+';
        int valor = 0;
        int comprimento = s.length();
        for (int i = 0; i < comprimento; i++) {
            char c = s.charAt(i);
            if (Character.isDigit(c)) {
                valor = valor * 10 + (c - '0');
            }
            if (!Character.isDigit(c) || i == comprimento - 1) {
                switch (operadorAnterior) {
                    case '+': pilha.push(valor); break;
                    case '*': pilha.push(pilha.pop() * valor); break;
                }
                operadorAnterior = c;
                valor = 0;
            }
        }
        int resultado = 0;
        while (!pilha.isEmpty()) {
            resultado += pilha.pop();
        }
        return resultado;
    }
}
</integer>