## 100 - The 3n + 1 problem

Moderator: Board moderators

mntamim
New poster
Posts: 8
Joined: Wed Nov 06, 2013 12:08 am

### PROBLEM 100

i cant understand why i get wrong answer

Code: Select all

``````#include <stdio.h>
#include <map>

#define MIN(x,y) (x<y)?x:y
#define MAX(x,y) (x>y)?x:y

std::map<unsigned long long int,unsigned long long int> number;

unsigned long long int compute(unsigned long long int n)
{
if(!number[n])
{
if(n&1)
number[n] = compute(3*n+1) + 1;
else
number[n] = compute(n>>1) + 1;
}
return number[n];
}

int main()
{
number = 1;

int i,j,temp_i,temp_j;
unsigned long long int max;
unsigned long long int temp;

int line = 0;

while(scanf("%d %d",&temp_i,&temp_j)!=EOF)
{
if(line&1)
printf("\n");

max = 0;

i=MIN(temp_i,temp_j);
j=MAX(temp_i,temp_j);

for(; i<=j ; i++)
{
temp = compute(i);
if(temp>max)
max = temp;
}

printf("%lu %lu %lu",temp_i,temp_j,max);
line=1;
}

return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: PROBLEM 100

Try using printf("%llu") for a long long unsigned.
Check input and AC output for thousands of problems on uDebug!

mntamim
New poster
Posts: 8
Joined: Wed Nov 06, 2013 12:08 am

### Re: PROBLEM 100

even if i do

Code: Select all

``````cout << temp_i << ' ' << temp_j << ' ' << max;
``````
any ideas ?

mntamim
New poster
Posts: 8
Joined: Wed Nov 06, 2013 12:08 am

### Re: PROBLEM 100

wow how stupid,

what it looked like in the program output that the last line doesnt have a newline,
turns out that it has a newline and i wasnt printing it ecarrera
New poster
Posts: 3
Joined: Wed Nov 20, 2013 2:47 am

### Re: If you get WA in problem 100, read me before post!

Hi everybody, I'm trying with this fu/%=ing code...

Can anyone tell me what is going on?
Why WA?

C++ version 4.9.9.2

Code: Select all

``````#include <stdio.h>

using namespace std;

int main()
{
unsigned long n;
unsigned int a,b,i,atemp;
unsigned short c=0,d;
while (scanf ("%d %d", &a, &b) != EOF){

if (a>b)
{
atemp=a;
a=b;
b=atemp;
}
i=a;
while (i<=b){
d=0;
n = i;
while(n!=1){
if(n%2==0) n/=2;
else n=3*n+1;
d++;
}
d++;
if (d>c) c=d;
i++;
}
printf ("%d %d %d\n", a, b, c);
c=0;
}
return 0;
}``````
I compile and it works great, when a<b, a>b, a or b ~< 10.000.000

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: If you get WA in problem 100, read me before post!

Input:

Code: Select all

``````1 10
10 1
``````
Output should be:

Code: Select all

``````1 10 20
10 1 20
``````
Check input and AC output for thousands of problems on uDebug!

ecarrera
New poster
Posts: 3
Joined: Wed Nov 20, 2013 2:47 am

### Re: If you get WA in problem 100, read me before post!

Yes the output is ok,

Code: Select all

``````1 10 20
10 1 20
1 999999 525
999999 1 525
``````
Is my first submit, but always WA brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: If you get WA in problem 100, read me before post!

The code that you posted is producing this output:

Code: Select all

``````1 10 20
1 10 20``````
Post your updated code if you need more help.
Check input and AC output for thousands of problems on uDebug!

ecarrera
New poster
Posts: 3
Joined: Wed Nov 20, 2013 2:47 am

### Re: If you get WA in problem 100, read me before post!

I got it, thanks @brianfry713, that was! lol ... I was ordering the output. Now my output is in the same way of the input but adding the maxcicle Run Time: 0.545

Code: Select all

``````#include <stdio.h>

using namespace std;

int main()
{
unsigned long n;
unsigned int a,b,i,atemp,btemp;
unsigned short c=0,d;
while (scanf ("%d %d", &a, &b) != EOF){

atemp=a;
btemp=b;

if (a>b)
{
atemp=b;

btemp=a;
}
i=atemp;
while (i<=btemp){
d=0;
n = i;
while(n!=1){
if(n%2==0) n/=2;
else n=3*n+1;
d++;
}
d++;
if (d>c) c=d;
i++;
}
printf ("%d %d %d\n", a, b, c);
c=0;
}
return 0;
}
``````
Last edited by ecarrera on Fri Nov 22, 2013 1:28 am, edited 1 time in total.

New poster
Posts: 1
Joined: Tue Dec 10, 2013 6:54 am

### 100 - The 3n + 1 problem Runtime Error

Thanks in advanced for any assistance. When i submit my code i get a run time error, specifically "Your submission with number 12818442 for the problem 100 - The 3n + 1 problem has failed with verdict Runtime error.This means that the execution of your program didn't finish properly. Remember to always terminate your code with the exit code 0." Could anyone look look at my code and tell me where the problem lies? It works fine in the testing i did. I am using the latest version of netbeans to code. Thanks for any help and/or advice.

Code: Select all

``````/*
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/

package onlinejudge100;

import java.util.Scanner;

/**
*
* @author Dave
*/
public class Main {

//method to conduct the 3n + 1 problem
float cycleCount(float i)
{
float count = 1; //resets count to 1 every time the method is called to include the number 1 :NOTE if count is not set to one, the previous value will be stored and it will continue to add up.
float n = i;     //sets N to the arguement sent to through the method call.
while(n != 1)
if (n % 2 == 1) //inspects the number to see if it is odd
{
n = 3 * n + 1;   //formula
count = count+1; //counts the occurance
}
else
{
n = n / 2;       //formula
count = count+1; //counts the occurance
}
return count; //returns count to the object call
}

public static void main(String[] args)
{
Main cycle = new Main();  //creates new object of class OnlineJudge100
Scanner in = new Scanner(System.in);         //creats object of class Scanner to take in inputs
float count = 0;
float i=0, j=0, answer = 0;                    //variable declarations
System.out.print("Enter Integer I and J: "); //output message
i = in.nextInt();                            //sets value to user input
if (i < 0 || i > 999999)                     //restricts number between 0 and 1,000,000
throw new IllegalArgumentException("Specified number is out of range"); //throws error if restriction is not met
j = in.nextInt();                           //sets value to user input
if (j < 0 || j > 999999)                    //restricts number between 0 and 1,000,000
throw new IllegalArgumentException("Specified number is out of range"); //throws error if restriction is not met

for (float test = i; test < j + 1; test++)   //for loot to test all the numbers between the 2 input integers.
{
float result = cycle.cycleCount(test);   //calls the method in the object and sets the result to variable result
count = count + 1;
//System.out.println("result = " + count);
if (result > answer)                    //compares result to stored answer, if result is bigger, save that into the answer
{
}
}
System.out.println(i + " " + j + " " + answer);    //output information
}

}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 100 - The 3n + 1 problem Runtime Error

Check input and AC output for thousands of problems on uDebug!

enil14someone
New poster
Posts: 1
Joined: Thu Jan 02, 2014 4:09 pm

### 3n+ 1 : y u always go WA/RUNTIME!?

yea ive been trying this problem for the tenth time already and its always it wrong answer or runtime. ive check it and it seems fine but still...WA. can anyone tell me whats wrong?

Code: Select all

``````#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;
}

}
``````

