Estoy seguro de que todos han visto antes que las tazas se pueden apilar en pirámides (y otras formas):

           A    
        A A A   
 A     A A A A  
A A A A A A A A

^{Sí, Adefinitivamente es un personaje adecuado para representar una taza.}

Se pueden agregar nuevas tazas en el suelo, a la derecha de la estructura, o en la parte superior de dos tazas adyacentes. Aquí está la estructura anterior nuevamente, pero todos los lugares disponibles para las tazas nuevas están marcados con _:

         _ A         
        A A A        
 A _ _ A A A A       
A A A A A A A A _ _ _

Digamos que queremos construir un robot que pueda ensamblar estas pilas de tazas. El robot comprenderá dos instrucciones simples para manipular dicha estructura:

• a: Agregue una taza nueva en el primer lugar disponible en orden de lectura de izquierda a derecha (es decir, escanee las filas de arriba a abajo, de izquierda a derecha hasta encontrar un lugar disponible, luego coloque la taza allí). El ejemplo anterior se convertiría en:

           A A   
          A A A  
   A     A A A A 
  A A A A A A A A
  

• r: Retire la primera copa en orden de lectura de izquierda a derecha. El ejemplo anterior se convertiría en:

          A A A  
   A     A A A A 
  A A A A A A A A
  

Resulta que cualquier estructura puede construirse desde cero utilizando solo estas dos operaciones. P.ej

      A
 A   A A
A A A A A

Se puede construir con la secuencia de instrucciones

aaaaaaaaaaaarrrrraa

El ejemplo más grande anterior se puede construir usando

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrraaaaaaarr

Aquí hay uno aún más grande:

    A
   A A                   A
  A A A     A   A       A A
 A A A A   A A A A     A A A A
A A A A A A A A A A   A A A A A

que se puede construir con

aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrraaaaaaaaaaaaaaaaaaarrrrrrrrrrrrrrraaaaaaaaaaaaaarrrrrrrrrrraaaaaaaa

Nota: Si las manchas en el suelo se liberan mediante instrucciones de eliminación, se reutilizarán antes de colocar las tazas a la derecha de todas las tazas existentes. P.ej

aaaarrra

rendirá

A   A

no

    A A

Puedes pensar en el suelo como si estuviera encima de una fila semi-infinita de tazas.

El reto

Dada una estructura de tazas apiladas, devuelve una secuencia que representa las instrucciones para construir esta estructura. Su puntaje principal es la suma de la cantidad de instrucciones para los casos de prueba provistos en la parte inferior. En caso de empate (lo cual es probable, porque estoy convencido de que es posible una solución óptima eficiente), gana la solución más corta.

Aquí hay más detalles sobre las reglas:

