#include <bits/stdc++.h>

using namespace std;
long long arr[6608375];
long long f(long long n)
{
    if(n==4){
        return arr[4];
    }
    if(arr[n]==0){
        arr[n] = (n&1?f(3*n+1) : f(n/2));
        return arr[n]+1;
    }
    else{
        return arr[n]+1;
    }
}
int main()
{
    long long a;
    arr[4]=0;
    while(scanf("%lld",&a)!=EOF)
    {
        printf("%lld\n",f(a));
    }
    return 0;
}

因為沒有測資範圍，所以我把表(arr)開到盡量最大。

並使用遞迴(f())來建表(arr)，但

而當我把表作小一點時

#include <bits/stdc++.h>

using namespace std;
long long arr[1000000];
long long f(long long n)
{
    if(n==4){
        return arr[4];
    }
    if(arr[n]==0){
        arr[n] = (n&1?f(3*n+1) : f(n/2));
        return arr[n]+1;
    }
    else{
        return arr[n]+1;
    }
}
int main()
{
    long long a;
    arr[4]=0;
    while(scanf("%lld",&a)!=EOF)
    {
        printf("%lld\n",f(a));
    }
    return 0;
}

出現了另一種錯誤：

希望有人能告訴我出錯的地方以及資料範圍

註：以上程式碼在測試執行都沒問題

就算把long long 改成int也沒辦法

這題記憶體只給16MB

你用的 #include <bits/stdc++.h> 會爆炸

請改成 #include <stdio.h>

I/O用這個標頭檔內的 scanf()、printf()

以上OuOb

可是我照著上面改了之後：

然後我又試了兩種更改方法：

1.首先，我懷疑會RE的原因是因為系統在讀取arr的時候超出上限，所以我把arr陣列擴大(成2000000)，結果

2.看樣子是不太行，而我發現好像沒有必要使用long long int，因為arr陣列也沒有那麼大，所以把long long 改成int、陣列改回原樣(1000000)

3.我再試了另一個：long long ->int  以及 arr 1000000 -> 2000000

我不太理解abort的那個錯誤是甚麼意思，以及為甚麼改成int會造成那樣的錯誤。

也不太理解下兩個測資RE的原因。

還請各位解釋，謝謝。

可是我照著上面改了之後：

為甚麼後兩個RE，第一個沒有？

然後我又試了兩種更改方法：

1.首先，我懷疑會RE的原因是因為系統在讀取arr的時候超出上限，所以我把arr陣列擴大(成2000000)，結果

2.看樣子是不太行，而我發現好像沒有必要使用long long int，因為arr陣列也沒有那麼大，所以把long long 改成int、陣列改回原樣(1000000)

3.我再試了另一個：long long ->int  以及 arr 1000000 -> 2000000

我不太理解abort的那個錯誤是甚麼意思，以及為甚麼改成int會造成那樣的錯誤。

也不太理解下兩個測資RE的原因。

還請各位解釋，謝謝。

一樣是記憶體的問題

你可以稍微試算一下

1個 int 佔32 byte，1byte 佔 4bits

你開的陣列存了1000000個 int：

32 x 4 x 1000000 / 1024 /1024 約等於 122MB

遠超過題目限制，自然會卡RE

>---------------------------------------------------------------------<

題外話

這個演算法在計算途中經過的數字，相對於數字範圍非常稀疏

大約只有 logn / n ～ n^0.65，相當於我就算從1000000000開始

你頂多只能存到30 ～ 30000個數字，效果極度有限

幾乎沒有利用DP陣列記憶化的價值

更別提還要開到10^6這種大小ww

其實你可以逐個數字每次重新計算即可AC

一樣是記憶體的問題

你可以稍微試算一下

1個 int 佔32 byte，1byte 佔 4bits

你開的陣列存了1000000個 int：

32 x 4 x 1000000 / 1024 /1024 約等於 122MB

遠超過題目限制，自然會卡RE

>---------------------------------------------------------------------<

題外話

這個演算法在計算途中經過的數字，相對於數字範圍非常稀疏

大約只有 logn / n ～ n^0.65，相當於我就算從1000000000開始

你頂多只能存到30 ～ 30000個數字，效果極度有限

幾乎沒有利用DP陣列記憶化的價值

更別提還要開到10^6這種大小ww

其實你可以逐個數字每次重新計算即可AC

啊啊啊啊不對不對

1個 int 是 8 bytes -> 32 bits

