Universidad de Costa Rica. Escuela de Ciencias de la Computación e Informática. CI-0113 Programación II. 2019a
Examen 01 [26-Oct-2019]. Prof: Gr01 Jeisson Hidalgo-Céspedes, Gr02-03 Luis Gustavo Esquivel Quirós.

Rotar la imagen

Escriba un programa en C que rote imágenes cuadradas 90 grados en la dirección de las manecillas el reloj. El programa recibirá en la primera línea de la entrada estándar el tamaño n de la imagen, y luego n × n enteros (pixeles).

Luego el programa debe rotar la imagen en memoria. Escriba al menos una subrutina que realice la rotación en la imagen directamente (in place). Finalmente, el programa debe imprimir la imagen rotada en la salida estándar como se aprecia en los ejemplos de ejecución.

Ejemplo de entrada 1:

3

1 2 3
4 5 6
7 8 9

Ejemplo de salida 1:

7 4 1
8 5 2
9 6 3

Ejemplo de entrada 2:

10

23 13 56 12 27 67 44 10 50 34
51 18 71 87 21 73 89 24 38 28
35 24 41 96 67 52 62 53 82 95
29 55 42 27 70 18 17 42 59 39
91 72 19 78 36 12 83 92 46 30
33 36 86 53 84 62 95 33 54 33
52 76 20 51 40 96 20 38 49 48
17 73 57 35 19 16 84 22 12 18
38 42 99 28 10 93 48 19 25 35
74 72 92 24 16 75 97 40 68 30

Ejemplo de salida 2:

74 38 17 52 33 91 29 35 51 23
72 42 73 76 36 72 55 24 18 13
92 99 57 20 86 19 42 41 71 56
24 28 35 51 53 78 27 96 87 12
16 10 19 40 84 36 70 67 21 27
75 93 16 96 62 12 18 52 73 67
97 48 84 20 95 83 17 62 89 44
40 19 22 38 33 92 42 53 24 10
68 25 12 49 54 46 59 82 38 50
30 35 18 48 33 30 39 95 28 34

Ejemplo de entrada 3:

4

1 2 3 4
4 5 6 7

Ejemplo de salida 3:

invalid data

Nota. Este problema ha sido empleado por Amazon, Microsoft, y Apple en sus entrevistas de empleo con una restricción: debe resolver el problema con O(1) de memoria auxiliar. Es decir, realiza la rotación directamente en la matriz original (in place) usando una o unas pocas variables y no arreglos o matrices auxiliares.

Evaluación

En todos los rubros se evaluarán las buenas prácticas de programación, en especial la reutilización de código.

  1. [25%] Diseño (algoritmo)

  2. [10%] Validación de datos

  3. [15%] Uso correcto de memoria dinámica

  4. [20%] Modularización (al menos 5 subrutinas)

  5. [30%] Rotación de la imagen

  6. [10% extra] Resuelve el problema en el juez en línea (HackerRank)

La calificación máxima del punto 5 anterior será:

  • 100% si resuelve el problema con $O(1)$ de memoria auxiliar, es decir, no usa arreglos auxiliares para rotar la imagen original.

  • 75% si su solución usa menos de $O(n^2)$ de memoria auxiliar, es decir, usa menos de n × n elementos auxiliares para rotar la imagen original.

  • 50% en cualquier otro caso.

Para optar por el 10% extra debe seguir estas instrucciones cuidadosamente:

  1. Tomarle fotografías al examen una vez que haya firmado la hoja de asistencia.

  2. Transcribir sin cambios su solución de las fotografías al juez en línea. Transcriba primero el algoritmo como comentarios de C. Luego transcriba el código fuente intercalándolo entre los comentarios.

  3. Hacer las correcciones que necesite para que su solución compile.

  4. Hacer las correcciones que necesite para que su solución pase los casos de prueba.