1031 - Crise de Energia

Mesmo raciocínio do URI 1030 - A Lenda de Flavious Josephus, mas com um raciocínio a mais...

Descrição

Solução

Consulte a página URI 1030 - A Lenda de Flavious Josephus para entender melhor o problema a ser resolvido e a nossa abordagem.

Exceto que neste caso, é como se nós já tivéssemos escolhido nosso sobrevivente, a posição 12, e só estamos interessados em saber de quantos em quantos pulos ele é o último a ficar vivo. Neste caso, podemos experimentar diversos valores de k até que a função retorne o valor 12, o que é perfeitamente possível pois cada análise tem complexidade de O(n) e sabemos (na verdade, não sabemos) que os valores de n que vamos encontrar não estão muito longe dos limites estabelecidos pelo enunciado, ou seja, não vamos lidar com resultados gigantescos.

Com isso, podemos implementar uma função que pesquisa para cada número se o sobrevivente é 12 e retorna caso tenha um resultado positivo. Podemos usar memorização para evitar refazer alguns dos cálculos, mas no geral, é isso.

Para os casos apresentados aqui, a pilha de recursão do Python não estoura, então podemos seguir com a versão recursiva.

#include <stdio.h>

int T[101][1001];

int sobrevivente(int n, int k){
    if(T[n][k] == -1){
        T[n][k] = (sobrevivente(n - 1, k) + k) % n;
    }
    return T[n][k];
}

int main(){
    int N, m;

    for(int i = 0; i < 2; ++i){
        for(int j = 0; j < 1001; ++j){
            T[i][j] = 0;
        }
    }
    for(int i = 2; i < 101; ++i){
        for(int j = 0; j < 1001; ++j){
            T[i][j] = -1;
        }
    }

    while(scanf("%d", &N) != EOF){
        if(!N)  break;

        m = 1;
        while((sobrevivente(N - 1, m) + 1) % N != 12){
            ++m;
        }

        printf("%d\n", m);
    }

    return 0;
}

Last updated

Was this helpful?