← Volver a los ejercicios

feynman: cuántos cuadrados caben en una cuadrícula

UVa 12149, Feynman, pregunta cuántos cuadrados distintos hay en una cuadrícula de N × N casillas. Con N = 2 la respuesta es 5: cuatro de lado 1 y uno de lado 2. Primero se cuentan a mano, lado por lado; después se cuentan las vueltas de los tres ciclos que hacen lo mismo.

1. Lado por lado

N = 4
esquina superior izquierda posible un cuadrado de lado m
Pase el puntero por una esquina para ver el cuadrado que empieza ahí.

posiciones:
lado mposicionesacumulado

2. Los tres ciclos: lado, fila y columna

El ciclo de m escoge el lado; los de f y c recorren las esquinas donde ese lado cabe. Cada vez que corre la línea 6 se cuenta un cuadrado, y la cuadrícula muestra cuál.

m = – f = – c = – cuenta = –
Paso 0 de 0
Cada cabecera de for cuenta como su condición y se cuenta cada vez que se evalúa, también la última, la que da falso. La inicialización y el incremento no se cuentan aparte.

3. El conteo línea a línea

Escriba cuántas veces corre cada línea con el N elegido. Puede comprobar contra los contadores de la parte 2, pero la idea es llegar con la tabla de la parte 1: congele m, cuente lo de adentro y sume.

líneavecesfórmula (k = N − m + 1)
Al sumar las siete líneas,
T(N) = N(N + 1)(2N + 1)/3 + N² + 3N + 4
y con N = da . El término que crece más rápido es 2N³/3: el conteo con tres ciclos es Θ(N³).

4. De la tabla a la fórmula

La línea 6 corre una vez por cada cuadrado, así que su conteo es la respuesta. Para el lado m hay (N − m + 1)² esquinas; con k = N − m + 1, cuando m va de 1 a N, k va de N a 1:

Σm=1..N (N − m + 1)² = Σk=1..N k² = N(N + 1)(2N + 1)/6

Con N = 2 da 2 · 3 · 5 / 6 = 5 y con N = 8 da 8 · 9 · 17 / 6 = 204, los dos valores de la salida de ejemplo. La fórmula responde con un número fijo de operaciones, sin importar N; los tres ciclos hacen Θ(N³). Con el N más grande que permite el enunciado, 100, la línea 6 corre 338.350 veces por caso.

5. El problema en el juez

UVa 12149, Feynman. Enunciado en https://vjudge.net/problem/UVA-12149; envío en https://vjudge.net/problem/UVA-12149.

El parámetro es N, el número de casillas por lado, de 1 a 100. La propiedad que hace funcionar el conteo es que un cuadrado queda fijo con su lado y su esquina superior izquierda, y la esquina solo puede ir donde el cuadrado no se sale. La trampa está en la palabra distintos: no son solo las N² casillas, son los cuadrados de todos los lados, y con N = 2 la respuesta es 5, no 4. La entrada trae varios casos y termina con una línea que tiene 0, que no se procesa.