Debería escribir un programa o función que tome un número entero no negativo ky una lista entera ordenada Lcomo entrada y salida o devuelva una lista suavizada M.

Mse crea a partir de la lista ascendente Linsertando en la mayoría de los kelementos enteros mientras se mantiene la lista ordenada. Los enteros insertados deben elegirse de manera que la diferencia máxima hacia adelante Msea ​​lo más pequeña posible. Llamaremos a este valor más pequeño "suavidad".

Las diferencias de avance de la lista -1 3 8 11 15son 4 5 3 4y la diferencia de avance máxima es 5.

Con las 2inserciones, la suavidad de 2 10 15es 4y una salida posible es 2 6 10 11 15con diferencias hacia adelante 4 4 1 4.

Entrada

• Un entero no negativo k.
• Una lista entera ascendente Lcon al menos 2 elementos.

Salida

• La lista entera ascendente M.
• Si existen múltiples respuestas correctas, salga exactamente una de ellas (cualquiera es suficiente).
• Su solución tiene que resolver cualquier caso de prueba de ejemplo en menos de un minuto en mi computadora (solo probaré casos cercanos. Tengo una PC por debajo del promedio).

Ejemplos

Entrada ( k, L) => Una salida posible y la diferencia máxima hacia adelante (que no es parte de la salida) entre paréntesis

0, 10 20 => 10 20 (10)

2, 1 10 => 1 4 7 10 (3)

2, 2 10 15 => 2 6 10 11 15 (4)

3, 2 10 15 => 2 5 8 10 12 15 (3)

5, 1 21 46 => 1 8 15 21 27 33 39 46 (7)

5, 10 20 25 33 => 10 14 18 20 24 25 29 33 (4)

3, 4 4 6 9 11 11 15 16 25 28 36 37 51 61 => 4 4 6 9 11 11 15 16 22 25 28 36 37 45 51 59 61 (8)

15, 156 888 2015 => 156 269 382 495 608 721 834 888 1001 1114 1227 1340 1453 1566 1679 1792 1905 2015 (113)

8, -399 -35 -13 56 157 => -399 -347 -295 -243 -191 -139 -87 -35 -13 39 56 108 157 (52)

5, 3 3 3 => 3 3 3 3 (0)

Este es el código de golf, por lo que gana la entrada más corta.

Pyth, 28 27 bytes

S+Qu?smt%hHrFdC,QtQ>GvzGhvz

Entrada dada como:

3
[2, 10, 15]

Demostración. Prueba de arnés.

Nota: En el momento en que se hizo la pregunta, había un pequeño error en Pyth relacionado con el uso rFdinterno u, que acabo de solucionar. El error hizo imposible su uso en el Finterior u, lo que definitivamente no fue intencionado.

S+Qu?smt%hHrFdC,QtQ>GvzGhvz

                               Implicit:
                               z is the number of insertions, in string form.
                               Q is the input list.
              C,QtQ            Pairs of elements, e.g. [(2, 10), (10, 15)]
           rFd                 d = (a, b) -> range(a, b)
        %hH                    Take every H+1th element of that range
       t                       And throw out the first one.
      m                        Perform this process for each element pair
     s                         And combine the results into one list.

                               The above is a minimal set of additional elements
                               To reduce the maximal difference to H+1.

  u                     hvz    Repeat until the result stops changing, where
                               the prior result is G, H starts at 0 and
                               increases by 1 each repetition, and
                               G is initialized to eval(z)+1.
   ?               >GvzG       If not G[eval(z):], return G. In other words,
                               if the prior result was short enough, stop.
                               Also, this is always false on the initial call.
    smt%hHrFdC,QtQ             Otherwise, recalculate with H incremented.
S+Q                            Take the result, add the original list, and sort.

Aquí hay una versión que habría funcionado con el intérprete en el momento en que se hizo la pregunta. Tiene 28 bytes y funciona exactamente de la misma manera:

S+Qu?smt%hHr.udC,QtQ>GvzGhvz

Demostración.

Git commit de la versión apropiada, f6b40e62

Pitón 2, 104

def f(L,k,d=1):
 M=[];p=L[0]
 for x in L:M+=range(p+d,x,d);p=x
 return M[k:]and f(L,k,d+1)or sorted(L+M)

Intenta diferentes incrementos máximos d, comenzando desde 1 y contando hacia arriba. Rellena los huecos de cada par (p,x)de elementos sucesivos al tomar cada dnúmero en el hueco. Si Mes más largo de lo que permite la cuota, recurre para probar una más alta d. De lo contrario, devuelve una lista de los elementos agregados y originales, ordenados.

Esto hace todos los casos de prueba sin demora en mi máquina.