Spaced Out
Pista
Pista
Observemos las dos configuraciones posibles siguientes:
C.C. C..C
.C.C .CC.
.C.C C..C
C.C. .CC.¿Se ve algo interesante?
Respuesta a la pista
Miremos las filas del primer ejemplo y las columnas del segundo.
¡Definitivamente hay algún patrón!
Solución
Solución
Explicación
La idea clave es que, en cualquier disposición válida, o bien cada fila alterna entre vaca y no-vaca, o bien cada columna alterna entre vaca y no-vaca.
Demostración
Si no hay dos vacas adyacentes, la afirmación vale de forma trivial: tanto las filas como las columnas alternan en este caso.
En caso contrario, supongamos que existen dos vacas colocadas una al lado de la otra. Sin pérdida de generalidad, asumamos que están colocadas de forma horizontal:
?????
?CC??
?????
?????
?????La única forma de rellenar de manera consistente las columnas que contienen a estas dos vacas es alternando entradas de vaca y no-vaca:
?..??
?CC??
?..??
?CC??
?..??A continuación hay que rellenar las columnas restantes. Empezamos con una columna adyacente a una que ya está rellena. Observamos que estas también deben alternar entre vaca y no-vaca; si no lo hacen, inevitablemente se crea un bloque de 2 por 2 con exactamente 1 o 3 vacas, lo cual es inválido. Este mismo razonamiento se aplica por inducción a todas las columnas restantes. De ahí se sigue la afirmación.
C..C.
.CC.C
C..C.
.CC.C
C..C.Para resolver el problema, solo hay que comprobar ambos escenarios: o las filas alternan, o las columnas alternan. Para cada fila (o columna), solo hay dos patrones alternantes posibles, así que elegimos la disposición que maximiza la belleza.
Implementación
Complejidad temporal:
#include <algorithm>
#include <iostream>
using namespace std;
const int MAX_N = 1000;
int grid[MAX_N][MAX_N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) { cin >> grid[i][j]; }
}
// belleza máxima si cada fila alterna entre vaca y no vaca
int rows_alternate = 0;
// belleza máxima si cada columna alterna
int cols_alternate = 0;
// cada fila tiene un patrón alternante de vaca y no vaca
for (int i = 0; i < n; i++) {
int sum[2]{};
// hay dos formas de alternar, índice impar e índice par
for (int j = 0; j < n; j++) { sum[j % 2] += grid[i][j]; }
rows_alternate += max(sum[0], sum[1]);
}
// cada columna tiene un patrón alternante de vaca y no vaca
for (int i = 0; i < n; i++) {
int sum[2]{};
// dos formas de alternar
for (int j = 0; j < n; j++) { sum[j % 2] += grid[j][i]; }
cols_alternate += max(sum[0], sum[1]);
}
cout << max(rows_alternate, cols_alternate) << endl;
}import java.io.*;
import java.util.*;
public class SpacedOut {
public static void main(String[] args) throws IOException {
Kattio io = new Kattio();
int n = io.nextInt();
int[][] grid = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) { grid[i][j] = io.nextInt(); }
}
// belleza máxima si cada fila alterna entre vaca y no vaca
int rowsAlternate = 0;
// belleza máxima si cada columna alterna
int colsAlternate = 0;
// cada fila tiene un patrón alternante de vaca y no vaca
for (int i = 0; i < n; i++) {
int[] sum = new int[2];
// hay dos formas de alternar, índice impar e índice par
for (int j = 0; j < n; j++) { sum[j % 2] += grid[i][j]; }
rowsAlternate += Math.max(sum[0], sum[1]);
}
// cada columna tiene un patrón alternante de vaca y no vaca
for (int i = 0; i < n; i++) {
int[] sum = new int[2];
// dos formas de alternar
for (int j = 0; j < n; j++) { sum[j % 2] += grid[j][i]; }
colsAlternate += Math.max(sum[0], sum[1]);
}
io.println(Math.max(rowsAlternate, colsAlternate));
io.close();
}
// CodeSnip{Kattio}
}n = int(input())
# grid_by_rows[i] es la i-ésima fila
grid_by_rows = [list(map(int, input().split())) for _ in range(n)]
# grid_by_cols[i] es la i-ésima columna
grid_by_cols = zip(*grid_by_rows)
rows_alternate = 0 # belleza máxima si cada fila alterna entre vaca y no vaca
cols_alternate = 0 # belleza máxima si cada columna alterna
for i in range(n):
# cada fila tiene un patrón alternante de vaca y no vaca
row = grid_by_rows[i] # la i-ésima fila
# row[::2] es una lista de cada dos elementos, empezando en el índice 0
# row[1::2] es una lista de cada dos elementos, empezando en el índice 1
rows_alternate += max(sum(row[::2]), sum(row[1::2]))
# cada columna tiene un patrón alternante de vaca y no vaca
col = next(grid_by_cols) # la i-ésima columna
cols_alternate += max(sum(col[::2]), sum(col[1::2]))
print(max(rows_alternate, cols_alternate))Solución en video
Por Maggie Liu