• Puede suponer que no hay espacios iniciales en la fila inferior de la entrada, por lo que siempre debe usarse el punto del suelo más a la izquierda para una taza.
• Puede suponer cualquier cantidad razonable de espacios finales (sin espacios, un espacio, rellenado a un rectángulo, relleno a un rectángulo con un solo espacio final).
• Opcionalmente, puede esperar que la entrada termine en una nueva línea final.
• Puede elegir cualquiera de los dos caracteres ASCII imprimibles distintos (0x20 a 0x7E, inclusive) en lugar de Ay espacios (las reglas sobre espacios luego se transfieren al carácter elegido).
• Su salida debe contener solo dos caracteres distintos que representen las operaciones (puede elegir otros caracteres distintos de ay r). Opcionalmente, puede imprimir una nueva línea final.
• Su código debe ser capaz de resolver cualquiera de los casos de prueba a continuación en menos de un minuto en una PC de escritorio razonable (si me toma dos minutos, le daré el beneficio de la duda, pero si toma diez gané 't - Creo que es posible un algoritmo óptimo que resuelva cualquiera de ellos en menos de un segundo).
• No debe optimizar su código para casos de prueba individuales (por ejemplo, codificándolos). Si sospecho que alguien lo está haciendo, me reservo el derecho de cambiar los casos de prueba.

Puede utilizar este script CJam para la operación inversa: tomará una serie de instrucciones de construcción e imprimirá la pila de tazas resultante. (Gracias a Dennis por reescribir el fragmento y acelerarlo significativamente).

Sp3000 también proporcionó amablemente este script Python alternativo para el mismo propósito.

Casos de prueba

Después de cada caso de prueba, hay un número que indica el número óptimo de instrucciones según la respuesta de Ell.

                                       A
                                      A A
                                     A A A
                                    A A A A
                                   A A A A A
                                  A A A A A A
                                 A A A A A A A
                                A A A A A A A A
                               A A A A A A A A A
                              A A A A A A A A A A
                             A A A A A A A A A A A
                            A A A A A A A A A A A A
                           A A A A A A A A A A A A A
                          A A A A A A A A A A A A A A
                         A A A A A A A A A A A A A A A
                        A A A A A A A A A A A A A A A A
                       A A A A A A A A A A A A A A A A A
                      A A A A A A A A A A A A A A A A A A
                     A A A A A A A A A A A A A A A A A A A
                    A A A A A A A A A A A A A A A A A A A A
                   A A A A A A A A A A A A A A A A A A A A A
                  A A A A A A A A A A A A A A A A A A A A A A
                 A A A A A A A A A A A A A A A A A A A A A A A
                A A A A A A A A A A A A A A A A A A A A A A A A
               A A A A A A A A A A A A A A A A A A A A A A A A A
              A A A A A A A A A A A A A A A A A A A A A A A A A A
             A A A A A A A A A A A A A A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A A A A A A A A A A A A A
           A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
          A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
        A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
       A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
     A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
    A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
  A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

820
                                             A
                                            A A
                                           A A A
                                          A A A A
                                         A A A A A
                                        A A A A A A
                                       A A A A A A A
                                      A A A A A A A A
                     A               A A A A A A A A A
                    A A             A A A A A A A A A A
                   A A A           A A A A A A A A A A A
                  A A A A         A A A A A A A A A A A A
         A       A A A A A       A A A A A A A A A A A A A
        A A     A A A A A A     A A A A A A A A A A A A A A
   A   A A A   A A A A A A A   A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

1946

               A
              A A
             A A A
            A A A A
           A A A A A
          A A A A A A
         A A A A A A A
        A A A A A A A A
       A A A A A A A A A               A
      A A A A A A A A A A             A A
     A A A A A A A A A A A           A A A
    A A A A A A A A A A A A         A A A A
   A A A A A A A A A A A A A       A A A A A       A
  A A A A A A A A A A A A A A     A A A A A A     A A
 A A A A A A A A A A A A A A A   A A A A A A A   A A A   A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

2252

                                                         A A
                                                      A A A A
                                                   A A A A A A
                                                A A A A A A A A
                                             A A A A A A A A A A
                                          A A A A A A A A A A A A
                                       A A A A A A A A A A A A A A
                                    A A A A A A A A A A A A A A A A
                                 A A A A A A A A A A A A A A A A A A
                              A A A A A A A A A A A A A A A A A A A A
                           A A A A A A A A A A A A A A A A A A A A A A
                        A A A A A A A A A A A A A A A A A A A A A A A A
                     A A A A A A A A A A A A A A A A A A A A A A A A A A
                  A A A A A A A A A A A A A A A A A A A A A A A A A A A A
               A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

9958

                   A A
                  A A A A
                 A A A A A A
                A A A A A A A A
               A A A A A A A A A A
              A A A A A A A A A A A A
             A A A A A A A A A A A A A A
            A A A A A A A A A A A A A A A A
           A A A A A A A A A A A A A A A A A A
          A A A A A A A A A A A A A A A A A A A A
         A A A A A A A A A A A A A A A A A A A A A A
        A A A A A A A A A A A A A A A A A A A A A A A A
       A A A A A A A A A A A A A A A A A A A A A A A A A A
      A A A A A A A A A A A A A A A A A A A A A A A A A A A A
     A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
    A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
  A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

5540

A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A

10280

 A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A   A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

10320

   A       A       A       A       A       A       A       A       A       A
  A A     A A     A A     A A     A A     A A     A A     A A     A A     A A
 A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A   A A A
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

5794

              A
             A A
            A A A
           A A A A                                               A
          A A A A A                                             A A
         A A A A A A A                                         A A A
        A A A A A A A A               A                       A A A A
       A A A A A A A A A             A A             A       A A A A A   A
      A A A A A A A A A A           A A A           A A     A A A A A A A A
     A A A A A A A A A A A         A A A A         A A A   A A A A A A A A A
    A A A A A A A A A A A A       A A A A A       A A A A A A A A A A A A A A
 A A A A A A A A A A A A A A     A A A A A A     A A A A A A A A A A A A A A A
A A A A A A A A A A A A A A A   A A A A A A A   A A A A A A A A A A A A A A A A

3297

                                                   A A
                                                  A A A
                                                 A A A A
                                                A A A A A
                                               A A A A A A
                                              A A A A A A A
                                             A A A A A A A A
                                            A A A A A A A A A
                                           A A A A A A A A A A     A
                                          A A A A A A A A A A A   A A
                                       A A A A A A A A A A A A A A A A
                                      A A A A A A A A A A A A A A A A A
                                     A A A A A A A A A A A A A A A A A A
      A                             A A A A A A A A A A A A A A A A A A A
     A A                           A A A A A A A A A A A A A A A A A A A A
    A A A             A A         A A A A A A A A A A A A A A A A A A A A A
   A A A A           A A A       A A A A A A A A A A A A A A A A A A A A A A
  A A A A A         A A A A     A A A A A A A A A A A A A A A A A A A A A A A
 A A A A A A     A A A A A A   A A A A A A A A A A A A A A A A A A A A A A A A
A A A A A A A   A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A

4081

                      A
                     A A       A                     A
                    A A A     A A                   A A A                 A
             A     A A A A   A A A A               A A A A     A         A A
  A         A A   A A A A A A A A A A         A   A A A A A   A A       A A A
 A A       A A A A A A A A A A A A A A       A A A A A A A A A A A     A A A A
A A A   A A A A A A A A A A A A A A A A     A A A A A A A A A A A A   A A A A A

4475

                                                             A              
      A           A                       A                 A A A   A       A
     A A         A A   A         A A     A A A   A         A A A A A A     A A
A   A A A A A   A A A A A   A   A A A   A A A A A A   A   A A A A A A A   A A A

5752

Eso significa que el mejor puntaje posible es 64,515 instrucciones.

Pitón 2, 64,515

import sys

input = map(str.rstrip, sys.stdin.readlines())
width = (len(input[-1]) + 1) / 2
for i in range(len(input)):
    indent = len(input) - i - 1
    input[i] = [c != " " for c in input[i][indent::2]]
    input[i] += [False] * (width - indent - len(input[i]))
input = [[False] * n for n in range(width - len(input) + 1)] + input
working_area = [[False] * n for n in range(width + 1)]

def add():
    sys.stdout.write("a")
    for row in range(width + 1):
        for i in range(row):
            if not working_area[row][i] and (
                row == width or
                (working_area[row + 1][i] and working_area[row + 1][i + 1])
            ):
                working_area[row][i] = True
                return
def remove():
    sys.stdout.write("r")
    for row in range(width + 1):
        if True in working_area[row]:
            working_area[row][working_area[row].index(True)] = False
            return

for row in range(width, -1, -1):
    r = input[row]; R = working_area[row]
    for i in range(len(r) - 1, -1, -1):
        if r[i]:
            while not R[i]: add()
        else:
            while R[i]: remove()

Resultados

# 1 - 820   # 2 - 1,946 # 3 - 2,252 # 4 - 9,958 # 5 - 5,540 # 6 - 10,280 # 7 - 10,320 # 8 - 5,794 # 9 - 3,297 # 10 - 4,081 # 11 - 4,475  
   
   
    # 12 - 5,752

Total 64,515

Explicación

Comenzamos con un "área de trabajo" vacía. Escaneamos la entrada en orden de lectura inversa , es decir, de derecha a izquierda y de abajo hacia arriba. Si hay una falta de coincidencia entre la entrada y el área de trabajo en la ubicación actual (es decir, una taza está presente en la entrada pero no en el área de trabajo, o viceversa), agregamos o eliminamos tazas al área de trabajo, de acuerdo con a las reglas, hasta que se resuelva el desajuste, en cuyo punto continuamos a la siguiente ubicación.

Exactitud

Para mostrar que este método es correcto, es decir, que la secuencia resultante genera la estructura de entrada, es suficiente para mostrar que nunca modificamos (es decir, agregamos o eliminamos tazas) las ubicaciones que ya hemos visitado (ya que en cada ubicación que visitamos) , nos aseguramos de que el área de trabajo coincida con la entrada.) Esta es una consecuencia fácil del hecho de que trabajamos en el orden inverso en el que se agregan y eliminan tazas:

