-1

Programming-Challenges Web サイトは、それを不正解としてマークしました。サンプル入力で確認しましたが、すべて正しかったです。コードに最適化を追加しました。別の数の数列にあることがわかっている数をチェックしないようにしました。これは、サブシーケンスであり、サイクルの長さが明らかに短いためです。

また、プログラミングに戻ったばかりなので、プログラムは簡潔すぎませんが、読みやすいと思います。

コードは次のとおりです。

#include <iostream>
#inclue <vector>
struct record
{
   int number;
   int cyclelength;
};

void GetOutput(int BEGIN, int END)
{
    //determines the output order at the end of function
    bool reversed = false;
    if (BEGIN > END)
    {
        reversed = true;
        int temp = BEGIN;
        BEGIN = END;
        END = temp;
    }
    vector<record> records;
    for (int i = BEGIN; i <= END; ++i)
    {
        //record to be added to records
        record r;
        r.number = i;
        r.cyclelength = 1;
        records.push_back(r);
    }

    int maxCycleLength = 1;
    //Determine cycle length of each number, and get the maximum cycle length
    for (int i =0;i != records.size(); ++i)
    {
        //
        record curRecord = records[i];
        //ABCD: If a number is in another number's sequence, it has a lower cycle length and do not need to be calculated,
        //set its cyclelength to 0 to mark that it can be skipped
        if (curRecord.cyclelength != 0)
        {
            //
            while (curRecord.number != 1)
            {
                //next number in the sequence
                int nextNumber;
                //finds the next number
                if (curRecord.number % 2 == 0)
                    nextNumber = curRecord.number / 2;
                else
                {
                    nextNumber = curRecord.number * 3 + 1;
                    //if nextNumber is within bounds of input, mark that number as skippable; see ABCD
                    if (nextNumber <= END)
                    {
                        records[nextNumber - BEGIN].cyclelength = 0;
                    }
                }
                curRecord.number = nextNumber;
                curRecord.cyclelength += 1;
            }
            maxCycleLength = max(curRecord.cyclelength, maxCycleLength);
        }
    }
    if (reversed)
    {
        cout << END << " " << BEGIN << " " << maxCycleLength;
    }
    else
    {
        cout << BEGIN << " " << END << " " << maxCycleLength;
    }
}

int main(){
    //The first and last numbers
    vector< vector<int> > input;
    int begin, end;

    while (cin >> begin >> end)
    {
        //storage for line of input
        vector<int> i;
        i.push_back(begin);
        i.push_back(end);
        input.push_back(i);
    }


    for (int i = 0;i != input.size(); ++i)
    {
        GetOutput(input[i][0], input[i][1]);
        cout << endl;
    }

    return 0;
}
4

2 に答える 2

2

問題を解決するためのヒントを提供しようとします。

サンプル入力はスモーク テストとしては優れていますが、多くの場合、プログラムがより極端なテスト ケースも処理できることを示す指標にはなりません。常にサンプル入力よりも多くをテストする必要があります。私の計算が正しい場合、プログラムは次の入力に対して間違った結果を生成します。

999000 999250

参考までに、これに対する期待される出力は次のとおりです。

999000 999250 321

そこで、検索スペースを 251 サイクルに絞り込みました :) デバッガを入手して、ジョブを終了してください。

とにかく、以下はスポイラー マークアップの完全な説明と解決策です。読みたい場合は空白の上にマウスを置き、自分で理解したい場合はそのままにしておきます。

この問題は、i と j が 100 万未満であり、32 ビット整数をオーバーフローする演算がないことを示しています。これは、中間結果が 4294967295 より大きくならないことを意味します。ただし、anintは符号付きの型であるため、32 ビットであっても絶対値は 31 ビットしかないため、2147483647 より大きい数値は収まりません。これらよりも大きな数値は、問題の範囲内の数 N のサイクルで発生します。そのうちの 1 つは 999167 です。符号なし 32 ビット整数を使用するのが 1 つの解決策です。

于 2012-06-23T03:58:10.437 に答える
1

謎は何もありません。最大の中間数は、符号付き整数の 31 ビットをオーバーフローします。record.numberとnextNumberasを宣言する必要がありますunsigned int。

于 2012-06-23T03:57:45.197 に答える