b028. F-終究逃不過...命運的制裁... (hard version)

內容

題目都與b015: 終究逃不過...命運的制裁... (easy version)一樣，只有測資加強

某天，柏霖經過一個夜市，看到入口處一個老人正擺著攤，旁邊一個牌子寫著「數字都逃不過的命運！」

柏霖很有興趣，便走過去問了老人是怎樣的輪迴

但既然都在夜市了，想當然耳，老人表示：先給50塊我就告訴你

柏霖按耐不住心中的好奇，只好掏出50塊遞給老人，接著老人偷偷在柏霖的耳邊說道：

「你選擇任何一個正整數，將他不斷地做以下兩種操作：

(1)若他是奇數，把他乘3再加1

(2)若他是偶數，把他除以2

那麼，」老人故意停頓一下：「他最後一定會變成1！！這就是數字都逃不過的命運！！」

柏霖起初完全不信：乘3和除2，一定會愈來愈大的吧！但當他隨便試了幾個數字發現都正確後也不得不相信了

回家的路上，柏霖不斷思考著這個神奇的規則，而且他發現愈大的數所需的操作次數不一定愈多

因此他想知道在一堆數字之中，哪一個數字變成1需要的操作次數最多以及他需要操作幾次呢？請你幫忙解決吧

輸入說明

單筆測資

第一行有一數 $\color{#333333}{N}$ 代表共有 $\color{#333333}{N}$ 個數

第二行有 $\color{#333333}{N}$ 個數字 $\color{#333333}{A_1\sim A_n}$

輸出說明

依照題敘的規則，輸出變成1需要最多操作次數的數是哪個、以及他需要操作幾次

中間以空格隔開

如果有最多操作次數的不只一個數，請輸出最前面的那個

範例輸入

5
1 3 4 6 7

範例輸出

7 16

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (6%): 1.0s , <1M
公開測資點#1 (6%): 1.0s , <1M
公開測資點#2 (6%): 1.0s , <10M
公開測資點#3 (6%): 1.0s , <1M
公開測資點#4 (6%): 1.0s , <10M
公開測資點#5 (15%): 1.0s , <50M
公開測資點#6 (15%): 1.0s , <50M
公開測資點#7 (20%): 1.0s , <50M
公開測資點#8 (20%): 1.0s , <50M

提示：

題敘純屬虛構

範例輸入中，7的操作步驟如下：

$\color{#333333}{7\rightarrow 22\rightarrow 11\rightarrow 34\rightarrow 17\rightarrow 52\rightarrow 26\rightarrow 13\rightarrow 40\rightarrow 20\rightarrow 10\rightarrow 5\rightarrow 16\rightarrow 8\rightarrow 4\rightarrow 2\rightarrow 1}$

共16個步驟

$\color{#333333}{1\le N\le 5\times 10^6}$

$\color{#333333}{1\le A_i\le 10^7}$

保證有解

標籤:

出處:

[管理者：

mattwu0918 (12th 進階教學)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」