uva: 3n + 1 == runtime, runtime....RUNTIME!

[Dammned Programmer]

hello there. i've trying to solve a problem in uva but for some reason its always runtime, runtime, and runtime. i've check using the inputs given and they were right but when i submitted it: runtime! it's already my six-ed try anduva doesn't really give a reason why its a runtime so pls help me! i don't know what to do! >.<

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
double i, j;
int x, ioriginal, imax, temp;
vector<int>v;

while(cin>>i>>j && (i < 1000000 && j < 1000000)){

    i = int(i);

    j = int(j);

    if(i > j)
    {
        temp = j;
        j = i;
        i = temp;
    }

    ioriginal = i;

    while(i != j)
    {

    int ctr = 1;

    x = i;

        while(x != 1)
        {
            if(x%2 == 0)
                x = x/2;
            else
                x = 3*x + 1;
        ctr++;
        }

    v.push_back(ctr);

    i++;

    }

imax = *max_element(v.begin(), v.end());

cout<<ioriginal<<" "<<j<<" "<<imax<<endl;

v.clear();

}

return 0;

}

[Chervil]

Could clarify the question please.

What input data is used and what output do you get? Are there any error messages, if so please give the actual error message.

Edit: The key may be in attention to detail.
The two integers must be output in the same order as they were input. Also what happens if the two input integers are the same?

As for your code, the use of <vector> and <algorithm> here is overkill in my opinion, its more straightforward to simply keep track of the highest value of ctr instead of pushing it into the vector. I don't think type double is required as all values are integers here.

[tipaye]

Don't know if this will help but here are some points:

If i == j on your first run, you have an empty vector and v.end() is returned. Since this points past the end of your vector, you'll likely to get a segmentation fault.

Calling vector::clear() doesn't guarantee reallocation or change in capacity, so if it's not your first run, and i == j, you may end up with the previous result rather than a crash. This is even worse.

Finally, consider that if your values are negative, then your inner while loop will never terminate!

[Dammned Programmer]

o.k i've changed the code into a simpler form and now it's a "wrong answer". I don't think there's anything wrong with it (since i checked the inputs and outputs using a different code that got accepted).

#include <iostream>
using namespace std;

int oddEven(int x)
{
int ctr = 1;

    while(x != 1)
    {
        if(x%2 == 0)
            x = x/2;
        else
            x = 3*x + 1;
    ctr++;
    }

return ctr;
}

int main()
{
int i, j, x, iOriginal, jOriginal, ctr, temp = 0;

while(cin>>i>>j)
{
int temp = 0;

    iOriginal = i;
    jOriginal = j;

    if(i > j)
        swap(i, j);


    if(i == j)
        temp = oddEven(i);

    while(i != j)
    {
        x = i;
        ctr = oddEven(x);
        if(ctr > temp)
            temp = ctr;
        i++;
    }

    i = iOriginal;
    j = jOriginal;

cout<<i<<" "<<j<<" "<<temp<<endl;
}

}

[ne555]

learn to indent.

determine the maximum cycle length over all integers between and including i and j.

You fail for input: 1 2

[Dammned Programmer]

i've changed the "while(i != j)" part to "while(i != j + 1)". does that help?

#include <iostream>
using namespace std;

int oddEven(int x)
{
int ctr = 1;

    while(x != 1)
    {
        if(x%2 == 0)
            x = x/2;
        else
            x = 3*x + 1;
    ctr++;
    }

return ctr;
}

int main()
{
int i, j, x, iOriginal, jOriginal, ctr, temp = 0;

while(cin>>i>>j)
{
    int temp = 0;

        iOriginal = i;
        jOriginal = j;

        if(i > j)
            swap(i, j);


        if(i == j)
            temp = oddEven(i);

        while(i != j + 1) /// from "i != j" to "i != j + 1"
        {
            x = i;
            ctr = oddEven(x);
            if(ctr > temp)
                temp = ctr;
            i++;
        }

        i = iOriginal;
        j = jOriginal;

    cout<<i<<" "<<j<<" "<<temp<<endl;
}

}

finally got accepted for the 11th time! thnks for the help guys! :D

[Chervil]

Looks like this is done now. I would have suggested while (i <= j) as slightly simpler than while(i != j + 1).