Descrição: Há pessoas em pé em um círculo esperando para serem executadas. A contagem começa em algum ponto do círculo e prossegue ao redor do círculo em uma direção fixa. Em cada etapa, um certo número de pessoas é ignorado e a próxima pessoa é executada. A eliminação prossegue em torno do círculo (que está se tornando cada vez menor à medida que as pessoas executadas são removidas), até que apenas a última pessoa permaneça, a quem é dada liberdade.

Eu pesquisei esse problema de Josephus e o hit da Wikipedia me oferece uma solução de programação dinâmica:f(n,k)=((f(n-1,k)+k-1) mod n)+1, with f(1,k)=1, mas isso só produz o último sobrevivente. Como posso obter a sequência das pessoas executadas? Diga, p (5, 3) = {3,1,5,2,4}.

Além disso, existeO(nlogn) solução em vez de umO(nk) 1?