TopCoder

Caido
主唱太拼命了

User's AC Ratio

95.8% (23/24)

Submission's AC Ratio

35.8% (24/67)

Tags

Description

未解決的數學問題對所有自然數,如果它是奇數,則對它乘 3 再加 1,如果它是偶數,則對它除以 2,如此循環,最終都能夠得到 1。

考拉茲猜想(英語:Collatz conjecture),又稱為奇偶歸一猜想3n+1 猜想冰雹猜想角谷猜想哈塞猜想烏拉姆猜想敘拉古猜想,是指對於每一個正整數,如果它是奇數,則對它乘 $3$ 再加 $1$,如果它是偶數,則對它除以 $2$,如此循環,最終都能夠得到 $1$。

以上取自於維基百科

為了驗證考拉茲猜想的正確性,請你寫出一個程式使其可以輸入一個數字,輸出考拉茲猜想的過程直到 $1$ 為止。

Input Format

輸入只有一行,裡面只有一個數字 $x$,表示請你驗證考拉茲猜想的起始數字。

  • $1 \le x \le 1000$,且 $x$ 為整數。

Output Format

輸出過程的格式,請參照以下格式
x -> 下一步的x -> ... -> 1 -> end,所有的數字以及箭頭都有空格,最後以換行結尾。
舉例來說,如果輸入為 $1$,則你該輸出一行 1 -> end
如果輸入為 $18$,則你該輸出以下一行:
18 -> 9 -> 28 -> 14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> end

Sample Input 1

1

Sample Output 1

1 -> end

Sample Input 2

18

Sample Output 2

18 -> 9 -> 28 -> 14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> end

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~9 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2