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

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

I didn't check your code completely. But I see, you haven't considered that first number can be greater than the second.
There are many posts about this topic. Have a look at them.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman »

Your program should be able to read & process multiple test cases. You may try using -

Code: Select all

while(scanf(" %ld %ld",&x,&y)==2)
{
   //process
}
You should never take more than you give in the circle of life.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman »

As far as I have seen your program, it should terminate at EOF. Did you provide inputs from stdin or from a file while testing? If from stdin, then press ctrl + Z after all the input sets after the input cases.
You should never take more than you give in the circle of life.

=viki=
New poster
Posts: 23
Joined: Mon Jan 02, 2006 6:23 pm
Contact:

Post by =viki= »

Emilio wrote:The input haven't only a case.
You must check if x is greater than y or not.
By other hand, you must reuse another post that talk about the same problem, also there are a lot of post about this problem that you can have a look and I'm almost sure that they will resolve your doubts and mistakes.
Good luck! :D

got AC for prob no. 101 .. now i know for prob 100 end of input is not specified. how long to take the input?

and if x < y then what should i do ... ignore it and take the next input
or stop the prog execution...(no point in printing error msg)...

=viki=
New poster
Posts: 23
Joined: Mon Jan 02, 2006 6:23 pm
Contact:

Post by =viki= »

now im getting WA for the same code posted above...

now whats the prob ... plz help

Schutzstaffel
New poster
Posts: 37
Joined: Fri Apr 30, 2004 6:52 pm
Location: Portugal

Post by Schutzstaffel »

If x < y then you swap the value of y to x and vice versa or if just use the min(x,y) for x and max(x,y) for y.
Image

=viki=
New poster
Posts: 23
Joined: Mon Jan 02, 2006 6:23 pm
Contact:

Post by =viki= »

changed my prog but still getting WA plz help..


Code: Select all

#include<stdio.h>


long max=0;
void process(long,long);

int main(void)
	{
         long x,y,a,b;
         while(scanf("%ld%ld",&x,&y)!=EOF){
            if(x>y){
            a=x;
            b=y;
            process(b,a);
         }

         process(x,y);
         printf("%ld  %ld  %ld\n",x,y,max);
         max=0;
         }
	 return 0;
 	}


void process(long x, long y)
	{long i,count=0,n;
	 for(i=x;i<y;i++)
		{
		 n=i;
		 while(1)
		       {
			count++;
			if(max<count)
				max=count;
			if(n==1)
			       {
				count=0;
				break;
			       }

			if((n%2)==0)
				n=n/2;

			else
				n=(3*n)+1;

		       }
		}
	}

whats the problem here now....plz help

Schutzstaffel
New poster
Posts: 37
Joined: Fri Apr 30, 2004 6:52 pm
Location: Portugal

Post by Schutzstaffel »

I think you're a little confused, let's see:

Code: Select all

long x,y,a,b;
         while(scanf("%ld%ld",&x,&y)!=EOF){
            if(x>y){
            a=x;
            b=y;
            process(b,a);
         }

         process(x,y);
         printf("%ld  %ld  %ld\n",x,y,max);
         max=0;
         } 
- You check if x > y, if so you use two variables to get the values of x and y and then process the input in the switched way...ok is correct but why the two extras variables? you can just do process(y,x) if x > y.

- Also if x > y you process with y first and then x (correct), after that you process again with x first and then y (wrong).
You're missing an else statement.

Be sure to test your program before submiting.
Image

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman »

Still a lot of error left.
1. Swap (x,y) if x>y.
2. Be carefull about the output format. Your printf statement has extra space charecter which will immediately lead to wrong answer.
3. In the for loop within process, why should you write in this way?-

Code: Select all

for(i=x;i<y;i++)
It must be

Code: Select all

for(i=x;i<=y;i++)
You should never take more than you give in the circle of life.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

Post by Emilio »

Schutzstaffel wrote:
If x < y then you swap the value of y to x
For her(I guess) code must swap the values if x > y.

=viki= wrote
how long to take the input?
For example in this manner:

Code: Select all

while (scanf("%d%d",&x,&y)==2)
{
    .....
}

Schutzstaffel
New poster
Posts: 37
Joined: Fri Apr 30, 2004 6:52 pm
Location: Portugal

Post by Schutzstaffel »

It was actually a typo :oops: my bad.
Image

=viki=
New poster
Posts: 23
Joined: Mon Jan 02, 2006 6:23 pm
Contact:

Post by =viki= »

modified my code and got AC thanx for helping......

Code: Select all



oopss  sorry my mistake... :oops: 



Last edited by =viki= on Thu Jan 05, 2006 12:02 pm, edited 1 time in total.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman »

Please immediately remove the code. It's not a good practice to leave AC codes on board as others can get AC simply by just copying it & sending to judge.
You should never take more than you give in the circle of life.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan »

To =viki=, You should read two numbers until EOF. So, use

Code: Select all

while(scanf("%ld%ld",&x,&y)==2)
{
    //process
}
And remember that x can be greater than y and both can be equal. So, change ..

Code: Select all

void process(long x, long y) 
   {long i,count=0,n;
   if(x>y) 
      //swap x,y 
    for(i=x;i<=y;i++)  //i <= y
      {
          //Remaining code
      }
   }


Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Red Cent
New poster
Posts: 5
Joined: Sun Jan 22, 2006 9:23 pm

CE with problem 100 3N+1

Post by Red Cent »

Im getting discouraged here.

I know the algorithm. Ive compiled successfully on linux with gcc using the -ansi flag.

But yet Im getting the CE problem.

Here is the code:

/* 3N+1

*/
#include <stdio.h>
#include <stdlib.h>
int cycles(long);
int main (int argc, char **argv)
{
int result = 1;
long i=1;
int stepper = 1, max=1;
long firstnumber, secondnumber;
while (scanf("%ld %ld",&firstnumber, &secondnumber)!=EOF)
{
/*DEBUG
printf("\nfirstnumber = %ld",firstnumber);
printf("\nsecondnumber= %ld\n",secondnumber);
*/
if (firstnumber>secondnumber) stepper = -1;
for (i=firstnumber; i<=secondnumber; i=i+stepper)
{
result = cycles(i);
if (result > max) max=result;
result = 0;
}
printf("%ld %ld %ld\n",firstnumber, secondnumber, max);
firstnumber = 0;
secondnumber = 0;
max =1;
}
}

int cycles(long N)
{
int counter=1;
while (N!=1)
{
if (N%2==0) /*N is even*/
N=N/2;
else /*N is odd*/
N=N*3+1;
counter++;
}
return counter;
}

Post Reply

Return to “Volume 1 (100-199)”