100 - The 3n + 1 problem

[Rob Ferguson]

Your C++ program has solved Ok the problem 100 (The 3n + 1 problem)
in 3.630 seconds using as much as 440 kbytes of virtual memory.
Congratulations!

->Thanks!<-

[cpp]
/* @JUDGE_ID: XXXXXX 100 C++ */
@BEGIN_OF_SOURCE_CODE
#include <iostream>
using namespace std;
int main() {
register long int n,i,j,ii,jj,k,l,c;
while(cin >> i >> j) {
ii=i;jj=j;
if(i>j) {
k=i;i=j;j=k;
}
l=0;k=i;
for (k;k<=j;k++) {
n=k;c=0;
while (n) {
c++;
if (n==1) {
break;
}
if (n%2) {
n=(3*n)+1;
} else {
n/=2;
}
}
if (c>l) {
l=c;
}
}
if(ii<jj) {
cout << i << " " << j << " " << l << endl;
} else {
cout << j << " " << i << " " << l << endl;
}
}
return 0;
}
@END_OF_SOURCE_CODE
[/cpp][/code]

[displesmer]

I can't understand why my program has errors , it runs correctly under my BC++ compiler but when i send it the judge says that my program has these errors:

Here are the compiler error messages:

01170600_24.c: In function `main':
01170600_24.c:28: parse error before `/'
01170600_24.c:42: parse error at end of input

And my program is:
[c]

Code: Select all

/*   @JUDGE_ID: 0000000 100 C */ 


[color=darkblue]/*@BEGIN_OF_SOURCE_CODE*/


#include<stdio.h>

