Este artigo documenta a resolução de múltiplos problemas de algoritmos, com foco em variantes do Problema de Josephus e recursão.

Problema 1: Seleção do Macaco Líder (Josephus)

Para a primeira sbutarefa, a solução é baseada no Problema de Josephus. Utiliza-se uma abordagem iterativa. A fórmula fundamental é f[i] = (f[i-1] + m) % i, onde f[i] armazena o índice (base zero) do sobrevivente em um círculo de tamanho i. A lógica parte do final: com uma pessoa, o sobrevivente é o índice 0. Para cada tamanho subsequente, calcula-se a nova posição do sobrevivente com base no anterior.

Para a subtarefa onde m = 1, a resposta é simplesmente o último indivíduo.

Para m = 2, uma relação pode ser observada. A resposta é dada por (n - 2^floor(log2(n))) * 2 + 1.

#include <iostream>
#include <cmath>
using namespace std;

long long josephus_iterativo(long long total, long long passo) {
    long long sobrevivente = 0;
    for (long long i = 2; i <= total; ++i) {
        sobrevivente = (sobrevivente + passo) % i;
    }
    return sobrevivente + 1; // Converte para índice base 1
}

long long resolver_caso_m2(long long total) {
    long long potencia = 1;
    while (potencia <= total / 2) {
        potencia <<= 1;
    }
    return (total - potencia) * 2 + 1;
}

int main() {
    long long n, m;
    cin >> n >> m;

    if (n <= 10000000) {
        cout << josephus_iterativo(n, m);
    } else if (m == 1) {
        cout << n;
    } else if (m == 2) {
        cout << resolver_caso_m2(n);
    }
    return 0;
}

Problema 2: Pessoas Boas vs. Más (Josephus Dinâmico)

Este problema requer encontrar o passo mínimo m tal que, no processo de eliminação tipo Josephus, todas as k "pessoas más" sejam eliminadas antes de qualquer uma das k "pessoas boas". A abordagem é simular o prcoesso para cada m candidato, mas de forma otimizada, usando módulo para determinar o próximo a ser eliminado.

#include <iostream>
using namespace std;

int main() {
    int k;
    cin >> k;
    int total = 2 * k;
    int passo = 0;

    while (true) {
        passo++;
        int posicao = 0;
        bool todos_maus_mortos = true;

        for (int i = 0; i < k; ++i) {
            posicao = (posicao + passo - 1) % (total - i);
            if (posicao < k) {
                todos_maus_mortos = false;
                break;
            }
            if (i == k - 1) {
                break;
            }
        }

        if (todos_maus_mortos) {
            cout << passo << endl;
            return 0;
        }
    }
}

Problema 3: Formigas na Árvore (Divisão Recursiva)

Dado um número inicial de formigas N e um divisor K, as formigas se dividem em dois grupos de tamanho (N - K) / 2 e (N - K) / 2 + K se (N - K) for par e N >= K + 2. Caso contrário, o processo para. A solução é recursiva.

#include <iostream>
using namespace std;

long long contar_colonias(long long n, long long k) {
    if ((n - k) % 2 != 0 || n < k + 2) {
        return 1;
    }
    long long metade = (n - k) / 2;
    return contar_colonias(metade, k) + contar_colonias(metade + k, k);
}

int main() {
    long long n, k;
    cin >> n >> k;
    cout << contar_colonias(n, k) << endl;
    return 0;
}

Problemas Adicionais

Pedras de Anergia: A solução ótima requer programação dinâmica com otimização por inclinação.

Circuito Mais Curto: A solução utiliza divisão e conquista combinada com uma tabela de Mínimos Esparsos (Sparse Table).