UVA Online Judge 3n+1 : Right answer is Wrong answer

Posted by Samuraisoulification on Stack Overflow See other posts from Stack Overflow or by Samuraisoulification
Published on 2012-09-06T02:37:33Z Indexed on 2012/09/06 3:38 UTC
Read the original article Hit count: 276

Filed under:
|
|
|

Ive been toying with this problem for more than a week now, I have optimized it a lot, I seem to be getting the right answer, since it's the same as when I compare it to other's answers that got accepted, but I keep getting wrong answer. Im not sure what's going on! Anyone have any advice? I think it's a problem with the input or the output, cause Im not exactly sure how this judge thing works. So if anyone could pinpoint the problem, and also give me any advice on my code, Id be very appreciative!!!

#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <vector>

using namespace std;

class Node{ // node for each number that has teh cycles and number
private: 
    int number;
    int cycles;
    bool cycleset; // so it knows whether to re-set the cycle

public:
    Node(int num){
        number = num;
        cycles = 0;
        cycleset = false;
    }

    int getnumber(){
        return number;
    }
    int getcycles(){
        return cycles;
    }
    void setnumber(int num){
        number = num;
    }
    void setcycles(int num){
        cycles = num;
        cycleset = true;
    }

    bool cycled(){
        return cycleset;
    }
};

class Cycler{
private:
    vector<Node> cycleArray;
    int biggest;

    int cycleReal(unsigned int number){ // actually cycles through the number
        int cycles = 1;
        if (number != 1) {
            if (number < 1000000) { // makes sure it's in vector bounds
                if (!cycleArray[number].cycled()) { // sees if it's been cycled
                    if (number % 2 == 0) {
                        cycles += this->cycleReal((number / 2));
                    } else {
                        cycles += this->cycleReal((3 * number) + 1);
                    }
                } else { // if cycled get the number of cycles and don't re-calculate, ends recursion
                    cycles = cycleArray[number].getcycles();
                }
            } else { // continues recursing if it's too big for the vector
                if (number % 2 == 0) {
                    cycles += this->cycleReal((number / 2));
                } else {
                    cycles += this->cycleReal((3 * number) + 1);
                }
            }
        }
        if(number < 1000000){ // sets cycles table for the number in the vector
            if (!cycleArray[number].cycled()) {
                cycleArray[number].setcycles(cycles);
            }
        }
        return cycles;
    }

public:
    Cycler(){
        biggest = 0;
        for(int i = 0; i < 1000000; i++){ // initialize the vector, set the numbers
            Node temp(i);
            cycleArray.push_back(temp);
        }
    }

    int cycle(int start, int end){ // cycles thorugh the inputted numbers. 
        int size = 0;
        for(int i = start; i < end ; i++){
            size = this->cycleReal(i);
            if(size > biggest){
                biggest = size;
            }
        }
        int temp = biggest;
        biggest = 0;
        return temp;
    }

    int getBiggest(){
        return biggest;
    }
};

int main() {    
    Cycler testCycler;
    int i, j;
    while(cin>>i>>j){ //read in untill \n
    int biggest = 0;
    if(i > j){
        biggest = testCycler.cycle(j, i);
    }else{
        biggest = testCycler.cycle(i, j);
    } 
    cout << i << " " << j << " " << biggest << endl;
    }
    return 0;
}

© Stack Overflow or respective owner

Related posts about c++

Related posts about algorithm