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, 14monotonicznie 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 *

Haskell , 41 bajtów

fpobiera listę i zwraca listę, gdzie 0 oznacza ?s.

f=scanr1 min.tail.scanl(#)0
m#0=m+1
_#n=n

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

Mathematica, 84 bajty

Rest[{0,##}&@@#//.{a___,b_,,c___}:>{a,b,b+1,c}//.{a___,b_,c_,d___}/;b>c:>{a,c,c,d}]&

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 Nullo 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żliwymi Nullliterami s na początku listy, zaczynamy od przygotowania 0( {0,##}&@@#), wykonania algorytmu, a następnie usunięcia początkowej 0( Rest).

Tak, wybrałem Nullzamiast Xlub coś w tym rodzaju, aby zapisać dosłownie jeden bajt w kodzie (ten, który w innym przypadku znajdowałby się między przecinkami b_,,c___).

C 160

To nigdy nie wygra, ale:

#define p(x)printf("%d ",x);
i=1,l=0,m=0,n;main(c,v)char**v;{for(;i<c;i++)if(*v[i]==63)m++;else{for(n=atoi(v[i]);m>0;m--)p(l<n?++l:n)p(l=n)}for(;m>0;m--)p(++l)}

Pobiera listę z argumentów wiersza poleceń.

05AB1E , 31 23 13 bajtów

Oszczędność 10 bajtów dzięki Grimy

ε®X:D>U].sR€ß

Wypróbuj online!

Wyjaśnienie

ε      ]       # apply to each number in input
 ®X:           # replace -1 with X (initially 1)
    D>U        # store current_number+1 in X
        .s     # get a list of suffixes
          R    # reverse
           ۧ  # take the minimum of each

Pip , 25 23 21 bajtów

Y{Y+a|y+1}MgW PMNyPOy

Pobiera 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:

? 1 ? 1 2 ? 4 5 5 5 ? ? ? ? 8 10 11 ?  14 14 ?  ?
1 1 2 1 2 3 4 5 5 5 6 7 8 9 8 10 11 12 14 14 15 16

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ść.

                      y is initially "", which is 0 in numeric contexts
                      Stage 1:
 {       }Mg           Map this function to list of cmdline args g:
   +a                  Convert item to number: 0 (falsey) if ?, else nonzero (truthy)
     |                 Logical OR
      y+1              Previous number +1
  Y                    Yank that value into y (it is also returned for the map operation)
Y                      After the map operation, yank the whole result list into y
                      Stage 2:
            W          While loop, with the condition:
               MNy      min(y)
              P         printed (when y is empty, MN returns nil, which produces no output)
                  POy  Inside the loop, pop the leftmost item from y

Python 2 z NumPy, 163 bajty

Zaoszczędzono 8 bajtów dzięki @wythagoras

Zero używane do oznaczania pustych miejsc

import numpy
l=[1]+input()
z=numpy.nonzero(l)[0]
def f(a,b):
 while b-a-1:a+=1;l[a]=l[a-1]+1;l[a]=min(l[a],l[b])
i=1
while len(z)-i:f(z[i-1],z[i]);i+=1
print l[1:]

Bardziej czytelne z komentarzami:

import numpy
l=[1]+input()           # add 1 to the begining of list to handle leading zeros
z=numpy.nonzero(l)[0]   # get indices of all non-zero values
def f(a,b):             # function to fill gap, between indices a and b
    while b-a-1:
        a+=1
        l[a]=l[a-1]+1   # set each element value 1 larger than previous element
        l[a]=min(l[a],l[b])   # caps it by value at index b
i=1
while len(z)-i:       
    f(z[i-1],z[i])      # call function for every gap
    i+=1
print l[1:]             # print result, excluding first element, added at the begining

PHP, 95 77 71 69 68 bajtów

for($p=1;$n=$argv[++$i];)echo$p=$n>0?$n:++$p-in_array($p,$argv)," ";

pobiera dane z argumentów wiersza poleceń, drukuje listę rozdzieloną spacjami. Uruchom z -nr.

awaria

for($p=1;$n=$argv[++$i];)   # loop through arguments
    echo$p=                     # print and copy to $p:
    $n>0                            # if positive number
        ?$n                             # then argument
        :++$p                           # else $p+1 ...
            -in_array($p,$argv)         # ... -1 if $p+1 is in input values
    ," ";                       # print space

$njest prawdą dla każdego łańcucha oprócz pustego łańcucha i "0".
$n>0jest prawdziwe dla liczb dodatnich - i ciągów je zawierających.

Perl 6 , 97 bajtów

{my $p;~S:g/(\d+' ')?<(('?')+%%' ')>(\d*)/{flat(+($0||$p)^..(+$2||*),(+$2 xx*,($p=$2)))[^+@1]} /}

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:

{                       # bare block lambda with implicit parameter ｢$_｣

    my $p;              # holds the previous value of ｢$2｣ in cases where
                        # a number is sandwiched between two replacements

    ~                   # stringify (may not be necessary)
    S                   # replace
    :global
    /
        ( \d+ ' ' )?    # a number followed by a space optionally ($0)

        <(              # start of replacement

          ( '?' )+      # a list of question marks
          %%            # separated by (with optional trailing)
          ' '           # a space

        )>              # end of replacement

        (\d*)           # an optional number ($2)

    /{                  # replace with the result of:

        flat(

          +( $0 || $p ) # previous value or 0
          ^..           # a range that excludes the first value
          ( +$2 || * ), # the next value, or a Whatever star

          (
            +$2 xx *,   # the next value repeated endlessly

            ( $p = $2 ) # store the next value in ｢$p｣
          )

        )[ ^ +@1 ]      # get as many values as there are replacement chars
    } /                 # add a space afterwards
}

JavaScript (ES6), 65 bajtów

a=>a.map(e=>a=e||-~a).reduceRight((r,l)=>[r[0]<l?r[0]:l,...r],[])

Ponieważ chciałem użyć reduceRight. Objaśnienie: mapZastępuje każdą wartość fałsz jedną o więcej niż poprzednią, a następnie reduceRightwraca od końca, upewniając się, że żadna wartość nie przekracza następującej wartości.

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 .

• Zakłada się? = 0
• Wstawia 0 na początku tablicy w przypadku? na starcie.
• Skanuje tablicę, zastępując 0 1 + poprzednim elementem.
• Odwraca tablicę i skanuje ponownie, zastępując elementy większe niż poprzedni element poprzednim elementem.
• Odwraca i wycina pierwszy element (dodane 0 od początku).

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.

TI-Basic (TI-84 Plus CE), 81 bajtów

not(L1(1))+L1(1→L1(1
For(X,2,dim(L1
If not(L1(X
1+L1(X-1→L1(X
End
For(X,dim(L1)-1,1,-1
If L1(X)>L1(X+1
L1(X+1→L1(X
End
L1

Prosty port odpowiedzi Haskell firmy Ørjan Johansen na TI-Basic. Używa 0 jako wartości zerowej. Pobiera dane z L ₁ .

Wyjaśnienie:

not(L1(1))+L1(1→L1(1 # if it starts with 0, change it to a 1
For(X,2,dim(L1     # starting at element 2:
If not(L1(X              # if the element is zero
1+L1(X-1→L1(X            # change the element to one plus the previous element
End
For(X,dim(L1)-1,1,-1 # starting at the second-last element and working backwards
If L1(X)>L1(X+1           # if the element is greater than the next
L1(X+1→L1(X               # set it equal to the next
End
L1                   # implicitly return

Java 8, 199 164 bajtów

a->{for(int l=a.length,n,j,x,i=0;i<l;)if(a[i++]<1){for(n=j=i;j<l;j++)if(a[j]>0){n=j;j=l;}for(j=i-3;++j<n-1;)if(j<l)a[j+1]=j<0?1:a[j]+(l==n||a[n]>a[j]|a[n]<1?1:0);}}

Zmienia tablicę wejściową zamiast zwracać nową, aby zapisać bajty.
Używa 0zamiast ?.

Wypróbuj online.

Wyjaśnienie:

a->{                      // Method with integer-array parameter and no return-type
  for(int l=a.length,     //  Length of the input-array
      n,j,x,              //  Temp integers
      i=0;i<l;)           //  Loop `i` over the input-array, in the range [0, length):
    if(a[i++]<1){         //   If the `i`'th number of the array is 0:
                          //   (And increase `i` to the next cell with `i++`)
      for(n=j=i;          //    Set both `n` and `j` to (the new) `i`
          j<l;j++)        //    Loop `j` in the range [`i`, length):
        if(a[j]>0){       //     If the `j`'th number of the array is not 0:
          n=j;            //      Set `n` to `j`
          j=l;}           //      And set `j` to the length to stop the loop
                          //    (`n` is now set to the index of the first non-0 number 
                          //     after the `i-1`'th number 0)
      for(j=i-3;++j<n-1;) //    Loop `j` in the range (`i`-3, `n-1`):
        if(j<l)           //     If `j` is still within bounds (smaller than the length)
          a[j+1]=         //      Set the `j+1`'th position to:
            j<0?          //       If `j` is a 'position' before the first number
             1            //        Set the first cell of the array to 1
            :             //       Else:
             a[j]+        //        Set it to the `j`'th number, plus:
              (l==n       //        If `n` is out of bounds bounds (length or larger)
               ||a[n]>a[j]//        Or the `n`'th number is larger than the `j`'th number
               |a[n]<1?   //        Or the `n`'th number is a 0
                1         //         Add 1
               :          //        Else:
                0);}}     //         Leave it unchanged by adding 0

Python 2 , 144 124 119 bajtów

l=input()
for n in range(len(l)):a=max(l[:n]+[0]);b=filter(abs,l[n:]);b=len(b)and b[0]or-~a;l[n]=l[n]or a+(b>a)
print l

Wypróbuj online!

Używa 0zamiast?

JavaScript (ES6), 59

Funkcja z tablicą liczb całkowitych jako wejściem. Puste miejsca są oznaczone symbolem0

a=>a.map((v,i)=>v?w=v:(a.slice(i).find(x=>x)<=w?w:++w),w=0)

Test

var F=
a=>a.map((v,i)=>v?w=v:(a.slice(i).find(x=>x)<=w?w:++w),w=0)

;[[2, 4, 10]
,[1, 0, 3]
,[1, 0, 4]
,[]
,[8]
,[0]
,[0, 0, 0]
,[0, 1]
,[0, 2]
,[0, 3]
,[45, 0]
,[1, 0, 0, 0, 1]
,[3, 0, 0, 0, 0, 30]
,[1, 0, 2, 0, 3, 0, 4]
,[1, 0, 3, 0, 5, 0, 7]
,[1, 0, 3, 0, 5, 0, 0, 7]
,[1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 4, 0, 4, 0, 0, 6]
,[98, 0, 0, 0, 102, 0, 104]]
.forEach(a=>{
  console.log(a+'\n'+F(a))
})

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.

l=>{if(l[0]<1)l[0]=1;int j;for(j=0;j<l.Length;j++)l[j]=l[j]==0?l[j-1]+1:l[j];for(j=l.Length-2;j>=0;j--)l[j]=l[j]>l[j+1]?l[j+1]:l[j];foreach(var m in l) System.Console.Write(m+" ");};

Wypróbuj online!

Perl 5 -p , 99 bajtów

s,(\d+ )?\K((\? )+)(?=(\d+)),$d=$1;$l=$4;$2=~s/\?/$d<$l?++$d:$l/rge,ge;($d)=/.*( \d+)/;s/\?/++$d/ge

Wypróbuj online!