Respuestas en código

IMPORTANTE: Este es un tipo de problema de Karel que nunca antes ha aparecido en una olimpiada. En este problema, se te dará un codigo con dos instrucciones en blanco: codifica/encode() y decodifica/decode() las cuales debes implementar. Puedes agregar tantas instrucciones como consideres necesario al código, pero NO debes modificar nada del código que ya está escrito. Si lo modificas, tus envíos no serán tomados en cuenta para ser evaluados. Puedes encontrar el código base al final del problema.

Como bien sabes, Karel es muy bueno para las matemáticas. En la escuela, sus compañeros suelen pedirle que les pase las respuestas de los exámenes. Karel está dispuesto a "ayudar" a sus compañeros, pero no quiere ser descubierto.

Las respuestas de un examen son una lista de números positivos con valores entre \(1\) y \(9999\). Para no ser descubierto, Karel desea inventar un método para codificar esa lista utilizando únicamente montones de un zumbador. Karel considera que el método es mejor mientras menos montones utilice.

El mundo de Karel tiene una lista de montones de zumbadores en la primera fila que representan las respuestas del examen.

Debes implementar una función codifica/encode() que considerando que Karel inicia en la posición (1, 1) viendo al norte, codifique la lista de números y deje en el mundo, en las posiciones que quiera, únicamente montones de 1 zumbador.

También debes implementar una funcion decodifica/decode() que considerando que Karel inicia en la posición (1, 1) viendo al norte, y que el mundo tiene los zumbadores que dejó la función codifica/encode() sea capaz de reconstruir la lista de respuestas.

Para que te quede más claro te recomendamos ver el ejemplo.

Problema

Implementa las funciones codifica/encode() y decodifica/decode() que permitan a Karel codificar una lista de números con montones de zumbadores y posteriormente ser capaz de reconstruirla.

Ejemplo de ejecución

Consideraciones

• El mundo de Karel es un cuadrado de 100x100 sin paredes internas.
• Karel lleva 0 zumbadores en la mochila.
• En la fila 1 del mundo hay una lista de montones de zumbadores que representan las respuestas.
• Las respuestas son valores entre \(1\) y \(9999\).
• Al inicio de la ejecución de codifica/encode() Karel estará en la posición (1, 1) viendo al norte.
• Al inicio de la ejecución de decodifica/decode() Karel estará en la posición (1, 1) viendo al norte y llevará en la mochila la cantidad de zumbadores que llevaba al terminar codifica/encode()¨.
• No importan la orientación ni posición final de Karel.
• Para obtener los puntos debe cumplirse lo siguiente:
  • Al terminar la ejecución de codifica/encode() en el mundo sólo deben haber montones de 1 zumbador.
  • Al terminar la ejecución de decodifica/decode() el mundo debe estar EXACTAMENTE igual que al inicio del problema.
  • NO debes modificar ninguna parte del código inicial que se te da.

Subtareas

En este problema, los casos de cada subtarea se encuentran agrupados. Para obtener el puntaje de una subtarea deberás resolver correctamente todos los casos del grupo.

Para definir cada subtarea, se utilizarán las siguientes variables:

\(N\): Es la cantidad de números que hay, la cantidad de respuestas.

\(S_n\): Es la suma de todas las respuestas.

\(K\): Es la cantidad de montones de 1 zumbador que quedan luego de ejecutar codifica/encode().

• ⭐ Subtarea 1 (25 puntos): Los números son menores o iguales a 100 y \(K <= S_n\)
• Subtarea 2 (25 puntos): Los números son menores o iguales a 100 y \(K <= 8N\)
• Subtarea 3 (25 puntos): \(K <= 4N\)
• Subtarea 4 (25 puntos): \(K <= 3N\)

Código base

Código base en Karel - Pascal

usa rekarel.globales;
iniciar-programa

    define codifica como inicio
        { Implementa tu función para codificar }
    fin;

    define decodifica como inicio
        { Implementa tu función para decodificar }
    fin;

    (*
        ¡¡¡IMPORTANTE!!!
        No debes mover nada debajo de este comentario
    *)

    define avanza-evaluacion como inicio
        si frente-libre entonces avanza
        si-no inicio
            gira-izquierda; gira-izquierda;
            mientras frente-libre hacer avanza;
            gira-izquierda;
            si frente-libre entonces inicio
                avanza;
                gira-izquierda;
            fin;
        fin;
    fin;

    define evalua(zumbadores) como inicio
        mientras orientado-al-sur y no junto-a-zumbador hacer inicio
            avanza-evaluacion;
        fin;
        si orientado-al-sur y junto-a-zumbador entonces inicio
            (* Valida que el monton sea de un zumbador *)
            si no(zumbadores-del-piso == 1) entonces apagate;
            si frente-bloqueado y derecha-bloqueada entonces inicio
                gira-izquierda; gira-izquierda;
            fin
            si-no avanza-evaluacion;
            evalua(sucede(zumbadores))
        fin
        si-no inicio
            gira-izquierda;
            mientras frente-libre hacer avanza;
            gira-izquierda; gira-izquierda;
            decodifica;
            mientras no orientado-al-oeste hacer gira-izquierda;
            mientras frente-libre hacer avanza;
            gira-izquierda;
            mientras frente-libre hacer avanza;
            gira-izquierda; gira-izquierda;
            repetir precede(zumbadores) veces avanza-evaluacion;
        fin;
    fin;

    inicia-ejecucion
        codifica;

        mientras no orientado-al-este hacer gira-izquierda;
        mientras frente-libre hacer avanza;
        gira-izquierda;
        mientras frente-libre hacer avanza;
        gira-izquierda; gira-izquierda;

        evalua(0);

        apagate;
    termina-ejecucion
finalizar-programa

Código base en Karel - Java

import rekarel.globals;
class program {

    void encode(){
        // Implementa tu codigo para codificar
    }

    void decode(){
        // Implementa tu codigo para decodificar
    }

    /*
        ¡¡¡IMPORTANTE!!!
        No debes mover nada debajo de este comentario
    */

    void evalMove(){    
        if (frontIsClear){ move(); }
        else {
            turnleft(); turnleft();
            while (frontIsClear) move();
            turnleft();
            if (frontIsClear){
                move();
                turnleft();
            }
        }
    }

    void eval(beepers){
        while(facingSouth && !nextToABeeper) evalMove();
        if(facingSouth && nextToABeeper){
            if (!(beepersOnFloor == 1)) turnoff();
            if (frontIsBlocked && rightIsBlocked){
                turnleft(); turnleft();
            }
            else evalMove();
            eval(succ(beepers));
        }
        else{
            turnleft(); 
            while (frontIsClear) move();
            turnleft(); turnleft(); turnleft();
            decode();
            while (!facingWest) turnleft();
            while (frontIsClear) move();
            turnleft();
            while (frontIsClear) move();
            turnleft(); turnleft();
            iterate (pred(beepers)) evalMove();
        }
    }

    program () {
        encode();

        while (!facingWest) turnleft();
        while (frontIsClear) move();
        turnleft();
        while (frontIsClear) move();
        turnleft(); turnleft();

        eval(0);
        turnoff();
    }
}