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

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 100

Post by Obaida » Sun Jul 06, 2008 6:32 am

What will happen if two is grater then one?
I think, Then you should exchange the values. :wink:
try_try_try_try_&&&_try@try.com
This may be the address of success.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

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

Post by Obaida » Sun Jul 06, 2008 12:01 pm

You shouldn't submit same problem in several place!!!
try_try_try_try_&&&_try@try.com
This may be the address of success.

mrmrumman
New poster
Posts: 10
Joined: Sat Jul 05, 2008 11:26 pm
Location: Dhaka
Contact:

Volume 100 with WA message

Post by mrmrumman » Sun Jul 06, 2008 8:25 pm

Code: Select all

# include <stdio.h>

int main()
{
	
	int i=0, max;
	int one, two;
	while(scanf("%d %d",&one,&two)==2)
	{
		int j=one;
		int k=j,max=0;
		while(j<=two)
		{
			one=j;
			i=0;
			while(one!=1)
			{
				if(one%2==0)
				{
					one=one/2;
					i++;
				}
				else if(one%2==1)
				{
					one=3*one+1;
					i++;
				}
			}
			i++;/*for one=1*/
			if(max>i)
				max=max;
			else
				max=i;
			j++;
		}
		printf("%d %d %d\n",k,two,max);
	}
	return 0;
}
This is my code anyone can tell why it shows WA error.
R|_|\/|\/|/-\|\|

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 100

Post by Obaida » Mon Jul 07, 2008 9:56 am

Check this.
INPUT:

Code: Select all

10 1
OUTPUT:

Code: Select all

10 1 20
try_try_try_try_&&&_try@try.com
This may be the address of success.

mrmrumman
New poster
Posts: 10
Joined: Sat Jul 05, 2008 11:26 pm
Location: Dhaka
Contact:

Re: 100

Post by mrmrumman » Mon Jul 07, 2008 10:05 am

Thanks Opu bhaiya and mf my solution has been accepted. :D
R|_|\/|\/|/-\|\|

passworder
New poster
Posts: 1
Joined: Thu Jul 17, 2008 1:46 am

The 3n + 1 problem

Post by passworder » Thu Jul 17, 2008 1:52 am

I'm trying to solve the 3n + 1 problem and finally got a program that worked. I've tested it and the result is correct. I also tested it in comparison of a working example and it got the correct values. However, it says my source code is wrong.

Can someone please tell me what's wrong with this code and why it won't work.

Code: Select all

#include <iostream>

int main() {
	int n=0, length = 1, max = 0;
	int i,j;

	while (std::cin >> i >> j) {
	    for (int I=i;I<j;I++) {
	    	n = I; // set 'n' to the current cycle 

		    // perform the necessary operations on 'n' until its value is 1
	        while (n != 1) {
	    	    if (n%2 == 0)
		        	n/=2;
		        else
		    	    n = 3*n+1;

		        length++;
	        }

		    // check if the current cycle length is greater than the max value
		    if (length > max)
		    	max = length;

		    // reset the length variable so we can check the max value again next cycle
		    length = 1;
	    }

	    std::cout << i << " " << j << " " << max << "\n";
		max = 0;
	}

	while (std::cin) std::cin.get();
	return 0;
}
I'm making this challenge from the site: http://www.programming-challenges.com
Thankful for help.

ljh
New poster
Posts: 2
Joined: Fri Jul 18, 2008 7:32 am

Re: 100

Post by ljh » Fri Jul 18, 2008 7:41 am

when input is testcase, output is correct.
but i got WA.
please help me TT

Code: Select all

import java.util.Scanner;

class Main
{
	public static void main(String[] args) 
	{
		try
		{
			Scanner scan = new Scanner(System.in);
			String input;
			
			int i, j, k;
			
			for(;scan.hasNext();)
			{
				input = scan.nextLine();
				String[] temp = input.split(" ");
				
				i = Integer.parseInt(temp[0]);
				j = Integer.parseInt(temp[1]);
				
				if(i>j)
				{
					k = i;
					i = j;
					j = k;
				}
				
				System.out.println(input + " " + solution(i, j));
			}
		} 
		catch(Exception e)
		{
			System.exit(0);
		}
	}
	
	static int solution(int i, int j)
	{
		int n, a, count, result=0;
		
		for(a=i; a<=j; a++)
		{
			n = a;
			
			for(count=1;; count++)
			{
				if(n == 1)
					break;
				else if(n%2 == 0)
					n = n/2;
				else
					n = 3*n + 1;
			}
			
			if(count > result)
				result = count;
		}
		
		return result;
	}

}

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 100

Post by x140l31 » Sat Jul 19, 2008 2:15 am

I think it's the same problem that I had got

This is the solution that a poster gives me...
Ron wrote:To x140l31,

Code: Select all

System.out.println(line + " " + c);
line contains a '\n' also...
so you have to print i and j before it, when you take values in integers.
then print c .

your remaining code is ok...!!!
try changing your

System.out.println(input + " " + solution(i, j));

ljh
New poster
Posts: 2
Joined: Fri Jul 18, 2008 7:32 am

Re: 100

Post by ljh » Mon Jul 21, 2008 2:40 am

thanks
I changed my code.