• Una taza en la posición l siempre será removido antes de una taza en un lugar que tiene éxito l en orden de lectura, y por lo tanto, que precede l en orden de exploración, por lo tanto, no hay peligro de que la eliminación de un vaso que ya hemos visitado.
• De manera similar, una taza en la ubicación l siempre se agregará antes de una taza que la precede en orden de escaneo, dado que ya hay dos tazas debajo (o que está en la parte inferior); sin embargo, dado que ya habremos visitado estos lugares y, por lo tanto, agregado las tazas necesarias, y dado que, como se señaló anteriormente, no hay peligro de haberlas quitado más tarde, esta condición se cumple, por lo que no hay peligro de agregar una taza en Un lugar que ya hemos visitado.

Óptima

Tenga en cuenta que el efecto de agregar o quitar una taza de una estructura no depende de la secuencia de operaciones utilizadas para generar la estructura, solo de su configuración actual. Como resultado, dada una secuencia óptima S _n = { s ₁ , ..., s _n } de operaciones que generan una determinada estructura, cada segmento inicial de S _n , es decir, cualquier secuencia S _m = { s ₁ , .. ., s _m }, donde m ≤ n , también es una secuencia óptima, para la estructura correspondiente que genera, o de lo contrario habría una secuencia más corta que S _n, generando la misma estructura.

