3n+1 UVa problem

[Melchizedek]

I've tried submitting this multiple times thinking my output was the problem. Also did input from a file instead of testing with cin. Still keep getting incorrect answer. Any suggestions?

Problem: https://uva.onlinejudge.org/external/1/100.pdf

Code:

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

int main()
{
    int value1, value2, range, n, maxCycles, temp;
    bool reverse = false;
    
    while (cin >> value1 >> value2)
    {
     
        if (value2 < value1)
        {
            temp = value2;
            value2 = value1;
            value1 = temp;
            reverse = true;
        }

        
        range = value2 - value1 + 1;
        
        
        vector<int> checkValues(range);
        vector<int> cycles(range, 0);
        
        for (int i=0; i < range; i++)
            checkValues[i] = value1 + i;
        
        for (int i=0; i<range; i++)
        {
            n = checkValues[i];
            
            while (n != 1)
            {
                if (n % 2 == 0)
                    n = n/2;
                else
                    n = 3*n+1;
            
                cycles[i] = cycles[i]+1;
            }
            
            cycles[i] = cycles[i]+1;
        }
        
        maxCycles = *max_element(cycles.begin(), cycles.end());
        
    
      if (reverse == false)
          cout << value1 << " " << value2 << " " << maxCycles;
      else
          cout << value2 << " " << value1 << " " << maxCycles;

        cout << endl;
    }
    
    return 0;
}

[Ganado]

What is incorrect? Please be specific. Which input causes unexpected results? What is the expected result that you did not get?
Your program seems to work for all the test cases that the PDF gives.

Also, please use CODE TAGS [code] ... [/code] around your code. You can still edit your first post to add this.

[Melchizedek]

That's the issue it's UVa submission so they won't tell you what's wrong other than compile errors :(

[jlb]

It looks like your loop condition is incorrect.

How does your loop end?

How does the instructions say the loop should end? In fact you don't really seem to be following most of the instructions correctly. Perhaps you need to review the instructions and actually follow them.

[Ganado]

If the input and output is through file redirection, doing
UVa_program < input.txt > output.txt
is how it's probably done by the testers.

OP, trying looping on while (cin >> value1 >> value2) { ... }
Not sure if that will help, but it's worth a true.
This ensures that the 2nd input has to succeed as well. No "100 foo" as input.

[Melchizedek]

I tried putting both in values in the while loop - works but still "wrong answer"

Here's another code (jolly jumpers) I submitted for a different problem that did work - the loop should take in data as long as there is data just like the following:

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
    
    vector<int> list;
    int list_size;
    
    while (cin >> list_size)
    {
        vector<int> list(list_size);
        
        for (int i=0; i<list_size; i++)
            cin >> list[i];
        
        vector<int> absolutes(list_size-1);
        
        for (int j=0; j<list_size-1; j++)
            absolutes[j] = abs (list[j]-list[j+1]);
        
        sort(absolutes.begin(), absolutes.end());
        
        vector<int> checkList(list_size-1);
        
        for (int k=0; k<list_size-1; k++)
            checkList[k] = k+1;
        
        
        if (checkList == absolutes)
            cout << "Jolly";
        else
            cout << "Not jolly";
        
    }
    
    
    return 0;
}

[JLBorges]

Memoize: https://en.wikipedia.org/wiki/Memoization

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <ctime>

unsigned int cycle_length( unsigned int n ) // n > 0
{
    // look up table of cycle lengths
    static std::unordered_map< unsigned int, unsigned int > cycle_length_map ;

    if( n == 1 ) return 1 ;

    // if found it in look up table, return the value
    if( cycle_length_map[n] != 0 ) return cycle_length_map[n] ;

    // otherwise, compute the cycle length, and return it after memoizing it
    else return cycle_length_map[n] = 1 + cycle_length( (n%2) ? (3*n + 1) : (n/2) ) ;
}

unsigned int max_cycle_length( unsigned int low, unsigned int high )
{
    unsigned int max_length = 0 ;

    for( auto n = low ; n <= high ; ++n )
        max_length = std::max( max_length, cycle_length(n) ) ;

    return max_length ;
}

int main()
{
    const auto start = std::clock() ;

    struct input { unsigned int i ;  unsigned int j ; } ;
    for( input inp : { input{ 1, 10 }, input{ 100, 200 }, input{ 201, 210 }, input{ 900, 1000 }, input { 1, 9'999 } } )
        std::cout << inp.i << ' ' << inp.j << ' ' << max_cycle_length( inp.i, inp.j ) << '\n' ;

    const auto end = std::clock() ;
    std::cout << '\n' << (end-start) * 1000.0 / CLOCKS_PER_SEC << " milliseconds\n" ;
} 

1 10 20
100 200 125
201 210 89
900 1000 174
1 9999 262

6 milliseconds

http://rextester.com/WETO49900