Rozważ listę l
składającą się z liczb. Zdefiniować operację bloku o indeksie i
na liście l
się czynnością przesuwania 3 kolejne elementy, począwszy od i
wl
do końca.
Przykład:
l, i (1-indexing) -> l (after applying block operation at index i)
[1,2,3,4,5], 1 -> [4,5,1,2,3]
[1,2,3,4,5,6,7], 3 -> [1,2,6,7,3,4,5]
Biorąc pod uwagę listę składającą się tylko z 0 i 1, Twoim zadaniem jest podzielić ją tak, aby zera były z przodu, a zera z tyłu, używając tylko operacji blokowania. Dane wyjściowe powinny być indeksami w kolejności, w jakiej są stosowane na liście.
Ponieważ jest to niemożliwe dla listy [1,0,1,0]
, długość listy wynosi co najmniej 5.
Przypadki testowe (indeksowanie 1)
(istnieją inne ważne dane wyjściowe)
[1,1,1,0,0] -> [1]
[0,1,0,1,0] -> [1,2,1,1]
[0,0,0,1,1,1,0,0,0] -> [4]
Użyj tego skryptu, aby wygenerować więcej przypadków testowych. (tylko wejście. Ten rplc ' ';','
element do R e en C e przestrzenie przecinkami na wyjściu)
Kryteria wygranej
Wyzwanie kodu to główne kryterium wygranej, a najszybszy kod to remis. W szczególności:
- Rozwiązanie o najkrótszej długości wyjściowej (najmniejszej liczbie operacji bloku) z przypadkiem testowym (
n_elem
= 500,random_seed
= {tajna wartość}) wygrywa. Powinieneś być w stanie uruchomić rozwiązanie do końca z przypadkiem testowym (n_elem
= 500,random_seed
= 123456). - W przypadku powiązań rozwiązanie, które może obsłużyć największą wartość potęgi-2
n_elem
zrandom_seed
wygrywa = = tajna wartość} w ciągu 10 sekund (dla mnie). - W przypadku powiązań wygrywa rozwiązanie, które zajmuje mniej czasu w tym przypadku testowym.
źródło
Odpowiedzi:
Krok 3 w Pythonie (0,397 n + 3,58)
Regresja wielomianowa 1000-punktowa wg
numpy.polyfit
.Wypróbuj online!
źródło
Python 3, ~ 179 kroków dla n = 500 (średnio)
Heurystyczne chciwe podejście. Trochę wolno, ale nadal działa. Wykorzystuje optymalny solver dla małych rozmiarów.
źródło