greentea99
New poster
Posts: 1
Joined: Sun Jan 05, 2014 8:55 am

### Re: If you get WA in problem 100, read me before post!

Hey guys, haven't coded in a long time and trying to get started on uva to freshen up. Forgotten almost everything, so pardon any noob mistakes. Wondering why my code is giving WA?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define buffSize 100

int numIterations(int n){
int count = 1;
while(n != 1){
if((n%2) != 0){
n = 3*n + 1;
} else {
n = n/2;
}
count++;
}
return count;
}

int main(){
int value1, value2;
int temp1, temp2, tempSwap;
int maxIter, iterValue;
while(scanf("%d %d", &value1, &value2) != EOF){
temp1 = value1;
temp2 = value2;
/* swap values if values decrease */
if(value1 > value2){
tempSwap = temp1;
temp1 = temp2;
temp2 = tempSwap;
}
maxIter = numIterations(temp1);
for(iterValue = temp1; iterValue < temp2; iterValue++){
int currIter = numIterations(iterValue);
if(currIter > maxIter){
maxIter = currIter;
}
}
printf("%d %d %d\n", value1, value2, maxIter);
}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 3n+ 1 : y u always go WA/RUNTIME!?

http://uva.onlinejudge.org/data/p100.c.html

input 9 1
output should be 9 1 20
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: If you get WA in problem 100, read me before post!

http://uva.onlinejudge.org/data/p100.c.html

input 9 1
output should be 9 1 20
Check input and AC output for thousands of problems on uDebug!