Medio · simulación
El círculo de José
Las reglas son cruelmente simples: cuenta k personas vivas desde la actual, la k-ésima sale del círculo, y el conteo se reanuda con la que va detrás. Sin fórmula ni astucia — solo contabilidad fiel, que es justo para lo que sirve un ordenador.
En una fraseMantén <code>alive[n]</code> y un cursor. Recorre el círculo contando vivos; al llegar al k-ésimo, escribe, márcalo muerto y reinicia el conteo en la posición siguiente (<code>cur = (cur + 1) % n</code>).
El problema
Entrada: Una línea con n y k (1 ≤ n ≤ 100, 1 ≤ k ≤ 100). Las personas van numeradas 1..n; se cuenta desde la persona 1 y la k-ésima viva es eliminada, repetidamente, hasta que no quede ninguna.
Salida: El orden de eliminación: n números separados por un espacio (el último es el superviviente).
Ejemplos:
| Entrada | Salida |
|---|---|
5 3 | 3 1 5 2 4 |
1 7 | 1 |
Con n = 5, k = 3: cuenta 1, 2, 3 — la persona 3 sale. Se reanuda en 4: 4, 5, 1 — la 1 sale. Se reanuda en 2: 2, 4, 5 — la 5 sale. De nuevo desde 2 (quedan 2 y 4): 2, 4, 2 — la 2 sale; la superviviente es la 4.
Tu solución
Entrada personalizada para «Ejecutar mi entrada»
La corrección corre en tu navegador contra pruebas ocultas. Un bucle infinito se corta a los 3 segundos — aun así, asegúrate de que todo bucle tenga salida. Tu código se guarda solo mientras escribes.
¿Atascado? Pistas
Pista 1 — El círculo es solo módulo
La persona i vive en el índice i−1, y la posición siguiente a n−1 es la 0: cur = (cur + 1) % n. Esa única expresión es todo el círculo. Todo problema circular que conozcas — buffers anillos, planificación round-robin — es este mismo módulo con otras ropas.
Pista 2 — Cuenta solo a los vivos
El paseo interno debe saltar las posiciones muertas sin gastar cuenta: if (alive[cur]) { count++; ... } y avanzar. Si los muertos consumieran cuentas, las eliminaciones se repetirían y el orden se autodestruiría a la tercera ronda — el ejemplo del juez lo caza al instante.
Pista 3 — El conteo se reanuda tras el caído
Tras eliminar a la persona p, el siguiente conteo empieza en la persona posterior a p — con tu cursor apuntando a p, es un cur = (cur + 1) % n más antes de la siguiente ronda. Volver a contar desde p da la misma respuesta cuando los vecinos de p viven... y diverge en silencio más tarde. Sigue el ejemplo a mano antes de confiar.
Solución (¡inténtalo primero!)
#include <iostream>
using namespace std;
bool alive[105];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) alive[i] = true;
int cur = 0;
for (int round = 0; round < n; round++) {
int count = 0;
while (true) {
if (alive[cur]) {
count++;
if (count == k) break;
}
cur = (cur + 1) % n;
}
alive[cur] = false;
cout << cur + 1;
if (round < n - 1) cout << " ";
cur = (cur + 1) % n;
}
cout << endl;
return 0;
}Dos ideas de contabilidad sostienen el problema entero: un array booleano como única verdad de quién queda, y el módulo como círculo. Ambas son bestias de carga — el mismo patrón alive[] marca la criba en Contar primos, y el mismo módulo mueve los buffers anillo. Cuando una historia puede rejugarse paso a paso, la simulación no es la opción ingenua: es la verificable.
Análisis profundo
Por qué funciona
A esta escala no hace falta forma cerrada — las reglas son tan simples que pueden rejugarse con fidelidad. Un array booleano alive[] es la única verdad de quién queda; el círculo es (cur + 1) % n; el conteo solo cuenta posiciones vivas. La simulación convierte el puzle en contabilidad, y la contabilidad no discute con el juez.
El coste
O(n × k) en el peor caso (cada ronda recorre hasta k posiciones), O(n) de espacio — para n = 100, k = 100 son 10.000 pasos, trivial.
Dónde falla
- Contar posiciones muertas como vivas: las eliminaciones empiezan a repetirse y el orden se autodestruye — visible desde la tercera eliminación del ejemplo.
- Reiniciar el conteo en la persona recién eliminada en vez de en la siguiente: coincide una ronda o dos por casualidad, y diverge en silencio después.
- Error de uno en k: «cada k-ésima» incluye a quien empieza (con k = 1 se elimina a la persona corriente en cada ronda, dando 1 2 … n).
Siguiente paso
La contabilidad alive[] es la misma máquina que marca la criba en Contar primos; el paseo con módulo es el corazón del buffer anillo. Otro proceso fiel paso a paso que ya posees: Ordenamiento burbuja.
Dos cosas para recordar
- Un círculo es un array más (cur + 1) % n — nada más.
- La simulación es la herramienta honesta cuando las reglas son simples y las fórmulas no están al alcance.
🐞 Esta versión falla: ábrela y pruébala
También cuenta a los muertos: las eliminaciones se repiten y el orden se autodestruye
#include <iostream>
using namespace std;
bool alive[105];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) alive[i] = true;
int cur = 0;
for (int round = 0; round < n; round++) {
for (int step = 0; step < k; step++) { // bug: no alive check
cur = (cur + 1) % n;
}
cur = (cur - 1 + n) % n; // compensate — still wrong
alive[cur] = false;
cout << cur + 1;
if (round < n - 1) cout << " ";
cur = (cur + 1) % n;
}
cout << endl;
return 0;
}