-1

Programming-Challenges 网站将其标记为错误答案。我检查了样本输入，它们都是正确的。我对代码添加了优化，我做了它，所以它不会检查已知在另一个数字序列中的数字，因为它是一个子序列并且显然具有更短的循环长度。

此外，我刚刚重新开始编程，所以程序不太简洁，但我希望它是可读的。

这是代码：

#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

I'll try to give you a hint to nudge you into figuring out the problem.

The sample inputs are good as a smoke test, but they're often not good indicators that your program can handle the more extreme test cases too. You should always test with more than the sample inputs. If my calculations are correct, your program will produce the wrong result for the following input:

999000 999250

For reference, the expected output for this is:

999000 999250 321

There, I narrowed your search space down to 251 cycles :) Now get your debugger and finish the job.

Anyway, what follows is the full explanation and solution in spoiler markup. Mouse over the blank space if you want to read it, stay put if you want to figure it yourself.

The problem states that i and j are less than one million and that no operation overflows a 32-bit integer. This means that no intermediate result will be larger than 4294967295. However, an int is a signed type, so, even if it has 32-bits, it only has 31 bits for the absolute value, and thus cannot fit any number larger than 2147483647. Numbers larger than these occur in the cycles of for several Ns in the problem range, one of which is 999167. Using an unsigned 32 bit integer is one solution.

于 2012-06-23T03:58:10.437 回答
1

There is nothing mystery. The largest intermediate number overflows 31-bit of the signed integer. You need to declare record.number and nextNumber as unsigned int.

于 2012-06-23T03:57:45.197 回答