Lista liczb nazywana jest monotonicznie rosnącym (lub nie malejącym), jeśli każdy element jest większy lub równy pierwiastkowi przed nim.
Na przykład 1, 1, 2, 4, 5, 5, 5, 8, 10, 11, 14, 14
monotonicznie rośnie.
Biorąc pod uwagę monotonicznie rosnącą listę dodatnich liczb całkowitych, które mają dowolną liczbę pustych miejsc oznaczonych przez ?
, wypełnij puste miejsca dodatnimi liczbami całkowitymi, tak aby na liście było jak najwięcej unikalnych liczb całkowitych, ale nadal monotonicznie rośnie.
Istnieje wiele sposobów osiągnięcia tego celu. Każda jest ważna.
Wyświetl wynikową listę.
Na przykład , jeśli dane wejściowe to
?, 1, ?, 1, 2, ?, 4, 5, 5, 5, ?, ?, ?, ?, 8, 10, 11, ?, 14, 14, ?, ?
gwarantuje się, że bez pustych miejsc lista będzie monotonicznie powiększana
1, 1, 2, 4, 5, 5, 5, 8, 10, 11, 14, 14
a Twoim zadaniem jest przypisanie dodatnich liczb całkowitych do każdej z nich,
?
aby zmaksymalizować liczbę różnych liczb całkowitych na liście, jednocześnie nie zmniejszając jej.Jedno niepoprawne zadanie to
1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 8, 10, 11, 14, 14, 14, 14, 14
ponieważ chociaż nie zmniejsza się, ma tylko jedną unikalną liczbę całkowitą niż wejście, mianowicie
3
.W tym przykładzie można wstawić sześć unikatowych liczb całkowitych dodatnich i nie zmniejszać listy.
Kilka możliwych sposobów to:1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 6, 7, 8, 8, 8, 10, 11, 12, 14, 14, 15, 16 1, 1, 1, 1, 2, 3, 4, 5, 5, 5, 5, 6, 6, 7, 8, 10, 11, 13, 14, 14, 20, 200
Każdy z nich (i wiele innych) byłby prawidłowym wyjściem.
Wszystkie puste miejsca muszą zostać wypełnione.
Nie ma górnego limitu liczb całkowitych, które można wstawić. Jest ok, jeśli w notacji naukowej drukowane są bardzo duże liczby całkowite.
Zero nie jest dodatnią liczbą całkowitą i nigdy nie powinno być wstawiane.
Zamiast ?
was może wykorzystać dowolną stałą wartość, która nie jest liczbą całkowitą dodatnią, takich jak 0
, -1
, null
, False
, lub ""
.
Najkrótszy kod w bajtach wygrywa.
Więcej przykładów
[input]
[one possible output] (a "*" means it is the only possible output)
2, 4, 10
2, 4, 10 *
1, ?, 3
1, 2, 3 *
1, ?, 4
1, 2, 4
{empty list}
{empty list} *
8
8 *
?
42
?, ?, ?
271, 828, 1729
?, 1
1, 1 *
?, 2
1, 2 *
?, 3
1, 3
45, ?
45, 314159265359
1, ?, ?, ?, 1
1, 1, 1, 1, 1 *
3, ?, ?, ?, ?, 30
3, 7, 10, 23, 29, 30
1, ?, 2, ?, 3, ?, 4
1, 1, 2, 3, 3, 3, 4
1, ?, 3, ?, 5, ?, 7
1, 2, 3, 4, 5, 6, 7 *
1, ?, 3, ?, 5, ?, ?, 7
1, 2, 3, 4, 5, 6, 7, 7
1, ?, ?, ?, ?, 2, ?, ?, ?, ?, 4, ?, 4, ?, ?, 6
1, 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 5, 6, 6
98, ?, ?, ?, 102, ?, 104
98, 99, 100, 101, 102, 103, 104 *
źródło
Odpowiedzi:
Haskell , 41 bajtów
f
pobiera listę i zwraca listę, gdzie 0 oznacza?
s.Zasadniczo, pierwsza lista skanowania od lewej, zastępując zera o jeden więcej niż poprzedni element (lub 0 na początku); następnie skanuj od prawej, zmniejszając zbyt duże elementy, aby zrównać się z tymi po prawej.
Wypróbuj online! (z otoki do konwersji
?
s.)źródło
Mathematica, 84 bajty
Czysta funkcja przyjmująca listę jako argument, w której puste miejsca są oznaczane przez
Null
(jak w{1, Null, Null, 2, Null}
) lub usuwane całkowicie (jak w{1, , , 2, }
), i zwraca odpowiednią listę (w tym przypadku{1, 2, 2, 2, 3}
).Okazuje się, że używam tego samego algorytmu, co w odpowiedzi Haskella Ørjana Johansena : najpierw zamień każdy
Null
o jeden więcej niż liczba po lewej (//.{a___,b_,,c___}:>{a,b,b+1,c}
), a następnie dowolną zbyt dużą liczbę na liczbę po prawej (//.{a___,b_,c_,d___}/;b>c:>{a,c,c,d}
). Aby poradzić sobie z możliwymiNull
literami s na początku listy, zaczynamy od przygotowania0
({0,##}&@@#
), wykonania algorytmu, a następnie usunięcia początkowej0
(Rest
).Tak, wybrałem
Null
zamiastX
lub coś w tym rodzaju, aby zapisać dosłownie jeden bajt w kodzie (ten, który w innym przypadku znajdowałby się między przecinkamib_,,c___
).źródło
?, 2
. Podejrzewam, że wtedy produkowałbyś2, 2
zamiast właściwego1, 2
.C 160
To nigdy nie wygra, ale:
Pobiera listę z argumentów wiersza poleceń.
źródło
05AB1E ,
312313 bajtówOszczędność 10 bajtów dzięki Grimy
Wypróbuj online!
Wyjaśnienie
źródło
}}
mogą]
zaoszczędzić 2 bajty; iõ-)R
może być)˜R
zapisanie dodatkowego bajtu.Pip ,
252321 bajtówPobiera dane wejściowe jako wiele oddzielonych spacjami argumentów wiersza polecenia. Wysyła listę wyników o jeden numer w wierszu. Wypróbuj online! (Sfałszowałem wiele argumentów wiersza poleceń, ponieważ dodanie 25 argumentów do TIO byłoby utrudnione, ale działa również tak, jak reklamowano).
Wyjaśnienie
Wykonujemy dwa przejścia. Najpierw zamieniamy każdy
?
ciąg s na wejściu na sekwencję rozpoczynającą się od poprzedniego numeru na liście i zwiększającą się o jeden za każdym razem:Potem znów się zapętlamy; dla każdego numeru drukujemy jego minimum i wszystkie liczby po jego prawej stronie. To obniża zbyt wysokie liczby, aby utrzymać monotoniczność.
źródło
Python 2 z NumPy, 163 bajty
Zaoszczędzono 8 bajtów dzięki @wythagoras
Zero używane do oznaczania pustych miejsc
Bardziej czytelne z komentarzami:
źródło
if l[a]>l[b]:l[a]=l[b]
może być,l[a]=min(l[a],l[b])
a potem może być na linii wcześniej. Oznacza to również, że całą linię można umieścić powhile
. I myślęl=input()
il=[1]+l
może byćl=[1]+input()
(Ogólnie: jeśli używasz dwóch poziomów wcięcia, możesz użyć spacji i tabulacji zamiast spacji i dwóch spacji w Pythonie 2 (patrz codegolf.stackexchange.com/a/58 ) )len(z)-i:f(z[i-1],z[i]);i+=1
rozpoczynania od i = 1.PHP,
9577716968 bajtówpobiera dane z argumentów wiersza poleceń, drukuje listę rozdzieloną spacjami. Uruchom z
-nr
.awaria
$n
jest prawdą dla każdego łańcucha oprócz pustego łańcucha i"0"
.$n>0
jest prawdziwe dla liczb dodatnich - i ciągów je zawierających.źródło
Perl 6 , 97 bajtów
Dane wejściowe to albo lista wartości, albo ciąg oddzielony spacjami, gdzie
?
służy do zastąpienia wartości do zamiany.Dane wyjściowe to ciąg rozdzielany spacjami z końcową spacją.
Spróbuj
Rozszerzony:
źródło
$"
zamiast' '
golić bajt. Czy to działa tutaj?$!
. ($/
istnieje, ale jest używany do$1
→$/[1]
i$<a>
→$/{ qw< a > }
)JavaScript (ES6), 65 bajtów
Ponieważ chciałem użyć
reduceRight
. Objaśnienie:map
Zastępuje każdą wartość fałsz jedną o więcej niż poprzednią, a następniereduceRight
wraca od końca, upewniając się, że żadna wartość nie przekracza następującej wartości.źródło
Q, 63 bajty
{1_(|){if[y>min x;y-:1];x,y}/[(|){if[y=0;y:1+-1#x];x,y}/[0,x]]}
Zasadniczo ten sam algorytm, co odpowiedź Haskella Ørjana Johansena .
Wykorzystano min vs last, aby zapisać jeden bajt, ponieważ można założyć, że ostatnim elementem będzie element min, biorąc pod uwagę malejący rodzaj tablicy.
źródło
TI-Basic (TI-84 Plus CE), 81 bajtów
Prosty port odpowiedzi Haskell firmy Ørjan Johansen na TI-Basic. Używa 0 jako wartości zerowej. Pobiera dane z L 1 .
Wyjaśnienie:
źródło
Java 8,
199164 bajtówZmienia tablicę wejściową zamiast zwracać nową, aby zapisać bajty.
Używa
0
zamiast?
.Wypróbuj online.
Wyjaśnienie:
źródło
Python 2 ,
144124119 bajtówWypróbuj online!
Używa
0
zamiast?
źródło
b=filter(abs,l[n:])
równa sięb=l[n:]
?JavaScript (ES6), 59
Funkcja z tablicą liczb całkowitych jako wejściem. Puste miejsca są oznaczone symbolem
0
Test
źródło
C # (.NET Core) , 182 bajty
Stosując tę samą strategię jak Ørjan Johansen.
Używa 0 na liście danych wejściowych do oznaczenia nieznanego var.
Wypróbuj online!
źródło
Perl 5
-p
, 99 bajtówWypróbuj online!
źródło