Dada una matriz de tamaño m * n, ¿cómo ubica a k estudiantes de tal manera que se minimice la trampa en un examen?

Answer 1

Este problema se puede resolver con programación dinámica sobre subconjuntos. Debe colocar k estudiantes de tal manera que ningún estudiante esté adyacente entre sí (izquierda, derecha, arriba o abajo).

Aquí está el estado que tengo en mente.
f (fila actual, subconjunto de esta fila (perfil), número de estudiantes llenos)

desde este estado puede llenar un puesto de estudiante (siempre que esté disponible a izquierda y abajo) y marcar este puesto como ocupado y a la derecha y arriba (el perfil de la siguiente fila) como no disponible. Mover a la posición + 2. La respuesta final es f (m + 1,0, k)

Podemos representar subconjuntos como máscaras de bits. Entonces la matriz se vuelve de tamaño [m + 1] [(1 << n)] [k + 1].

Referencia:
Foros de TopCoder (Consulte la publicación del recuento de capas + perfil de capa)

Esta también es una cuestión de SPOJ.
Juez Esfera Online (SPOJ)

Answer 2

Si he entendido su pregunta correctamente, entonces algo como esto podría funcionar.
Este es un tipo de enfoque codicioso incremental que primero arreglamos a los estudiantes antes de comenzar con (r + 1) estudiante.
para cada estudiante
para cada posición vacía,
calcule la suma de distancias de cada estudiante colocado y si eso es mayor que el máximo que tenemos almacenamos esta coordenada y la suma máxima que tenemos hasta ahora
finalmente colocamos al alumno actual en la coordenada guardada

O algo así como un dibujo gráfico dirigido por la Fuerza

Esto puede funcionar de esta manera, todos los estudiantes son nodos con repulsión de culombio entre ellos, que es una fuerza cuadrada inversa.
while (diferencia de energía> umbral)
para cada alumno
calcule la suma de la fuerza que actúa sobre el estudiante actual de cada otro estudiante.
calcule la velocidad multiplicando la fuerza con cierto paso de tiempo y amortiguamiento.
calcule la coordenada final del alumno actual en función de la velocidad y el paso de tiempo.
finalmente agregue la energía calculada para este estudiante a la energía para esta iteración
recalcular la diferencia de energía

Answer 3

int 2d array para almacenar 4 valores para cada variable 0: sin vecino 1: diagnosticar vecino 2: horizontol o vecino vertical 4: asiento lleno ahora cada vez crear índice aleatorio para fila y columna y la primera prioridad dada a ningún vecino hasta que expire Luego prioridad dada a diagnosticar hasta que caduque en el último horizontol o vecino vertical
repita los pasos anteriores hasta contar = k

Answer 4

Ya que la pregunta aún está abierta. Yo diría (1, n) matriz con n / 10 cámaras y n / 10 invigiladores mirando las cámaras si n> 10. No hace falta decir que cada cámara se centra en 10 estudiantes. Si n <10, entonces n cámaras con n individuos.

Lo que sea.