Powinieneś napisać program lub funkcję, która przyjmuje nieujemną liczbę całkowitą k
i posortowaną listę liczb całkowitych L
jako dane wejściowe i wyjściowe lub zwraca wygładzoną listę M
.
M
jest tworzony z listy rosnącej L
przez wstawienie co najwyżej k
liczb 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 M
była jak najmniejsza. Nazwamy tę najmniejszą wartość „gładkością”.
Różnice w przód na liście -1 3 8 11 15
są, 4 5 3 4
a maksymalna różnica w przód wynosi 5
.
W przypadku 2
wstawek gładkość 2 10 15
jest, 4
a możliwy wynik jest 2 6 10 11 15
z różnicami do przodu 4 4 1 4
.
Wejście
- Nieujemna liczba całkowita
k
. - Rosnąca liczba całkowita
L
z 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.
rF<seq>
do rozpakowywania krotek dwuelementowych.u
pracowałem inaczej ie
nie istniałem,urGHd
był krótszy niżrhd@d1
. Umieszczę to na stronie sztuczek Pyth.U
.yvz
kończy się niepowodzeniemvz = 0
, alehvz
robi to samo.Python 2, 104
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ąd
liczbę w odstępie. JeśliM
jest 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.
źródło