100 - The 3n + 1 problem

[jtmh]

Java support is mentioned here. It will be greatly improved in the coming new Judge.

[law1009]

Excuse me!My code could run correctly in Dev c++, but can't be accepted by acm.
The message:"Your program has not solved the problem. It ran during 5.092 seconds."
What's wrong with it? Thanks.

Code: Select all

#include <iostream>

using namespace std;

int main(){
   int i=0;
   int j=0;

     
   while(cin>>i>>j){          
      int count;
      int val=0;              
      if(i>j){              
         int tmp;
         tmp=i;
         i=j;
         j=tmp;
      }      
      for(int s=i;s<=j;s++){
         count=1;                           
         int k=s;
         while(k!=1){
            if(k%2==1) k=3*k+1;  //odd
            else k=k/2;           //even
            count++;
         }
         if(count>=val) val=count;      
      }
      
      cout<<i<<' '<<j<<' '<<val<<endl;
          
   }    
   return 0;
}

[helloneo]

http://online-judge.uva.es/board/viewtopic.php?t=3015

You're not suppose to make a new thread on this problem

[law1009]

i am sorry.
i did't notice that thread.
i'll be careful at next time. thank for your advice.

[law1009]

[situation]
It could run well in Dev C++, but could't pass the demo of acm.
I already tried my best to find the bug but in vain.
Thanks for helping!

Code: Select all

#include <iostream>

using namespace std;

int main(){
   int i=0;
   int j=0;


   while(cin>>i>>j){
      int count;
      int val=0;
      if(i>j){
         int tmp;
         tmp=i;
         i=j;
         j=tmp;
      }
      for(int s=i;s<=j;s++){
         count=1;
         int k=s;
         while(k!=1){
            if(k%2==1) k=3*k+1;   //odd
            else k=k/2;           //even
            count++;
         }
         if(count>=val) val=count;
      }

      cout<<i<<' '<<j<<' '<<val<<endl;

   }
   return 0;
}

[trantri]

Java support is mentioned here. It will be greatly improved in the coming new Judge.

Thank you!

[jtmh]

[situation]
It could run well in Dev C++, but could't pass the demo of acm.
I already tried my best to find the bug but in vain.
Thanks for helping!

Code: Select all

#include <iostream>

using namespace std;

int main(){
   int i=0;
   int j=0;


   while(cin>>i>>j){
      int count;
      int val=0;
      if(i>j){
         int tmp;
         tmp=i;
         i=j;
         j=tmp;
      }
      for(int s=i;s<=j;s++){
         count=1;
         int k=s;
         while(k!=1){
            if(k%2==1) k=3*k+1;   //odd
            else k=k/2;           //even
            count++;
         }
         if(count>=val) val=count;
      }

      cout<<i<<' '<<j<<' '<<val<<endl;

   }
   return 0;
}

Note from the output description:

The integers i and j must appear in the output in the same order in which they appeared in the input...

[Vexorian]

I have gotten problem 100 to (accepted) in both Java an C, and I believe there to be a problem with the judge. The C program works no problem, but initially the Java program did not. I added a "hack" to the Java program, which actually causes it to miscalculate some values, and this program was accepted as correct.

The problem is that, in C even an unsigned long is not large enough to handle some of the numbers that will be encountered during calculation of the 3n+1 series. These numbers are (incorrectly) truncated, thus making 3n+1 < n sometimes. This doesn't cause any problems, assuming that I write my program in C, and the judge solutions are done in C, as they make the same mistakes and get matching answers.

However, if you use Java, it doesn't have the same limit for its long integers. It correctly calculates different values, thus not matching the (incorrect) judge. If you add in a hack into your java code, that is to truncate any value over the LONG_MAX value of c, you can get the java program to be accepted.

Just thought you might want to know that your "accepted" programs are all flawed, and perhaps it will help some students to be less frustrated with non-working java submissions.

I wanted to quote this rather old post, because in a sense it is right. The values do overflow with some of the bigger values allowed for the input in my program and it got AC.

But, the problem actually says:

You can assume that no operation overflows a 32-bit integer.

I think that since ints in JAVA are 32-bits then JAVA users should just use unsigned ints, but probably something has to be corrected in the problem's prompt for example an imperative "Assume that no operation overflows a 32-bit integer." or "Use 32 bits integers , assume that no operation overflows a 32-bit integer"

A better alternative (in my opinion) would be lowering the max input value so it doesn't overflow, though.

[jtmh]

That post seems no longer true because I got AC with unsigned long longs in C as well. That is, during the judgment, there are now

... no input values for which the intermediate results are too big to fit into a 32-bit number.

[Vexorian]

