El Problema De Josep

-------------------------------------------------
09/02/13
-------------------------------------------------
Problema de Flavio Josefo
El problema de Flavio Josefo es un problema teórico que se encuentra en matemática y ciencias de la computación. El nombre hace referencia a Flavio Josefo, un historiador judío que vivió en el siglo I. Según lo que cuenta Josefo, él y 40 soldados camaradas seencontraban atrapados en una cueva, rodeados de romanos. Prefirieron suicidarse antes que ser capturados y decidieron que echarían a suertes quién mataba a quién. Los últimos que quedaron fueron él y otro hombre. Entonces convenció al otro hombre que debían entregarse a los romanos en lugar de matarse entre ellos. Josefo atribuyó su supervivencia a la suerte o a la Providencia.1-------------------------------------------------
Planteamiento
El problema plantea lo siguiente:
Hay  personas paradas en un círculo esperando a ser ejecutadas. Después de que ejecutan a la primera persona, saltean a  personas y la persona número  es ejecutada. Entonces nuevamente, saltean a  personas y la persona número  es ejecutada. La eliminación continúa alrededor del círculo (que se hace cada vez máspequeño a medida que más personas son eliminadas del mismo) hasta que sólo queda la última, que es liberada.
El objetivo es escoger el lugar inicial en el círculo para sobrevivir (es el último que queda), dados  y .
-------------------------------------------------
Variantes
Si Josefo tenía un cómplice, el problema consistía en encontrar los lugares de los dos últimos sobrevivientes (aquelloscuya conspiración aseguraría su supervivencia).

Ejemplo

Preguntas

Problema
Organizar un concurso de programación colegial es un trabajo extenuante. Un refrán conocido es el que dice que un tonto puede hacer más preguntas que las que cien sabios pueden contestar. Y en un concurso de programación, las preguntas la hacen cien sabios.

El jurado del Tercer Concurso de Programación de laUniversidad Ural siendo lo suficientemente ingenioso, ha simplificado el trabajo. ¡Inventaron un algoritmo que ayuda a responder TODAS las preguntas! Aún más, este algoritmo garantiza que la misma pregunta obtenga siempre la misma respuesta (algo que normalmente es muy complicado). De acuerdo al algoritmo, los miembros del jurado empiezan a quitar letras de la pregunta en el siguiente orden:
1. Empezando del primero, cuentan n-1 caracteres (espacios, signos de puntuación, etc., también son considerados) y quitan el n-ésimo.
2.  Al terminar la cadena, se continúa desde el inicio.
3.  Después de borrar un caracter, la cuenta se reinicia desde el que sería (n+1)-ésimo en la cuenta anterior.
4.  Si el último caracter es un signo de interrogación (“?”), la respuesta es “Yes”. Si esun espacio, entonces la respuesta es “No”. Cualquier otro caracter dará una respuesta “No comments”.
Debes ayudar al jurado a escribir un programa que se encargue del duro trabajo de contestar preguntas. El número secreto n no será anunciado, ni siquiera después de finalizado el concurso. Tu programa debe usar n = 1999.

Por ejemplo, tomando la cadena “Is it a good question?” (longitud 22) loscaracteres serán contados de la siguiente forma: “Is it a good question?Is it ... quest”; y se elimina la “i”. Después se reinicia desde “on?Is it...” etc., repitiendo hasta que sola la “s” queda (por lo que la respuesta es “No comments”, como de costumbre). 
Entrada
La entrada es una pregunta, que puede ser cualquier archivo de texto que contenga por lo menos un caracter (fin de archivo no seconsidera un caracter). Cada caracter de la entrada (excepto los fin de línea) forman parte de la pregunta. Deberás leer la pregunta de la entrada de texto predeterminada.

El tamaño de la entrada no excederá los 30,000 caracteres. 
Salida
La respuesta.

Solución: Lo que estamos buscando es equivalente al problema de Joseph, sólo que con caracteres en lugar de personas. La cantidad de...