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: 302
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