URI - 1030 - Ad-Hoc - A Lenda de Flavious Josephus - C++

Plataforma: URI

Problema: 1030

Enunciado:

O problema de Josephus é assim conhecido por causa da lenda de Flavius Josephus, um historiador judeu que viveu no século 1. Segundo o relato de Josephus do cerco de Yodfat, ele e seus companheiros (40 soldados) foram presos em uma caverna, cuja saída foi bloqueada pelos romanos. Eles preferiram suicidar-se a serem capturados, e decidiram que iriam formar um círculo e começar a matar-se pulando de três em três. Josephus afirma que, por sorte ou talvez pela mão de Deus, ele permaneceu por último e preferiu entregar-se aos romanos a suicidar-se.

Linguagem: C++

Solução:

#include <iostream>
#include <vector>

using namespace std;

int main() { 
    
    int casos, contador = 1, n, k;
    cin >> casos;
    
    while (contador <= casos) {
        
        cin >> n >> k;
        vector<int> valores;
        int indice = 0;
        for (int i = 1; i <= n; i++)
            valores.push_back(i);
            
        while (valores.size() != 1) {
            indice = (indice + k - 1) % valores.size();
            valores.erase(valores.begin() + indice);
        }
        
        cout << "Case " << (contador++) << ": " << valores.at(0) << endl;
    }
    
    return 0; 
}