Vous devez écrire un programme ou une fonction qui prend un entier non négatif ket une liste entière triée Len entrée et en sortie ou renvoie une liste lissée M.

Mest créé à partir de la liste ascendante Len insérant au plus kdes éléments entiers tout en conservant la liste triée. Les entiers insérés doivent être choisis de manière à ce que la différence directe maximale Msoit aussi petite que possible. Nous appellerons cette plus petite valeur "douceur".

Les différences avant de la liste -1 3 8 11 15sont 4 5 3 4et la différence avant maximale est 5.

Avec les 2insertions, la fluidité de 2 10 15est 4et une sortie possible est 2 6 10 11 15avec des différences directes 4 4 1 4.

Contribution

• Un entier non négatif k.
• Une liste entière ascendante Lavec au moins 2 éléments.

Production

• La liste entière croissante M.
• S'il existe plusieurs réponses correctes, envoyez exactement l'une d'entre elles (n'importe laquelle suffit).
• Votre solution doit résoudre tout exemple de cas de test en moins d'une minute sur mon ordinateur (je ne testerai que les cas fermés. J'ai un PC inférieur à la moyenne.).

Exemples

Entrée ( k, L) => Une sortie possible et la différence directe maximale (qui ne fait pas partie de la sortie) entre parenthèses

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)

Il s'agit de code-golf, donc l'entrée la plus courte l'emporte.

Pyth, 28 27 octets

S+Qu?smt%hHrFdC,QtQ>GvzGhvz

Entrée donnée comme:

3
[2, 10, 15]

Manifestation. Harnais de test.

Remarque: Au moment où la question a été posée, il y avait un petit bug dans Pyth lié à l'utilisation de rFdinside u, que je viens de corriger . Le bug rendait impossible l'utilisation à l' Fintérieur u, ce qui n'était certainement pas prévu.

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.

Voici une version qui aurait fonctionné avec l'interprète au moment où la question a été posée. Il fait 28 octets et fonctionne exactement de la même manière:

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

Manifestation.

Git commit de la version appropriée, f6b40e62

Python 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)

Essaie différents incréments maximum d, à partir de 1 et en comptant. Remplit les lacunes de chaque paire (p,x)d'éléments successifs en prenant chaque dnuméro de l'espace. Si Mest plus long que le quota ne le permet, recommence pour essayer un plus haut d. Sinon, retourne une liste des éléments ajoutés et originaux, triés.

Cela fait tous les cas de test sans délai sur ma machine.