System.out.println(input + " " solution(i, j));
-->
System.out.println(i + " " + j + " " solution(i, j));
-->
System.out.print(i + " " + j);
System.out.println(" " + solution(i, j));

but i got all WA.

if i have miss understand your advice, please give me the example.

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

Re: 100

Post by x140l31 » Mon Jul 21, 2008 9:44 pm

be careful with

System.out.println(i + " " + j + " " solution(i, j));

it's possible that you have swaped "i" and "j" before...

try to do this:

Code: Select all

............
            i = Integer.parseInt(temp[0]);
            j = Integer.parseInt(temp[1]);
            int mini = Math.min(i, j);
            int minj = Math.max(i, j);
            System.out.println(i + " " + j + " " solution(mini, minj)); 
............

User avatar
wmqwj
New poster
Posts: 4
Joined: Thu Aug 14, 2008 3:32 am
Contact:

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

Post by wmqwj » Thu Aug 14, 2008 3:52 am

Hello everybody,
i know this sounds weird, but its true. :roll:
this is my C++ code:

Code: Select all

#include<cstdio>
#include<iostream>
using namespace std;
int main()
{
    unsigned long int n=0,max=0,x=0,s=0,e=0,i=0,s1=0,e1=0;
    bool first=true;
    while(cin>>s)
    {
                 if(first==false) cout<<endl;
                 first=false;
    cin>>e;
    if(s>e)
    {
        s1=e;
        e1=s;
    }
    else
    {
        s1=s;
        e1=e;
    }   
    max=0;
    for(i=s1;i<=e1;i++)
    {
                     n=i;
                     x=0;
                           while (n > 1)
                                   {
                                       if (n%2 != 0)
                                             n=3*n + 1;
                                                 else
                                                       n= n / 2;
                                                    x++;
                                       }
                                       if(max<x+1) max=x+1;
                     }
                         cout<<s<<" "<<e<<" "<<max;    
    }
cout<<endl;
    return 0;
}
removing the end line at the end of the code, will get a WA.
this happened to me in another problem "Minesweeper" i kept trying it all night.
good luck everyone.. :D

shorojini
New poster
Posts: 8
Joined: Sat Aug 16, 2008 8:14 am

Re: 100

Post by shorojini » Sat Aug 16, 2008 8:28 am

can anyone help me with this code-
#include<iostream>
using namespace std;
int main()
{
long long a,b,len,k,i,n;
while(cin>>a>>b)
{
long long max=1;
n=a;
i=a;
while(i<=b)
{

k=0;

while(i!=1)
{
if((i%2)!=0)
{i=(3*i)+1;}
else
{i=i/2;}
k=k+1;
}
len=k+1;
if(len>max)
max=len;
a++;
i=a;
}
cout<<n<<" "<<b<<" "<<max<<"\n";
}
return 0;
}

always shows wrong answer

StayPuft
New poster
Posts: 1
Joined: Sat Aug 16, 2008 1:46 pm

Re: 100

Post by StayPuft » Sat Aug 16, 2008 1:50 pm

The left bound ist not always smaller than the right.

mps
New poster
Posts: 5
Joined: Thu Aug 28, 2008 11:49 pm

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

Post by mps » Thu Aug 28, 2008 11:55 pm

My Code:

Code: Select all

#include <iostream>
#include<iomanip>
using namespace std;
int main(int argc,char *argv[])
{
  long int i=0,j=0;
  while(scanf("%ld %ld",&i,&j)
		!=EOF)
    {
//    cin>>i>>j;
//  scanf("%ld",&i);
//  scanf("%ld",&j);
    cout<<i<<" "<<j<<" ";
    if(i>j)
     {long int x;
      x=i;
      i=j;
      j=x;}
  int *flag= new int[j-i+1];
  long int a=0,n=1,count=1;
  for (a=0;a<=j-i+1;a++)
   flag[a]=1;  
  for(a=i;a<=j;a++)
  {
        long long x=a;
        count=1;
         if (flag[a-i])
        {           
           while(x!=1)
            {
                       if (x%2)
                          x=3*x+1;
                       else
                          x=x/2;
                       if(x>=i && x<=j)
                        flag[x-i]=0;                      
                 count++;      
             }
        }
      n=count>n?count:n;
  }    
  cout<<n;
  delete[] flag;
}
}

Getting Runtime error! Please help

User avatar
wmqwj
New poster
Posts: 4
Joined: Thu Aug 14, 2008 3:32 am
Contact:

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

Post by wmqwj » Fri Aug 29, 2008 2:55 am

Hi mps, :P
runtime errors are mostly produced due to: memory allocation errors,invalid memory reference or division by zero.
of course there are many other reasons, but these are the most common.
in your code there is a memory allocation problem in the line:

Code: Select all

  int *flag= new int[j-i+1];
when trying the first test case: 1 10 it it made a terrible segmentation fault and crashed the whole system.
so just by changing it to

Code: Select all

  int *flag= new int[1000000]; 
it worked like a charm.
my advice, don't allocate arrays with a variable size, always allocate arrays with the maximum size of input (constant), to avoid this error.
now, correct your code, and re-submit it, :wink:
Good luck,

Post Reply

Return to “Volume 1 (100-199)”