Podemos demostrar que nuestro método es óptimo por inducción en la longitud de la secuencia de generación óptima: nuestro método genera claramente una secuencia óptima para cualquier estructura cuya secuencia de generación óptima esté vacía (solo hay una de esas estructuras: la estructura vacía). Supongamos que nuestro El método genera una secuencia óptima para todas las estructuras cuya secuencia (o secuencias) óptima es de longitud n , y considere una estructura generada por una secuencia óptima S _{n +1} . Queremos mostrar que, dada la estructura generada por S _{n +1} como entrada, nuestro método produce la misma secuencia (o, al menos, una secuencia de la misma longitud).

Como se señaló anteriormente, S _n también es una secuencia óptima y, por hipótesis, nuestro método produce una secuencia óptima dada la estructura generada por S _n como entrada. Supongamos, sin pérdida de generalidad, que S _n es la secuencia producida por nuestro método (si no lo es, siempre podemos reemplazar los primeros n elementos de S _{n +1} con dicha secuencia, y obtener una secuencia de longitud n + 1 que genera la misma estructura.) Sea l la ubicación modificada por la última operación en S _{n +1} (es decir, s _{n +1} ), y dejeS _m será el segmento inicial de S _n , que nuestro programa habrá producido una vez que llegue a l (pero antes de procesar l ). Tenga en cuenta que, dado que las estructuras generadas por S _n y S _{n +1} están de acuerdo en todas las ubicaciones que siguen a l , en orden de lectura, S _m es la misma dada la estructura como entrada.

