100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

PROBLEM 100

Post by mntamim » Wed Nov 06, 2013 12:14 am

i cant understand why i get wrong answer
please help

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] = 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

Post by brianfry713 » Wed Nov 06, 2013 9:43 pm

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

Post by mntamim » Thu Nov 07, 2013 3:54 am

still wrong answer
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

Post by mntamim » Thu Nov 07, 2013 11:46 am

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

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!

Post by ecarrera » Wed Nov 20, 2013 3:21 am

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

Hope your answer

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!

Post by brianfry713 » Wed Nov 20, 2013 10:02 pm

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!

Post by ecarrera » Thu Nov 21, 2013 8:06 am

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!

Post by brianfry713 » Thu Nov 21, 2013 8:29 pm

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!

Post by ecarrera » Fri Nov 22, 2013 1:20 am

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.

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

100 - The 3n + 1 problem Runtime Error

Post by Jade__Dragon » Tue Dec 10, 2013 7:00 am

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 license header, choose License Headers in Project Properties.
 * 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
            {
                answer = result;
            }
        }
        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

Post by brianfry713 » Tue Dec 10, 2013 9:41 pm

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!?

Post by enil14someone » Fri Jan 03, 2014 2:32 am

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!

Post by greentea99 » Sun Jan 05, 2014 8:57 am

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!?

Post by brianfry713 » Wed Jan 08, 2014 2:06 am

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!

Post by brianfry713 » Wed Jan 08, 2014 2:10 am

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!

Post Reply

Return to “Volume 1 (100-199)”