Zestaw różnic cyklicznych to zbiór liczb całkowitych dodatnich o unikalnej właściwości:
- Niech
n
będzie największą liczbą całkowitą w zestawie. - Niech
r
będzie liczbą całkowitą (niekoniecznie w zestawie) większą niż 0, ale mniejszą lub równąn/2
. - Pozwolić
k
być liczba rozwiązań do(b - a) % n = r
gdziea
ib
są jakieś członkowie zestawu. Każde rozwiązanie jest uporządkowaną parą(a,b)
. (Należy również pamiętać, że ta wersja modulo sprawia, że liczby ujemne są dodatnie poprzez dodanien
do niej, w przeciwieństwie do implementacji w wielu językach.) - Wreszcie, jeśli i tylko jeśli jest to zestaw różnic cyklicznych, wartość
k
nie zależy od twojego wyborur
. Oznacza to, że wszystkie wartościr
dają taką samą liczbę rozwiązań powyższej zgodności.
Można to zilustrować następującym przykładem:
Cyclic difference set: {4,5,6,8,9,11}
0 < r <= 11/2, so r = 1,2,3,4,5
r=1: (4,5) (5,6) (8,9)
r=2: (4,6) (6,8) (9,11)
r=3: (5,8) (6,9) (8,11)
r=4: (4,8) (5,9) (11,4) since (4-11)%11=(-7)%11=4
r=5: (4,9) (6,11) (11,5)
Każda wartość r
ma taką samą liczbę rozwiązań, w tym przypadku 3, więc jest to zestaw różnic cyklicznych.
Wejście
Dane wejściowe będą listą liczb całkowitych dodatnich. Ponieważ jest to właściwość set, załóż, że dane wejściowe nie są sortowane. Możesz założyć, że n
jest co najmniej 2
, chociaż k
może wynosić zero.
Wynik
Twój program / funkcja powinna wypisywać prawdziwą wartość, jeśli zbiór jest zbiorem różnic cyklicznych lub w przeciwnym razie wartością falsey.
Przypadki testowe
Prawidłowe zestawy różnic cyklicznych:
10,12,17,18,21
7,5,4
57,1,5,7,17,35,38,49
1,24,35,38,40,53,86,108,114,118,135,144,185,210,254,266,273
16,3,19,4,8,10,15,5,6
8,23,11,12,15,2,3,5,7,17,1
( źródło danych , chociaż ich konwencja jest inna)
Nieprawidłowe zestawy różnic cyklicznych:
1,2,3,4,20
57,3,5,7,17,35,38,49
3,4,5,9
14,10,8
code-golf
number
decision-problem
number-theory
PhiNotPi
źródło
źródło
a
ib
będzie ten sam element (niekonieczniea ≠ b
)?b
ia
mają ten sam numer, to(b-a)%n = 0
0, ale 0 nie jest jedną z wartości, dla której szukasz rozwiązań. Więc nie ma wyraźnego zakazu, aby były one tym samym numerem, ale nigdy nie będą.7 7 7
były niepoprawne. Zestaw nie powtarza wartości7 7 7
został zgłoszony przez innego użytkownika, ale usunąłem go, ponieważ nie jest to zestaw.r
przez0 < r <= max(input)/2
, lecz0 < r < max(input)
dlatego, że możemy uzyskaćr > max(input)/2
przypadków po prostu przerzucanie odejmowanie wr <= max(input)/2
przypadkach.Odpowiedzi:
Galaretka ,
147 bajtówWypróbuj online!
Jak to działa
źródło
Łuska , 13 bajtów
Wypróbuj online!
Trzy indeksy górne 1 wydają się marnotrawstwem ...
Wyjaśnienie
źródło
Wolfram Language (Mathematica) ,
5352 bajtyWypróbuj online!
Uwaga: nie musimy dzielić elementu max przez dwa ze względu na symetrię (możemy sprawdzić liczbę wszystkich modułów
1
domax(input) - 1
).Wyjaśnienie
Weź wszystkie permutacje długości 2 danych wejściowych.
Znajdź różnice między nimi
Zmodyfikuj wynik o maksymalny element wejściowy.
Znajdź częstotliwości każdego elementu.
Zwróć, czy wszystkie liczby są takie same.
źródło
Python 3 ,
868481 bajtów-3 bajty thaks do JungHwan Min
Wypróbuj online!
źródło
JavaScript (ES6), 87 bajtów
Zwraca 0 lub 1 .
Przypadki testowe
Pokaż fragment kodu
źródło
Perl,
686766 bajtówObejmuje
+2
dlaap
źródło
Python 3 , 74 bajty
Wypróbuj online!
źródło
Ruby , 81 bajtów
Wypróbuj online!
Nie golfowany:
źródło
Haskell, 84 bajty
l jest funkcją, która sprawdza. Po prostu oblicza wszystkie różnice i się liczy.
źródło
let
w osłonie wzorów zamiastwhere
oszczędzać bajt: Wypróbuj online!