100 - The 3n + 1 problem

[Obaida]

would you please tell me why this will get acc???
You are declearing variables as unsigned long int
But in scanf and printf you are using %d?
I think this should be %lu.

[mf]

would you please tell me why this will get acc???
You are declearing variables as unsigned long int
But in scanf and printf you are using %d?
I think this should be %lu.

That's surely wrong, and probably won't work on 64-bit systems (where sizeof(long) != sizeof(int)), but judge is using a 32-bit compiler and OS, so sizeof(int) = sizeof(long) = 4. And all inputs are small non-negative numbers, so their binary representation in types 'int' and 'unsigned' is exactly the same. So here it happens to make no difference.

[zid]

verdict Wrong answer.

./100 < input.txt

output:

Code: Select all

1 10 20
100 200 125
201 210 89
900 1000 174
10 1 20
200 100 125
210 201 89
1000 900 174
2 1 2
3 1 8
4 1 8
2 2 2
3 2 8
2 1 2
3 1 8

Can't find any value that breaks it? Supports flipping the inputs and matches the testcases given in the question.

Any ideas?

[navin32]

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#define max 100001
using namespace std;

int main()
{
int n,t;
int v[max];
int i;

v[0] = 0 ;
v[1] = 1 ;
v[2] = 2 ;

for(i = 3 ; i < max ; i++ )
{
t = 1 ;
n = i;
while( n > 1 )
{
if( n%2 == 0 )
{
if( n < i )
break;
else
n/=2;
t++;
}
else
{
n = ( (3*n) + 1 ) >> 1;
t+=2;
}
}
v = v[n/2]+t;
}


int l , u, ol, ou ;
while ( scanf("%d %d",&l,&u) == 2 )
{
ol = l;
ou = u;

if ( l > u ) swap (l,u) ;

printf("%d %d %d\n",ol,ou,*max_element(v+l,v+u));
}
}


this is my code but it shows wrong angwer.................
pls anyone help me

[sazzadcsedu]

Several things to note:

The title of post should be 100: 3n+1,not WA,TLE,CE etc.
You didn't even mention problem name/no.

