1031 - Crise de Energia

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

Descrição

1031 - Crise de Energia - beecrowd

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.

Entretanto, atenção: a forma de desligar as cidades é diferenciada. Ao contrário do problema do Josephus, que começa matando o soldado m, aqui sempre começamos desligando a cidade 1, então precisamos chamar nossa recorrência com (T(n - 1, k) + 1) % n, já considerando que a cidade 1 não existe mais. Isso é equivalente a forçar o primeiro passo a desligar a primeira cidade.

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.

C99

#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;
}

C++17

#include <iostream>

using namespace std;

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(cin >> N){
        if (!N) break;

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

        cout << m << endl;
    }

    return 0;
}

JavaScript 12.18

var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.trim().split('\n');

let T = [];
for(let i = 0; i < 2; ++i){
    T[i] = Array(1001);
    T[i].fill(0);
}
for(let i = 2; i < 101; ++i){
    T[i] = Array(1001);
    T[i].fill(-1);
}

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

lines.pop();

while(lines.length){
    let N = parseInt(lines.shift().trim());

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

    console.log(m);
}

Python 3.9

T = [[-1 for _ in range(1001)] for _ in range(101)]

for i in range(2):
    T[i] = [0 for _ in range(1001)]

def sobrevivente(n, k):
    if(T[n][k] == -1):
        T[n][k] = (sobrevivente(n - 1, k) + k) % n
    return T[n][k]

while True:
    try:
        N = int(input())

        if(N == 0):
            break

        m = 1
        while((sobrevivente(N - 1, m) + 1) % N != 12):
            m += 1
        
        print(m)
    except EOFError:
        break