Wejście: Tablica I od k liczb całkowitych dodatnich. Liczba całkowita nie będzie większa niż 100 i k ≤ 100 .
Dane wyjściowe: Twój kod musi wypisywać wszystkie możliwe tablice O nieujemnych liczb całkowitych o długości k z zastrzeżeniem, że 0 ≤ O i ≤ I i . Aby przejść z jednej tablicy do drugiej, możesz dodać lub odjąć 1 do jednej wartości w tablicy. Twój kod nie może wyprowadzać tej samej tablicy dwukrotnie. Jeśli liczba różnych tablic, które mają być wyprowadzone, jest bardzo duża, twój kod powinien po prostu wyprowadzać wyjście w nieskończoność, dopóki nie zostanie zabity.
Przykłady
Jeśli jestem tablicą k tych, to jest to dokładnie problem iteracji po wszystkich kodach Graya o szerokości bitu k , z tym wyjątkiem, że pierwszy i ostatni element nie muszą być osiągalne w jednym kroku.
Jeśli tak,
I = [2,1]
to możliwe jest uporządkowanie tablic wyjściowych(0,0),(0,1),(1,1),(1,0),(2,0),(2,1)
- Jeśli tak,
I = [2,1,3]
to możliwe jest uporządkowanie tablic wyjściowych(0,0,0),(0,0,1),(0,0,2),(0,0,3),(0,1,3),(0,1,2),(0,1,1),(0,1,0),(1,1,0),(1,1,1),(1,1,2),(1,1,3),(2,1,3),(2,1,2),(2,1,1),(2,1,0),...
.
To jest wyzwanie dla golfa, wygrywa zgłoszenie z kodem źródłowym o najkrótszej długości. Nie pozwól, aby krótkie odpowiedzi w językach golfowych zniechęciły cię do zamieszczania odpowiedzi w innych językach. Spróbuj znaleźć najkrótszą odpowiedź w dowolnym języku.
Jest to również wyzwanie o ograniczonej złożoności. Każda nowa tablica powinna być wyprowadzana z upływem czasu O (k) od czasu poprzedniej tablicy wyjściowej (lub początku programu dla pierwszej tablicy wyjściowej). Oznacza to, że czas działania dla nowej tablicy wyjściowej (każda z nich ma długość k ) nie powinien być większy niż O (k) . To znaczy, że powinno to zająć czas proporcjonalny do k, a nie, na przykład k 2 lub 2 k . Zauważ, że nie jest to średni czas na wyjście, ale najgorszy przypadek dla każdej wysłanej tablicy.
Możesz założyć, że cała arytmetyka na 64-bitowych liczbach całkowitych może być wykonywana w stałym czasie, podobnie jak ich odczyt i wysyłanie, a także przypisywanie, wyszukiwanie i zmiana wartości w tablicach.
Jedną z konsekwencji ograniczonej złożoności jest to, że rozwiązania, które pojawiają się tylko przy wyjściu z programu, są niedopuszczalne.
I_i+1
? Czy można osiągnąć 0 odI_i
?)n
ik
są ograniczone? zakładając, że idą w nieskończoność z szerokością bitów jak jechaćOdpowiedzi:
Python 3 , 116 bajtów
Wypróbuj online!
Dzięki Mnemonic za -1 bajt.
Funkcja generatora. (dzięki Dennis za przypomnienie, zapomniałem, że funkcja istnieje) Jeśli wyjście powinno zostać wydrukowane na standardowym wyjściu, użyj
print(t,flush=1)
9 dodatkowych bajtów lub, jeśli wywoływany jest Python-u
,print(t)
wystarcza na +1 bajtów.Zatrzymuje się z błędem (
IndexError
). Jeśli chcesz wywołać tę funkcję, a następnie kontynuować program, musisz ją złapać.źródło
k
etapów, ponieważ na każdym krokui
zwiększa się1
i pok
schodachi==k
id[i]
powoduje błąd.not 0<=
gonot-1<
.yield t
zamiastprint(t,flush=1)
?Stax , 22 bajty
Uruchom i debuguj
Oto duży, aby pokazać asymptotyczne zachowanie Naciśnij bieg.
Rozpakowane, niepolowane i skomentowane, wygląda to tak.
Uruchom ten
źródło
O(k)
bity, więck
czasy podziału mogą zająć trochęO(k²)
czasu ...JavaScript (Node.js) , 114 bajtów
Wypróbuj online! Nie golfowany:
źródło
Kotlin ,
181178 bajtówDzięki: Anush wskazał, że źle zrozumiałem wyzwanie, oszczędzając 2 bajty. ovs wskazał 1 bajt oszczędności.
Wypróbuj online!
źródło
while(true)
może byćwhile(1<2)