Powinieneś napisać program lub funkcję, która przyjmuje nieujemną liczbę całkowitą ki posortowaną listę liczb całkowitych Ljako dane wejściowe i wyjściowe lub zwraca wygładzoną listę M.

Mjest tworzony z listy rosnącej Lprzez wstawienie co najwyżej kliczb całkowitych elementów przy zachowaniu sortowania listy. Wstawione liczby całkowite powinny być wybrane w taki sposób, aby maksymalna różnica w przód Mbyła jak najmniejsza. Nazwamy tę najmniejszą wartość „gładkością”.

Różnice w przód na liście -1 3 8 11 15są, 4 5 3 4a maksymalna różnica w przód wynosi 5.

W przypadku 2wstawek gładkość 2 10 15jest, 4a możliwy wynik jest 2 6 10 11 15z różnicami do przodu 4 4 1 4.

Wejście

• Nieujemna liczba całkowita k.
• Rosnąca liczba całkowita Lz co najmniej 2 elementami.

Wynik

• Rosnąca lista liczb całkowitych M.
• Jeśli istnieje wiele poprawnych odpowiedzi, wypisz dokładnie jedną z nich (każda jest wystarczająca).
• Twoje rozwiązanie musi rozwiązać każdy przykładowy przypadek testowy w ciągu minuty na moim komputerze (przetestuję tylko zamknięte przypadki. Mam komputer poniżej średniej.)

Przykłady

Input ( k, L) => Możliwe wyjście i maksymalna różnica w przód (która nie jest częścią wyjścia) w nawiasach

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)

To jest golf golfowy, więc wygrywa najkrótszy wpis.

Pyth, 28 27 bajtów

S+Qu?smt%hHrFdC,QtQ>GvzGhvz

Dane wejściowe takie jak:

3
[2, 10, 15]

Demonstracja. Uprząż testowa.

Uwaga: w momencie, gdy pytanie zostało zadane, w Pyth był mały błąd związany z używaniem rFdwewnątrz u, który właśnie naprawiłem. Błąd uniemożliwił korzystanie z niego w Fśrodku u, co zdecydowanie nie było zamierzone.

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.

Oto wersja, która działałaby z tłumaczem w momencie zadawania pytania. Ma 28 bajtów i działa dokładnie w ten sam sposób:

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

Demonstracja.

Git commit odpowiedniej wersji, 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)

Próbuje różnych maksymalnych przyrostów d, zaczynając od 1 i zliczając w górę. Wypełnia luki w każdej parze (p,x)kolejnych elementów, biorąc co każdą dliczbę w odstępie. Jeśli Mjest dłuższy, niż pozwala na to limit, rekurencja próbuje wypróbować wyższą wartość d. W przeciwnym razie zwraca listę posortowanych i dodanych elementów oryginalnych.

Robi to wszystkie przypadki testowe bezzwłocznie na moim komputerze.