Definiujemy binarray jako tablicę spełniającą następujące właściwości:
- nie jest pusty
- pierwsza wartość to
1
- ostatnia wartość to
1
- Wszystkie inne wartości są albo
0
albo1
Na przykład tablica [ 1, 1, 0, 1 ]
jest prawidłową tablicą binarną .
Zadanie
Biorąc pod uwagę niepustą tablicę A nieujemnych liczb całkowitych i dodatnią liczbę całkowitą N , Twoim zadaniem jest znalezienie tablicy b B o długości N, która pozwala wygenerować A poprzez zsumowanie nieograniczonej liczby kopii B , przesuniętej o nieograniczoną liczbę pozycje.
Przykład
A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
N = 4
Dla tych danych wejściowych binarna tablica B = [ 1, 1, 0, 1 ]
byłaby prawidłową odpowiedzią, ponieważ możemy wykonać:
[ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
+ [ 1, 1, 0, 1 ]
-----------------------------------------------
= [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
Zasady
- Dane wejściowe można przyjmować w dowolnym rozsądnym formacie.
- Wyjściem może być natywna tablica (np.
[1, 1, 0, 1]
) Lub ciąg binarny z separatorem lub bez (np."1,1,0,1"
Lub"1101"
) - Musisz wydrukować lub zwrócić tylko jeden ważny binarray . Alternatywnie możesz wydrukować lub zwrócić je wszystkie, jeśli istnieje kilka rozwiązań.
- Nie musisz obsługiwać danych wejściowych, które nie prowadzą do żadnego rozwiązania.
- Suma może zawierać ukryte zer, które nie pokrywają się z jakiejkolwiek kopii B . Drugie zero w powyższej sumie jest takim domniemanym zerem.
- Możesz założyć, że maksymalny rozmiar A wynosi 100, a maksymalny rozmiar B to 30.
- To jest golf golfowy, więc wygrywa najkrótsza odpowiedź w bajtach. Standardowe luki są zabronione.
Przypadki testowe
Input : N = 1 / A = [ 1, 2, 3, 4, 5 ]
Output: [ 1 ]
Input : N = 2 / A = [ 1, 2, 100, 99 ]
Output: [ 1, 1 ]
Input : N = 3 / A = [ 1, 1, 1 ]
Output: [ 1, 1, 1 ]
Input : N = 3 / A = [ 1, 1, 3, 2, 2 ]
Output: [ 1, 1, 1 ]
Input : N = 3 / A = [ 1, 0, 2, 1, 1, 1, 0, 0, 1, 0, 1 ]
Output: [ 1, 0, 1 ]
Input : N = 4 / A = [ 1, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1 ]
Input : N = 4 / A = [ 1, 1, 2, 4, 1, 2, 2, 1, 0, 1, 0, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1 ]
Input : N = 4 / A = [ 1, 1, 0, 2, 1, 0, 1 ]
Output: [ 1, 0, 0, 1 ] or [ 1, 1, 0, 1 ]
Input : N = 5 / A = [ 1, 3, 6, 9, 8, 6, 3, 4 ]
Output: [ 1, 1, 1, 0, 1 ]
Input : N = 8 / A = [ 2, 1, 0, 2, 3, 3, 1, 2, 1 ]
Output: [ 1, 0, 0, 1, 1, 1, 0, 1 ]
Input : N = 10 / A = [ 1, 2, 1, 2, 2, 1, 3, 3, 3, 2, 3, 0, 2, 1, 1, 0, 1 ]
Output: [ 1, 1, 0, 1, 0, 1, 1, 1, 0, 1 ]
Input : N = 13 / A = [ 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1 ]
Output: [ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ]
Input : N = 5 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 1, 1, 1 ]
Input : N = 6 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 0, 0, 0, 1 ]
Input : N = 7 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 1, 0, 0, 0, 1, 1 ]
Input : N = 9 / A = [ 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 ]
Output: [ 1, 0, 1, 0, 1, 0, 1, 0, 1 ]
code-golf
array-manipulation
polynomials
Arnauld
źródło
źródło
N
należy w uzasadniony sposób wspierać?N=4, A = [ 1, 1, 2, 4, 1, 2, 2, 2, 1, 2, 2, 1, 2, 0, 1 ]
, masz 30459, która jest podzielna zarówno przez 11 i 13 jeszcze tylko jednego[ 1, 1, 0, 1 ]
i[ 1, 0, 1, 1 ]
jest prawidłowym rozwiązaniem.Odpowiedzi:
PHP,
105 92 9086 bajtówRozwiązanie Jörga naprawione i golfa:
pobiera
N
z pierwszego argumentu wiersza poleceń, potem wartości; uruchom go-r
lub przetestuj online .wypisuje liczbę binarną (format
10001
); drukuje nieprawidłowe rozwiązanie lub przestaje działać, jeśli nie ma prawidłowego rozwiązania.pierwsza wersja (obecnie 97 bajtów), która nie drukuje niczego w przypadku nieprawidłowych danych wejściowych: przetestuj online
awaria
źródło
111
gdy jedynym poprawnym wynikiem jest [1, 0, 1].PHP , 219 bajtów
Wypróbuj online!
-4 Bajty za pomocą
[$g,$z]=$_GET
PHP 7.1 zamiastlist($g,$z)=$_GET
źródło
[1,0,1,0,1,0,1,0,1]
), jak i niepoprawną odpowiedź ([1,0,0,0,1,0,1,1,1]
) dla ostatniego przypadku testowego.while($_GET[0])$s+=2**$i++*array_pop($_GET[0]);
. -5 bajtów:range(1|.5*$m=2**$_GET[1],$m,2)
.[ 1,0,1,1,1,0,2,2,2,2,2,1 ]
.for($g=$_GET[0];$g;)
.Python, 166 bajtów
Wypróbuj online!
Jak to działa
Rozważ A i B jako cyfry podstawowych liczb k u i v . Na przykład (użyjemy k = 1000 dla ilustracji):
A = [1, 2, 1, 3, 2, 1, 2]
B = [1, 0, 0, 1]
u = 1 002 001 003 002 001 002
v = 1 000 000 001
Jak wielu innych Główni odpowiadający zauważył, jeśli B jest prawidłowa odpowiedź, następnie u jest podzielna przez v . W tym przypadku,
u = 1 002 001 002 ⋅ v
Ten iloraz, przetłumaczony z powrotem na tablicę [1, 2, 1, 2], mówi nam dokładnie, ile kopii B potrzebujemy przesuniętych na każdą pozycję.
(Dlaczego? Ponieważ dokładnie tak długo działa mnożenie w bazie k .)
To, czego inni autorzy nie zauważyli, to to powyższy warunek nie jest wystarczający . Na przykład:
A = [1, 2, 1, 3, 2, 1, 2]
B = [1, 1, 1, 1]
u = 1 002 001 003 002 001 002
v = 1 001 001 001
u = 1 000 999 002 ⋅ v
Matematycznie nadal możemy przetłumaczyć ten iloraz z powrotem na tablicę [1, 1, −1, 2], co działa dobrze, jeśli wolno nam używać ujemnych kopii B:
ale oczywiście wyzwanie nie pozwala na kopiowanie negatywne. Potrzebujemy więc dodatkowej kontroli.
W tym celu wybieramy podstawę k = 10 e, gdzie k > 10 ⋅ suma (A), i sprawdzamy, czy żadna z podstawowych liczb k nie przepełnia się do następnej podstawowej liczby k, gdy mnożymy iloraz przez dziesięć. Oznacza to, że każdy e th cyfra dziesięć podstawa, zaczynając od końca, w reprezentacji baza dziesięć czasów ilorazowe dziesięciu, musi być 0. gwarantuje, że iloraz przekłada powrotem do tablicy z elementami nieujemnych.
źródło
PHP, 213 bajtów
W ten sam sposób trochę golfa
Wypróbuj online!
PHP, 344 Bytes pierwszy działa
Po mojej pierwszej odpowiedzi zdecydowałem się na dłuższą próbę, która zwróci wszystkie ważne rozwiązania.
Wersja online
Awaria
źródło
=
pierwszą pętlę dla krótszej wersji W większej wersji trzeba usunąć cztery bajtyPython, 205 bajtów
Zwraca ciąg binarny bez separatora. Jak wskazuje @AndersKaseorg, istnieją dane wejściowe, dla których rozwiązanie @ fəˈnɛtɪk nie działa, ponieważ podział reprezentuje ujemny współczynnik, który jest niedozwolony. Aby obejść ten problem, używam bardzo dużej bazy i sprawdzam, czy w dziale nie ma pożyczki.
źródło
f([1, 1, 1, 0, 0, 0, 1, 1, 1], 3)
niepoprawnie zwraca101
.f([1, 0, 2, 0, 2, 0, 1], 3)
, a oba do przodu i do tyłu zawodząf([1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0], 5)
.i
jest to nieparzyste, zarówno wariant do przodu, jak i do tyłu zawodząf([1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0]*10, 5)
.(x^kn-1)/(x^k-1)
zawsze ma(x^n-1)/(x-1)
czynnik, który oszuka rozwiązanie @ fəˈnɛtɪk w dowolnej bazie.Pyth, 32 bajty
Wypróbuj online
Jak to działa
Strategia jest podobna do mojej odpowiedzi w Pythonie , z tym wyjątkiem, że ponieważ Pyth ma wbudowane funkcje do konwersji bazy, możemy użyć bardziej wydajnej bazy k = 2 ⋅ suma (A) i bezpośrednio sprawdzić, czy każda cyfra ilorazu jest co najwyżej sumą (A ).
źródło
Pari / GP ,
77749680 bajtówZwraca wszystkie rozwiązania.
Najpierw konwertuje tablicę
a
na wielomianb
. Następnie wybiera z dzielnikówb
wielomianówd
tak, że współczynnikid
są wszystkie1
i0
, a wszystkie współczynnikib / d
są nieujemne, id(0) = 1
, ideg(d) = n + 1
. Na koniec konwertuje je z powrotem na tablice.Wypróbuj online!
źródło