Definiujemy sekwencję podobną do Collatzas z 4 dodatnimi liczbami całkowitymi:

• n wartość początkowa
• d > 1 dzielnik
• m > 1 mnożnik
• i przyrost

(W oryginalnej sekwencji Collatz d = 2 m = 3i i = 1.)

Biorąc pod uwagę te liczby całkowite szostaną utworzone w następujący sposób:

• s(0) = n
• jeśli k > 0i s(k-1) mod d = 0wtedys(k) = s(k-1) / d
• jeśli k > 0i s(k-1) mod d != 0wtedys(k) = s(k-1) * m + i

Przykładowa sekwencja z d = 2, m = 3, i = 5i n = 80będzie s = 80, 40, 20, 10, 5, 20, 10, 5, 20, ....

Każda sekwencja albo osiągnie wyższe wartości niż jakakolwiek związana granica (tj. Sekwencja jest rozbieżna) lub przejdzie do nieskończonej pętli, jeśli dla niektórych ti u( t!=u) s(t) = s(u)równość będzie prawdziwa.

W naszym problemie, jeśli wartość elementu sekwencji jest większa niż 10^9lub nie ma powtórzenia elementu przed tym 1000elementem, sekwencja jest uważana za rozbieżną.

Zadanie

Powinieneś napisać program lub funkcję, która przyjmuje dodatnie liczby całkowite d moraz ijako dane wejściowe i wyjściowe wszystkie różne typy końcowe sekwencji (nieskończone pętle i rozbieżności), które n = 1, 2, 3, ... 999, 1000mogą wytworzyć wartości początkowe .

Dane wejściowe

• Wejście jest ciągiem znaków lub lista (lub najbliższy odpowiednik w języku polskim) reprezentująca (we wspólnej drodze) trzy liczby całkowite dodatnie d, mi iw tej kolejności. di msą przynajmniej 2. Żadna liczba nie jest większa niż 100.

Dane wyjściowe

Specyfikacja wyjściowa jest nieco nieporadna. Warto najpierw sprawdzić przykłady.

• Powinieneś wypisać dane na standardowe wyjście (lub najbliższą alternatywę) lub zwrócić ciąg znaków.
• Jeśli możliwa jest rozbieżna sekwencja, pierwsza linia powinna być DIVERGENT.
• Unikalną reprezentacją pętli sekwencji jest jej obrót, w którym najmniejsza liczba jest ostatnią oddzieloną spacjami. Np. Jeśli s = 2 1 4 2 1 4 2 1pętla jest 4 2 1.
• W każdym kolejnym wierszu powinieneś wypisać każdą unikalną pętlę dokładnie raz poprzedzoną słowem LOOP. Na przykładLOOP 4 2 1
• Pętle powinny być w porządku rosnącym względem ostatniego elementu.
• Końcowy znak nowej linii jest opcjonalny.

Przykłady:

Pierwsze wiersze są wejściami, a kolejne aż do pustej linii wyjściami.

2 3 1
LOOP 4 2 1

2 2 6
LOOP 8 4 2 1
LOOP 12 6 3

3 7 8
DIVERGENT
LOOP 15 5 43 309 103 729 243 81 27 9 3 1
LOOP 22 162 54 18 6 2
LOOP 36 12 4

3 9 1
DIVERGENT

6 9 9
DIVERGENT
LOOP 18 3 36 6 1
LOOP 27 252 42 7 72 12 2
LOOP 45 414 69 630 105 954 159 1440 240 40 369 3330 555 5004 834 139 1260 210 35 324 54 9 90 15 144 24 4
LOOP 81 738 123 1116 186 31 288 48 8
LOOP 99 900 150 25 234 39 360 60 10
LOOP 126 21 198 33 306 51 468 78 13

10 10 10
LOOP 20 2 30 3 40 4 50 5 60 6 70 7 80 8 90 9 100 10 1

93 91 92
DIVERGENT
LOOP 2185 198927 2139 23
LOOP 4278 46

Odwołanie do implementacji w Pythonie 3 na Ideone.

To jest golf golfowy, więc wygrywa najkrótszy wpis.

Python 3, 269 254 252 246 bajtów

d,m,i=eval(input())
S=set()
for n in range(1,1001):
 T=X=()
 while len(T)**3<1e9>=n:
  T=(n,)+T;n=[n//d,n*m+i][n%d>0]
  if n in T:I=T.index;L=T[:I(n)+1];M=I(min(L));X=L[M:]+L[:M]
 S|={X}
for x in sorted(S):print(x and"LOOP"or"DIVERGENT",*x[::-1])

(Teraz 10 razy wolniejszy, aby zaoszczędzić kilka bajtów. Typowy kod golfowy.)

Wprowadź listę za pomocą STDIN (np [2, 3, 1].). Myślę, że musi być lepszy sposób na ujednolicenie cykli ...

Podejście jest dość proste - przetestuj wszystkie 1000 liczb i weź tylko unikalne wyniki. Istnieją jednak dwie małe sztuczki:

• Pętle są reprezentowane przez niepuste krotki, ale co ważniejsze, rozbieżność jest reprezentowana przez pustą krotkę. Jest to dobre, ponieważ:

  • Nie pęka sorted, a nawet pojawi się przed wszystkimi krotkami pętli
  • Pozwala nam wybrać ciąg za pomocą x and"LOOP"or"DIVERGENT"
  • *()[::-1] nie wpływa print
• Pętle są zbudowane do tyłu, aby przekształcić „sortuj rosnąco według ostatniego elementu” w „sortuj rosnąco według pierwszego elementu”, co eliminuje potrzebę przekazywania lambda sorted.

Poprzednie przesłanie, 252 bajtów

d,m,i=eval(input())
def f(n,T=()):
 x=[n//d,n*m+i][n%d>0];I=T.index
 if x in T:L=T[:I(x)+1];M=I(min(L));return L[M:]+L[:M]
 return()if(T[1000:]or x>1e9)else f(x,(x,)+T)
for x in sorted(set(map(f,range(1,1001)))):print(x and"LOOP"or"DIVERGENT",*x[::-1])

Ten jest o wiele szybszy.