yeah, I tried testing further and it seems that the judge doesn't use the numbers that cause the overflow.

And since the unusual kind of this sequence the numbers that cause the overflow are lower than then limit although the limit doesn't cause the overflow.

[nnahata]

hi..
i write this code..even for worst case given by judge it work smoothly and giving right answer...but judge respnse is no...so plz suggest somethind....i already wested alot time in this prblem..me..



#include<iostream>
using namespace std;
int flag;
bool a[1000000];
int ans;
unsigned long int x,y,m1,m2,tmp;
int nahata(unsigned long int n)
{
ans++;
if(n>=x&&n<=y)
a[n]=true;
if(n==1)
return(0);
if(n%2==0)
{
n=n/2;
nahata(n);
}
else
{


n=n+(n+1)/2;
ans++;
nahata(n);
}
}
main()
{

for(int i=x;i<=y;i++)
a=false;

while(cin>>x)
{
m1=x;


int max=0;
cin>>y;
m2=y;
if(x>y)
{tmp=x;
x=y;
y=tmp;
}


if(x<(y/2))
x=y/2-1;


for(int i=x;i<=y;i++)
{


ans=0;
if(a==false)
{
nahata(i);
}
if(ans>max)
max=ans;
}

cout<<m1<<" "<<m2<<" "<<max<<"\n";
}
}




Thaxs in advance....

[sobuz]

#include<stdio.h>
int main()
{
unsigned long int n,i,count=0,j,k,max=0;
int sum=0,h[100],d=0,large=0,a[100];

while (scanf("%lu%lu",&n,&k)==2)
{
if(n<=k)
{
for(j=n;j<=k;j++)
{
i=j;
do
{
if(i%2!=0)
i=3*i+1;
else
i=i/2;
count++;

}while(i!=1);

if(large<count)
large=count;
count=0;
}
}

else if(n>k)
{ for(j=n;j>=k;j--)
{
i=j;
do
{
if(i%2!=0)
i=3*i+1;
else
i=i/2;
count++;

}while(i!=1);

if(large<count)
large=count;
count=0;
}
}


printf("%lu %lu ",n,k);
printf("%lu\n",large);
large=0;
}
return 0;
}

[User239]

This code is AC

Code: Select all

#include <iostream> 

using namespace std; 

int main(void){ 
   long i,j,m,temp,total,max; 
   while(cin>>i>>j){ 
      cout<<i<<" "<<j<<" "; 
      max=0; 
      if(i>j){ 
         temp=i; 
         i=j; 
         j=temp; 
      } 
      for(m=i;m<=j;m++){ 
         temp=m; 
         total=0; 
         while(1){ 
            if(temp==1){ 
               total++; 
               break; 
            } 
            total++; 
            if(temp%2==0) temp/=2; 
            else temp=3*temp+1;    
         } 
         if(total>max) max=total; 
      } 
      cout<<max<<endl; 
   } 
   return 0; 
} 

But this code wich does exactly the same is TLE. Why?!!!

Code: Select all

var
  i,j,m,temp,total,max:integer;

begin
  while not eof(input) do begin
    readln(i,j);
    write(i,' ',j,' ');
    max:=0;
    if i>j then begin
      temp:=i;
      i:=j;
      j:=temp;
    end;
    for m:=i to j do begin
      temp:=m;
      total:=0;
      while true do begin
        if temp=1 then begin
          inc(total);
          break;
        end;
        inc(total);
        if temp mod 2 = 0 then
          temp:=temp div 2 else
            temp:=3*temp+1;
      end;
      if total>max then
        max:=total;
    end;
    writeln(max);
  end;
end.

I tried to write longint instead of integer.

[blitzritz]

can anyone please tell me why am i getting Time Limit Exceeded??!!
heres my code..

#include<stdio.h>

void cycl(unsigned int a,unsigned int w)
{
unsigned int l,m,temp;
int k,f,b=0;
if(a>w)
{
temp=w;
w=a;
a=temp;
f=1;
}
for(m=a;m<=w;m++)
{
k=0;
k++;
l=m;
while(l!=1)
{
if(l%2==0)
l=l/2;
else
l=3*l+1;
k++;
}
if(b<=k)
b=k;
}
if(f==1)
printf("%d %d %d\n",w,a,b);
else
printf("%d %d %d\n",a,w,b);
}

void main()
{
unsigned int i,j;
start: scanf("%d %d",&i,&j);
cycl(i,j);
goto start;
}

thnx

[emotional blind]

can anyone please tell me why am i getting Time Limit Exceeded??!!

Because of INFINITE LOOP:

START:

...

goto START;

then when your program will stop.