¿Cuál es el algoritmo para resolver el problema del círculo de personas de SRM 147 en TopCoder?

Answer 1

Como las restricciones en numMales y numFemales son muy pequeñas (ambas <= 25). Así que solo podemos simular y encontrar el arreglo.

1. Use una matriz de tamaño numMales + numFemales con todas las entradas marcadas como -1.
-1 que denota que este índice aún no se conoce
2. Ahora tenemos que hacer numFemales ronda.
3. En cada paso, nos gustaría saber la posición de la persona a eliminar. Esto lo podemos hacer por simulación.
4. Una vez que sepamos un índice que se eliminará, podemos estar seguros de que este índice debe ser femenino. Marque esta posición en la matriz por decir 1.
5. Proceda de este modo para las rondas numFemale y asegúrese de omitir el índice en la matriz que ya se eliminó, es decir, el índice que se marca con 1.
6. Al final, habrías marcado en tu matriz las posiciones ocupadas por hembras.

Complejidad: Habría rondas de AO (número de mujeres) y en cada ronda en los pasos de O máximo (K). Entonces la complejidad sería O (numFemales * K) <= 1e8