Weźmy zbiór liczb większych niż 1 i nazwać X . Zdefiniujemy S (i) jako zbiór wszystkich elementów X podzielnych przez i, gdzie i> 1 . Chciałbym wybrać z tych podzbiorów grupę takich zestawów
Ich związek jest zbiorem X
Żaden element X nie znajduje się w dwóch zestawach.
Na przykład możemy przegrupować {3..11}
jako
{3,4,5,6,7,8,9,10,11}
S(3): {3, 6, 9, }
S(4): { 4, 8, }
S(5): { 5, 10, }
S(7): { 7, }
S(11):{ 11}
Niektórych zestawów nie można wyrazić w ten sposób. Na przykład, jeśli weźmiemy {3..12}
, 12
jest wielokrotnością zarówno 3, jak i 4, co zapobiega wzajemnemu wykluczaniu się naszych zestawów.
Niektóre zestawy można na przykład wyrazić na wiele sposobów {4..8}
można je przedstawić jako
{4,5,6,7,8}
S(4): {4, 8}
S(5): { 5, }
S(6): { 6, }
S(7): { 7, }
ale można to również przedstawić jako
{4,5,6,7,8}
S(2): {4, 6, 8}
S(5): { 5, }
S(7): { 7, }
Zadanie
Naszym celem jest napisanie programu, który pobierze zestaw jako dane wejściowe i wyprowadzi najmniejszą liczbę podzbiorów, które pokrywają go w ten sposób. Jeśli nie ma, powinieneś podać jakąś wartość inną niż dodatnia liczba całkowita (na przykład0
).
To jest golf golfowy pytanie w więc odpowiedzi będą oceniane w bajtach, przy czym mniej bajtów jest lepszych.
Testy
{3..11} -> 5
{4..8} -> 3
{22,24,26,30} -> 1
{5} -> 1
źródło
[5..5]
? Czy możemy otrzymać takie rzeczy[8..4]
?12
jest wielokrotnością obu3
i4
zapobiega wzajemnemu wykluczaniu się naszych zbiorów ”: dlaczego? W opisie problemu nie widzę nic innego, co wymagałoby12
przejścia do obu podzbiorów.[22,24,26,30]
są wielokrotnościami2
. Czy jesteś pewien, że nie byłoby lepiej, aby usunąć to i piaskownicy?Odpowiedzi:
Python 2 , 167 bajtów
Wypróbuj online!
-9 bajtów dzięki Zacharýowi
-4 bajty dzięki Mr. Xcoder
-2 bajtów za pomocą list zamiast zestawów
-5 bajtów za pomocą
a in [...]
zamiastany([a == ...])
.-2 bajty dzięki Mr. Xcoder
-8 bajtów poprzez połączenie instrukcji
-5 bajtów dzięki Mr. Xcoder
-7 bajtów dzięki Mr. Xcoder / Zacharý
+7 bajtów do naprawy błędu
-1 bajt dzięki ovs
Uwaga
Jest to bardzo wolne w przypadku większych liczb maksymalnych, ponieważ nie jest w żaden sposób zoptymalizowane; dla urządzenia pana Xcodera nie nastąpiło to w ciągu 2 minut
[22, 24, 26, 30]
.źródło
Clingo , 51 bajtów
Próbny
źródło
x(3..12).
(czy muszę aktualizować?). BTW, czy możesz zasugerować dobre wprowadzenie do clingo?UNSATISFIABLE
takim przypadku powinien wypisać dane. Najczęściej korzystałem z przewodnika Potassco .Mathematica, 105 bajtów
Wypróbuj online,
skopiuj i wklej kod za pomocą Ctrl + V,
wklej dane wejściowe na końcu kodu,
naciśnij Shift + Enter, aby uruchomić
Wejście
przyjmuje listę jako dane
wyjściowe 0, jeśli ich nie ma
źródło
Check
Haskell, 136 bajtów
Wypróbuj online!
Jak to działa
Poświęć dużo czasu
{22,24,26,30}
.źródło
Galaretka,
3835343331282524232019 bajtów-5 bajtów dzięki Leaky Nun
Wypróbuj online!
Myślę, że trzeci przypadek testowy działa, ale jest bardzo wolny.
0
jest generowany, gdy nie ma rozwiązań.Wyjaśnienie (mogło dojść do błędnego wyjaśnienia):
źródło
ṀḊŒPðḍ@þ@⁹Sḟ1ðÐḟḢL
ṀḊ
to naprawdę fajna sztuczka!Julia, 91 bajtów
źródło
[Text to display](link to website)