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.
| lado m | posiciones | acumulado |
|---|
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.
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.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ínea | veces | fórmula (k = N − m + 1) |
|---|
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:
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.
UVa 12149, Feynman. Enunciado en https://vjudge.net/problem/UVA-12149; envío en https://vjudge.net/problem/UVA-12149.