Codeforces 271B

codeforces.com/problemset/problem/271/B.

Este problema puede ser resuelto haciendo una criba hasta 10^5, ya que ese sera el mayor numero que aparece en la matriz, y después pre-calcular la distancia de cada numero n al menor numero primo p > n. Con esto pre-calculado  solo basta recorrer cada fila de la matriz, calculando la suma de las distancias de cada uno de los números hasta el menor primo mayor que el numero. Hacer lo mismo con las columnas y quedarse con el menor valor de las filas y las columnas.

Mi solución en Codeforces codeforces.com/contest/271/submission/3099120

Referencias

Articulo sobre la criba de Eratostenes

Anuncios

2 comentarios en “Codeforces 271B

  1. …de donde deduces que el limite suficiente es int N = (int) (1e5)+3;

    En el problema especifican que los numeros en la matriz son maximo 10^5. Hay que establecer el limite en el menor numero primo mayor que 10^5 para calcular la distancia de 10^5 a ese numero, que es precisamente 10^5 + 3.

Comentar

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s