Definiujemy sekwencję podobną do Collatzas
z 4 dodatnimi liczbami całkowitymi:
n
wartość początkowad > 1
dzielnikm > 1
mnożniki
przyrost
(W oryginalnej sekwencji Collatz d = 2
m = 3
i i = 1
.)
Biorąc pod uwagę te liczby całkowite s
zostaną utworzone w następujący sposób:
s(0) = n
- jeśli
k > 0
is(k-1) mod d = 0
wtedys(k) = s(k-1) / d
- jeśli
k > 0
is(k-1) mod d != 0
wtedys(k) = s(k-1) * m + i
Przykładowa sekwencja z d = 2, m = 3, i = 5
i n = 80
bę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 t
i 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^9
lub nie ma powtórzenia elementu przed tym 1000
elementem, sekwencja jest uważana za rozbieżną.
Zadanie
Powinieneś napisać program lub funkcję, która przyjmuje dodatnie liczby całkowite d
m
oraz i
jako 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, 1000
mogą 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
,m
ii
w tej kolejności.d
im
są przynajmniej2
. Ż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 1
pętla jest4 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.