1030 - A Lenda de Flavious Josephus
Um problema Ad Hoc complicadinho que envolve recorrência/recursão.
Descrição
Solução
O problema de Josephus é um problema conhecido na Matemática onde o objetivo é encontrar o sobrevivente num grupo de soldados que vão se matando de pulos em pulos. Tal problema pode ser descrito como: num grupo de n soldados que se matam de k em k, qual deles será o sobrevivente?
Vamos primeiro considerar o primeiro passo dessa matança. Considere que temos n soldados numerados de 0 a n - 1:
0
1
2
3
...
n - 3
n - 2
n - 1
Se estamos removendo de k em k, então o primeiro soldado a ser excluído é o soldado k - 1. Aqui em baixo represento o soldado a ser removido e como que ficam os soldados após sua remoção:
0
1
2
3
...
k - 1
k
k + 1
...
n - 3
n - 2
n - 1
0
1
2
3
...
k - 1 (antes k)
k (antes k + 1)
...
n - 3 (antes n - 2)
n - 2 (antes n- 1)
Veja que os elementos depois de k - 1 mudaram suas posições para compensar a falta do elemento k - 1 e que agora temos n - 1 soldados. Parece que nosso problema de achar o sobrevivente para n soldados pulando de k em k agora se transformou no problema de achar o sobrevivente para n - 1 soldados pulando de k em k, com a diferença de que antes começávamos em 0 e agora vamos começar na posição k (veja ali em cima que o soldado k assumiu o lugar do soldado k - 1 quando ele morreu). Logo, podemos montar a seguinte recorrência:
Onde é necessário aplicar o resto da divisão porque pode ser que esse + k resulte em um valor fora do intervalo [0, n - 1]. O nosso caso base então seria:
Ou seja, quando tem apenas um soldado, ele sobrevive, não importa o tamanho do pulo.
Na linguagem Python, decidi pela versão iterativa da recorrência, já que com os limites estabelecidos no enunciado a pilha de recursão do Python pode estourar.
#include <stdio.h>
int sobrevivente(int n, int k){
if(n == 1) return 0;
return (sobrevivente(n - 1, k) + k) % n;
}
int main(){
int NC, n, k;
scanf("%d", &NC);
for(int i = 1; i <= NC; ++i){
scanf("%d %d", &n, &k);
printf("Case %d: %d\n", i, sobrevivente(n, k) + 1);
}
return 0;
}#include <iostream>
using namespace std;
int sobrevivente(int n, int k){
if(n == 1) return 0;
return (sobrevivente(n - 1, k) + k) % n;
}
int main(){
int NC, n, k;
cin >> NC;
for(int i = 1; i <= NC; ++i){
cin >> n >> k;
cout << "Case " << i << ": " << sobrevivente(n, k) + 1 << endl;
}
return 0;
}var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var lines = input.split('\n');
const sobrevivente = (n, k) => {
if(n == 1) return 0;
return (sobrevivente(n - 1, k) + k) % n;
};
let NC = parseInt(lines.shift());
for(let i = 1; i <= NC; ++i){
let [n, k] = lines.shift().trim().split(' ').map((x) => parseInt(x));
console.log(`Case ${i}: ${sobrevivente(n, k) + 1}`);
}NC = int(input())
for i in range(1, NC + 1):
n, k = [int(x) for x in input().strip().split(' ')]
sobrevivente = 0
for j in range(1, n + 1):
sobrevivente = (sobrevivente + k) % j
print(f"Case {i}: {sobrevivente + 1}")Last updated
Was this helpful?