32 * 1000000 / 1024 / 1024 只佔不到 4MB 

不會超過題目限制

很抱歉差點造成誤解 orz

一樣是記憶體的問題

你可以稍微試算一下

1個 int 佔32 byte，1byte 佔 4bits

你開的陣列存了1000000個 int：

32 x 4 x 1000000 / 1024 /1024 約等於 122MB

遠超過題目限制，自然會卡RE

>---------------------------------------------------------------------<

題外話

這個演算法在計算途中經過的數字，相對於數字範圍非常稀疏

大約只有 logn / n ～ n^0.65，相當於我就算從1000000000開始

你頂多只能存到30 ～ 30000個數字，效果極度有限

幾乎沒有利用DP陣列記憶化的價值

更別提還要開到10^6這種大小ww

其實你可以逐個數字每次重新計算即可AC

啊啊啊啊不對不對

1個 int 是 8 bytes -> 32 bits

32 * 1000000 / 1024 / 1024 只佔不到 4MB 

不會超過題目限制

很抱歉差點造成誤解 orz

...... int 是 4 bytes 不是 8 bytes

4 * 1000000 /1024 /1024 bytes < 4MB

我很抱歉🫠

1.不太懂這兩句：不需要壓到很極限     就有可能出狀況@@             意思是要壓到很極限，還是不要？

2.您說："其實你可以逐個數字每次重新計算即可AC"          意思是說每輸入一筆資料就計算一次嗎？(==就當成是一般3n+1)

假如是的話，請問程式碼是否如下圖？    抱歉國文不好...

#include <stdio.h>
using namespace std;
int main()
{
    int a,cnt;
    while(scanf("%d",&a)!=EOF)
    {
        cnt=0;
        while(a!=4)
        {
            if(a&1){
                a = ((3*a)+1)/2;
                cnt+=2;
            }
            else{
                a/=2;
                cnt++;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

//然後這樣送的話會
是我少考慮了什麼？Q_Q

1. 抱歉表達得不太好，小弟不太懂 OJ 的運作原理，但我認為就算你的程式碼可能只會占用 15.0MB ，

    在這題 16.0MB 的限制下還是有機會炸掉，畢竟網站在測試時可能會有一些額外的開銷產生之類的。

2. 沒錯:) 每筆測資重新算一次就夠 AC 了。

另外你的 code 只有一個小問題，算是弄巧成拙？

用 1 自己手動算算看吧OuOb

1. 抱歉表達得不太好，小弟不太懂 OJ 的運作原理，但我認為就算你的程式碼可能只會占用 15.0MB ，

    在這題 16.0MB 的限制下還是有機會炸掉，畢竟網站在測試時可能會有一些額外的開銷產生之類的。

2. 沒錯:) 每筆測資重新算一次就夠 AC 了。

 

另外你的 code 只有一個小問題，算是弄巧成拙？

用 1 自己手動算算看吧OuOb

*最後一句是代入 1 這個數字當測資算算看的意思

1.假如可以每筆算一次的話，我為何TLE了?

#include <stdio.h>
using namespace std;
int main()
{
    int a,cnt;
    while(scanf("%d",&a)!=EOF)
    {
        cnt=0;
        while(a!=4)
        {
            if(a&1){
                a = ((3*a)+1)/2;
                cnt+=2;
            }
            else{
                a/=2;
                cnt++;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

//然後這樣送的話會
是我少考慮了什麼？Q_Q

2.其實我也有注意到這個問題，只是，題目說：多筆測資，每行一個整數a(a>2)

剛剛盯著你的 code 和我之前丟的 code 比對了好久，

才想到可能是溢位的問題_(:з」∠)_

雖然題目保證 a > 2，但因為有乘以3的操作，

計算過程中還是有可能會炸 int。

如果溢位了數字就會變負數，卡在 while 裡出不來。

（我當時剛好沒註解掉偷懶用的 #define int long long，

結果程式碼邏輯一調整好就過了，完全沒發現可能有溢位的問題）

剛剛盯著你的 code 和我之前丟的 code 比對了好久，

才想到可能是溢位的問題_(:з」∠)_

雖然題目保證 a > 2，但因為有乘以3的操作，

計算過程中還是有可能會炸 int。

如果溢位了數字就會變負數，卡在 while 裡出不來。

（我當時剛好沒註解掉偷懶用的 #define int long long，

結果程式碼邏輯一調整好就過了，完全沒發現可能有溢位的問題）

我WA幾十次都沒發現.......。

謝謝