void main()
{
  long i=1,j=1;
  long k,c;
  long max=0,temp;

  while(scanf("%ld %ld",&i,&j))
  {
	 if(!(i&&j))
		return;

	 printf("%ld %ld ",i,j);


	 max=0;
	 for(k=i;k<=j;k++)
	 {
	   temp=1;
	   c=k;
	   while(c!=1)
	   {
	     if(c&1)
	     {
	       c=c+(c<<1)+1;//c=c*3 + 1
	     }
	     else
	     {
	       c>>=1;
	     }
	     temp++;
	   }
	 printf("%ld\n",max);
  }
}
 

/* @END_OF_SOURCE_CODE*/

[/c][/color]Please help me , or if you want you can send your messages directly to mahdi_xpower@lycos.com
Thank you very very much.

[turuthok]

It might be your 'comment' ... you seem to be using C++ comment '//' ... if you compile using strict ANSI C compiler, then there will be compile errors.

-turuthok-

[otavio]

#include <stdio.h>
main (){
/* @JUDGE_ID: 100 C */
long int i, first, last, count, n, greatest;
long int tam, temp;
long int firstorig, lastorig;

while (scanf("%d %d", &first, &last) == 2){
greatest = 0;

/* guarda os valores originais */
firstorig = first;
lastorig = last;

/* trocar se estiver fora de ordem */
if (first > last){
temp = first;
first = last;
last = temp;
}

for (i=first; i<=last; i++){
n = i;
count++;

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

if (count > greatest)
greatest = count;
count = 0;
}
printf ("%d %d %d\n", firstorig, lastorig, greatest);
}
}

[Vladimir Fran]

Hi! I'm having a WA with this code. I noticed that with big values like this: 1 200000; the code doesn't work. In the loop while(k>num0), "k" isn't assuming all values that it supposed to.

Can someone help me?

[code]
/*@BEGIN_OF_SOURCE_CODE*/
#include <stdio.h>
#include <stdlib.h>
//#include <iostream.h>
/*@JUDGE_ID: 24657JF 100 C++ */

void swap(int *x, int *y) { *x=*y+*x; *y=*x-*y; *x=*x-*y; }

int test(int j);
int count=1;

int main(void){


int num0,k,num1,dif,swp,cycles,cycle2;




swp=0;
while(scanf("%d %d", &num0, &num1) == 2) {

if(num0 > 0 && num0 < 1000000 && num1 > 0 && num1 < 1000000 )
{
if(num0 >num1)
{
swap(&num0,&num1);
swp=1;
}

dif=(num1-num0);

if(dif==0)
{
count=1;
cycles=test(num0);
}
else{
count=1;

cycles=test(num1);
k=num1;
while(k>num0)
{
count=1;
k--;

cycle2=test(k);
if(cycle2>cycles) cycles=cycle2;
}


} /*fim do else */
if(swp==1)
printf("%d %d %d\n",num1,num0,cycles);
else
printf("%d %d %d\n",num0,num1,cycles);
}
}/*fim do while */
printf("fim");
return 0;
}

int test(int j){

if(j==1)
return count;
if((j%2)==0)
j/=2;
else
j=(3*j)+1;
count++;
test(j);
// return 0;
}

/* @END_OF_SOURCE_CODE */[code]

[turuthok]

It might be caused by your local variable 'count'.

As far as I can tell, this local variable is defined in the stack and the value cannot be guaranteed to be 0 initially.

Try to test your program with one number only (i.e.: i and j are the same) and see if it outputs the expected result.

-turuthok-

[a_jain]

Hi all,

I have a reply from judge saying:
"Your program has not solved the problem. It ran during 2.120 seconds."

This is my code:


/* @JUDGE_ID: XXXXXXX 100 C++*/

#include<iostream>
using namespace std;

int Cyclelength(int num)
{
int count = 1;

while(num > 1)
{

(num%2 == 1)?num = 3 * num + 1 : num /= 2;
count++;
}

return count;
}

void main()
{
int num1, num2;

while(cin >> num1 >> num2)
{
int maxCount = -1;
for(int i = num1; i <= num2; i++)
{
int temp = Cyclelength(i);
if(temp > maxCount)
maxCount = temp;
}

cout << num1 << " " << num2 << " "
<< maxCount << endl;
}
}
[/cpp]

[a_jain]

Don't worry!

[Iv@n]

You must to test all input possibilities like "num1 == num2", the input order must be the same of output "10 1" ...

Iv@n
Brasil

[brianschroeder]

Sometimes the numbers get so large you will have overflow in an int variable.

[Moni]

Have you swaped the values already before printing the results? Then output will be reversed. So check!

[ec3_limz]

Haha...

Try cheating in Problem #136, since there is no input for that problem and the output is always the same. Just print the answers; who cares about the calculation.

[Eric]

There are some problems that you can simply hard code the output.
So, low memory and time can be spent on these problem.
Also, some problems only require simple algorithm like addition. So, the time needed is fairly small.

[KoKo]

I don't know what's wrong with my program.I try the program on my computer,it's OK.But when I send it to judge,it response wrong answer.
Can anyone help me?Maybe try the program on your computer(if you have JDK,please),then tell me what's the problem is,thank you.



import java.io.*;
import java.util.*;

class Main
{
static String ReadLn (int maxLg)
{
byte line[] = new byte [maxLg];
int lg = 0, input = -1;

try
{
while (lg < maxLg)
{
input = System.in.read();
if ((input < 0) || (input == '\n')) break;
line [lg++] += input;
}
}
catch (IOException e)
{
return (null);
}

if ((input < 0) && (lg == 0)) return (null);
return (new String (line, 0, lg));
}

public static void main (String args[])
{
Main myWork = new Main();
myWork.Begin();
}

void Begin(){
String input;
StringTokenizer idata;
int c, d, x, max, arr[] ;

while ((input = Main.ReadLn (255)) != null)
{
idata = new StringTokenizer (input);
c = Integer.parseInt (idata.nextToken());
d = Integer.parseInt (idata.nextToken());

arr=new int[d-c+1];
x=d;
max=0;
while(x!=(c-1)){
if(arr[x-c]==0){
int i=x;
int counter=1;
while(i!=1){
if((i%2)==1){
i=(3*i+1);
if(i<=d&&i>=c)
arr[i-c]=1;
counter++;
}

if((i%2)==0){
i=(i/2);
if(i>=c&&i<=d)
arr[i-c]=1;
counter++;
}
}
if(counter>max)
max=counter;
}
x--;
}
System.out.println(c+ " " + d + " " + max);
}
}
}

[25258FM]

why my C program is exceding time limit....
but using the same concept , my friend write in C++.
he do not.
mine:
[c]/* @JUDGE_ID: XXXXXX 100 C */
#include <stdio.h>
int calc( unsigned int);
unsigned int i;
int main(void)
{
unsigned int input_1,input_2,k,first,second,no1,max;


do {
scanf("%u",&input_1);
scanf("%u",&input_2);
if (input_1>input_2)
{
first=input_2;
second=input_1;
}
else
{
first=input_1;
second=input_2;
}
i=1;
max=calc(first);
for (k=(first+1);k<=second;k++)
{
i=1;
no1=calc(k);
if (no1>max)
max=no1;
}
printf("%u %u ",input_1,input_2);
printf("%u\n",max);

}while (1);

return 0;

}


int calc( unsigned int input_1)
{

while (input_1!=1)
{
if (input_1 % 2==1)

input_1=3*input_1+1;

else

input_1=input_1/2;

i++;

}

return i;

}[/c]

my friend:

[cpp]#include <iostream>
using namespace std;

int FindCycleLength(unsigned int);
int FindMaxCycle(unsigned int,unsigned int);

void main()
{
unsigned int i = 0;
unsigned int j = 0;
while(cin >> i >> j)
cout << i << " " << j << " " << FindMaxCycle(i,j) << "\n" ;

}

int FindCycleLength(unsigned int k)
{
int index = 1 ;
while (k != 1)
{
if (k % 2 == 1)
k = 3*k+1;
else
k = k/2;
index++ ;
}
return index;
}

int FindMaxCycle(unsigned int a,unsigned int b)
{
int i;
if (a > b)
{ i = a ; a = b; b = i; }
int MaxCycle = FindCycleLength(a);
for ( i=a+1; i <= b; i++)
if (FindCycleLength(i)> MaxCycle)
MaxCycle = FindCycleLength(i);
return MaxCycle;

}
[/cpp]