you have define max (#define max 100001) which should be 1000001.

you define main function as a integer type but didn't return anything.so add return 0;

i think you should correct this and then search for sample input in board if WA.

[navin32]

thank you very much...........
l got accepted.......................

[C0d3R]

OK... i'm new with this type of contest ...
I resolve a problem - 3n+1 Problem - it works Fine in Eclipse But i have this error in UVA onlinejuge : Runtimerror
could You help me
this is the code
-----------------------------
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
class Test {
public static int Clength (int n){
int l=0;
while (n!=1){
if (n%2!=0)
{n= (3*n)+1 ; l++; }
else {n=n/2 ; l++ ;}
}
return l+1;
}
public static int Bigkeeper (int a,int b){
int big=0;
for (;a<b+1;a++){
if (big<Clength(a))
big =Clength(a);}
return big;
}
public static void main(String[] args) throws IOException {
BufferedReader lire = new BufferedReader (new FileReader ("c:\\100.in"));
PrintWriter ecrire = new PrintWriter (new FileWriter ("c:\\100.out"));
String str;
String []nbr;
while ((str=lire.readLine())!=null){
nbr =str.split(" ");
ecrire.println(nbr[0]+" "+nbr[1]+" "+Bigkeeper(Integer.parseInt(nbr[0]),Integer.parseInt(nbr[1])));
}lire.close();
ecrire.close();

}
}
--------------------------------

[mf]

File I/O is forbidden. And FYI, judge is using Linux, so filenames like "c:\100.in" don't even make sense to it.

Your program is supposed to read input from standard input (Systen.in in Java), and write output to standard output (System.out).

[Nescience]

Yeah, I just got 0.012 with precomputed tables and can't seem to improve on that. I imagine those that have a running time of 0 are doing something highly unusual, or I am missing something fundamental.

[fahim_xubayer]

i am new to programming.
can anyone tell me why i am getting TLE for the following code--

Code: Select all

#include<stdio.h>
int main(){
  
  unsigned long int a,b,c,d,e,f,x,y;
  while(scanf("%lu %lu",&x,&y)==2){
    if(x>y){
    a=x;
    b=y;
  }
    if(y>x){
    a=y;
    b=x;
  }
    f=0;
  
    for(c=b;c<=a;c++){
      d=c;
      e=0;
     
      while(1){
        if(d==1)
        break;
        if(d%2==0){
        d=d/2;
        e++;
     
        continue;
      }
        if(d%2!=0){
        d=3*d+1;
        e++;
     
        continue;
      }
    }
   
      if(e>f)
      f=e;
 
    }
  printf("%lu %lu %lu\n",x,y,f+1);
}
return 0;
}

[Marcel Hernandez]

I'm pretty sure that the OJ input for this problem isn't as exhaustive as it should be.


Yesterday I tried to solve problem nº 14 from projecteuler.net (which asks for the positive number below 1 milion which generates the longest Collatz sequence) with my AC code of problem 100 from UVa.

So I typed in "1 1000000" and the output was "1 1000000 476", and with some minor modifications to the code I managed to discover that that maximum corresponded to number 910107. But to my astonishment my answer was rejected again and again. It took me some time to realize what I was doing wrong.

In fact, the actual maximum was 525 and corresponded to 837799 (don't want to spoil it), but for that number the 59th member of the sequence grows above 2^31, leading to an integer overflow and causing my old program to abort the loop prematurely and to answer 59 when computing 837799 , instead of 525 .

The fix whas quite straightforward, I just had to store the ith value of the sequence in a 64bit integer while processing it, but the fact is that today UVa OJ still accepts my old buggy code but also the fixed one, so the logical conclusion is that private input does not include a critical test case containing 837799 within its range.


Hope this helps.

MH

[mf]

They can't include such numbers because problem statement forbids it - it says that 32-bit integers will be enough for the test cases in the input.

[arifcsecu]

Ok sorry, some bugs... but I fixed all of that and still got RE. Can you tell me please what could be a greater bug than all those? I tested and it's OK (running on Windows XP) I even tested it in cygwin I'm out of mind.

Code: Select all

// FIXED CODE
#include <stdio.h>
#include <stack.h>
#include <list.h>
#include <string.h>
#define MAX 1000001
int main()
{
  int *Vector, max, n1, n2;
  Vector = new int[MAX];
  memset(Vector, 0, MAX*sizeof(Vector));
  n1 = n2 = 1;
  while(n1 < MAX)
  {
    Vector[n1] = n2;
    n2++;
    n1*=2;
  }
  stack<int,list<int> > stack;
  while(1)
  {
	if (scanf("%d %d", &n1, &n2) == EOF)
      break;
  	printf("%d %d ", n1, n2);
    n2++;
    max = 0;
    for(int i=n1; i<n2; i++)
    {
      int k = i, cont = Vector[i];
      if (cont == 0)
      {
        while(k>1)
        {
          stack.push(k);
          k = (k % 2 == 0)?(k/2):(3*k+1);
          cont = Vector[k];
          if (cont > 0)
          {
            k = 1;
          }
        }
        while(!stack.empty())
        {
          Vector[stack.top()] = ++cont;
          stack.pop();
        }
      }
      max = (max<cont)?cont:max;
    }
    printf("%d\n", max);
  }
  delete Vector;
  return 0;
}

I tryed this other code, and still RE

Code: Select all

#include <vector.h>
int main()
{
  int max, n1, n2;
  vector<int> myVector(MAX);
  max = MAX;
  n1 = n2 = 1;
  while(n1 < max)
  {
    myVector[n1] = n2;
    n2++;
    n1*=2;
  }
  stack<int,list<int> > stack;
  while(1)
  {
    if (scanf("%d %d", &n1, &n2) == EOF)
      break;
    printf("%d %d ", n1, n2);
    n2++;
    max = 0;
    for(int i=n1; i<n2; i++)
    {
      int k = i, cont = myVector[i];
      if (cont == 0)
      {
        while(k>1)
        {
          stack.push(k);
          k = (k % 2 == 0)?(k/2):(3*k+1);
          cont = myVector[k];
          if (cont > 0)
          {
            k = 1;
          }
        }
        while(!stack.empty())
        {
          myVector[stack.top()] = ++cont;
          stack.pop();
        }
      }
      max = (max<cont)?cont:max;
    }
    printf("%d\n", max);
  }
  return 0;
}

Help...

What a easy problem it is!
45229 solve it ha ha ha.

For any two numbers i and j you are to determine the maximum cycle length over all numbers between i and j.
here don't say that i>j or i<j
u should consider both case
valid input: 1 5
5 1
output:
1 5 8
5 1 8

another matter is that :

u don't need to use vector or array anyway
u just calculate the length of the cycle
and compute the maximum cycle length

then print as usual
Hope it helps

[thinker_01]

Same problem can some one help
How can this code give me wrong answer
any help will be appreciated as its the first
problem that i tried and is getting so many
WA and i think my code is correct

#include<stdio.h>

long huh(long i,long j)
{
long _i,_j,n,temp,max=0,count;
if(i<=j)
{
_i=i;
_j=j;
}
else
{
_i=j;
_j=i;
}
for(n=_i;n<=_j;n++)
{
temp=n;
count=1;
while(temp-1)
{
if(temp%2) temp=temp*3+1;
else temp/=2;
count++;
}
if(count>max) max=count;
}
return max;
}

int main()
{
long i,j;
while(scanf("%ld %ld",&i,&j)!=EOF)
{
printf("\n%ld %ld %ld",i,j,huh(i,j));
}
return 0;
}

[arifcsecu]

Silly mistake here

change this line
printf("\n%ld %ld %ld",i,j,huh(i,j));

as
printf("%ld %ld %ld\n",i,j,huh(i,j));

Hope it helps