URI PROBLEMA 1030 - A Lenda de Flavious Josephus SOLUÇÃO EM C

URI Online Judge | 1030

A Lenda de Flavious Josephus

Por Neilor Tonin, URI  Brasil

Timelimit: 1

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.

Entrada

Haverá NC (1 ≤ NC ≤ 30 ) casos de teste. Em cada caso de teste de entrada haverá um par de números inteiros positivos n (1 ≤ n ≤ 10000 ) e k (1 ≤ k ≤ 1000). O  número n representa a quantidade de pessoas no círculo, numeradas de 1 até n. O número k representa o tamanho do salto de um homem até o próximo homem que será morto.

Segue um exemplo com 5 homens e um salto = 2.

Neste exemplo o elemento que restará após as eliminações é 3.

Saída

Para cada caso de teste de entrada será apresentada uma linha de saída no seguinte formato: Case n: m tendo sempre um espaço antes do n e do m.

#include <stdio.h>

#include <string.h>

#define MAX_N 10001

#define MAX_K 1001

int T[MAX_N][MAX_K];

int survivor(int n, int k)

{

    if (T[n][k] >= 0)

        return T[n][k];

    if (n == 1)

        T[n][k] = 0;

    else

        T[n][k] = (survivor(n - 1, k) + k) % n;

    return T[n][k];

}

int main()

{

    int NC, n, k;

    int i;

    memset(T, -1, MAX_N * MAX_K * sizeof(int));

    scanf("%d", &NC);

    for (i = 0; i < NC; ++i) {

        scanf("%d %d", &n, &k);

        printf("Case %d: %d\n", i + 1, survivor(n, k) + 1);

    }

    return 0;

}