Si s _{n +1} es a( es decir, adición de copa), entonces no debe haber ninguna ubicación anterior a l , en orden de lectura, donde se pueda agregar una copa a la estructura generada por S _n . Como resultado, la subsecuencia de S _n después de S _m debe ser todo a(ya que una rimplicaría que hay un espacio vacío antes de l , o que S _n no es óptima). Cuando lleguemos a procesar l , necesitaremos agregue exactamente n - m tazas antes de que podamos agregar una taza en l , por lo tanto, la secuencia resultante será S_m , seguido de n - m + 1 ₊₁ (no habrá ningún desajuste después de este punto, por lo tanto, esta es la secuencia completa producida).aelementos, que es igual a S _n

Del mismo modo, si s _{n +1} es r, entonces no debe haber ninguna taza en una ubicación anterior a l , en orden de lectura, en la estructura generada por S _n . Como resultado, la subsecuencia de S _n después de S _m debe ser todo r. Cuando lleguemos al proceso l , necesitaremos eliminar exactamente n - m tazas antes de que podamos quitar la taza en l , por lo tanto, la secuencia resultante será S _m , seguida de n - m + 1 relementos, que nuevamente es igual a S _{n +1} .

En otras palabras, nuestro método produce una secuencia óptima para dicha estructura de entrada y, por lo tanto, por inducción, para cualquier estructura de entrada.

Tenga en cuenta que esto no significa que esta implementación sea la más eficiente. Definitivamente es posible, por ejemplo, calcular el número de tazas que se deben agregar o quitar, en cada punto directamente, en lugar de realizar estas operaciones.

Unicidad

Podemos usar la optimización de nuestro método para mostrar que las secuencias óptimas son, de hecho, únicas (es decir, que no hay dos secuencias óptimas distintas que generen la misma estructura). Usamos, nuevamente, la inducción sobre el tamaño de la secuencia generadora óptima: La secuencia vacía es obviamente la secuencia generadora óptima única de la estructura vacía. Suponga que todas las secuencias generadoras óptimas de longitud n son únicas, y considere una estructura, Σ, generada por las dos secuencias óptimas S _{n +1} y T _{n +1} .

Recuerde que S _n y T _n son ellos mismos óptimos y, por lo tanto, por hipótesis, únicos. Dado que nuestro método produce secuencias óptimas, S _n y T _n pueden considerarse generados por nuestro método. Supongamos que l _S y l _T son las ubicaciones modificadas por la última operación en S _{n +1} y T _{n +1} , respectivamente, y supongamos, sin pérdida de generalidad, que l _S sigue o es igual a l _T en orden de lectura. Desde las estructuras generadas por S _ny T _n concuerda en todas las ubicaciones siguiendo l _S , en orden de lectura, la secuencia producida por nuestro método, dada cualquiera de las estructuras como entrada, una vez que alcanza l _S (pero antes de procesarla), es la misma para ambos; llamar a esta secuencia T .

Dado que la última acción de S _{n +1} modifica l _S , si Σ tiene una copa en l _S, entonces no debe haber ninguna vacante antes de l _S , y si Σ no tiene una copa en l _S, entonces no debe haber ninguna taza antes de l _S , en orden de lectura. Por lo tanto, el resto de la secuencia que genera Σ, después de U , debe consistir en la aplicación repetida de la misma instrucción, dictada por la presencia o ausencia de una taza en l _S (de lo contrario, no sería óptimo). En otras palabras, S _{n +1} y T _{n +1}son iguales (ambos comienzan con U y terminan con dicha secuencia de instrucciones repetidas), es decir, la secuencia generadora óptima de Σ es única y, por inducción, todas las secuencias generadoras óptimas son únicas.