100 - The 3n + 1 problem

[Ivchencov]

Hello!
plese help me with problem 100
This programm working perfeclty but I've still got WA

#include <iostream>


using namespace std;
int main(int argc, char *argv[])
{
unsigned i,j,k,n1, max,tmp,tmp1;
while (cin >>i >>j)
{

if (j<i)
{
tmp1=i;
i=j;
j=tmp1;
cout << j <<" " <<i;
}
else
cout << i << " " << j;
tmp=0;
for (k=i;k<=j; k++)
{
max=1;

n1=k;
while (n1!=1)
{
if (n1 % 2 == 0){
n1 = n1/2;
}
else{
n1 = 3*n1+1; }
max++;
if (max>tmp)
{
tmp=max;
}


}

}

cout << " " << tmp <<endl;}
return 0;
}

I want to know whats wrong with the code.If somebody help me i will be very gratefull

[emotional blind]

for this input

Code: Select all

1 1

output should be

Code: Select all

1 1 1

but your program gives

Code: Select all

1 1 0

this is the problem for which you got WA
change it and get accepted

[krik]

I trying with longint too :/
I have WA , and i can't to fix it
Please help.

function nx(liczba:word):word;
var licznik:word;
begin
licznik:=1;
while liczba>1 do
begin
inc(licznik);
if liczba mod 2=0 then
liczba := liczba div 2 else
liczba := liczba+liczba+liczba+1;
end;
nx:=licznik;
end;

var x,y,i,lol,max,temp:word;
begin
read(x,y);
write(x,' ',y,' ');
if x>y then
begin
temp:=x;
x:=y;
y:=temp;
end;

max:=nx(y);
lol:=x;

for i:=x+1 to y do
begin
temp:=nx(i);
if max<temp then
begin
max:=temp;
lol:=i;
end;
end;
writeln(max);
end.

[neno_uci]

Hi, I think that your problem is that you don't calculate all the values in the given interval, watch this:

Code: Select all

...
max:=nx(y); 
lol:=x; 

for i:=x+1 to y do 
...

I think that it must be:

Code: Select all

...
max:=nx(x); 
lol:=x; 

for i:=x+1 to y do 
...

otherwise you would compute nx(y) twice and won't compute nx(x) never, fix that mistake and then try again, hope this helps,

Yandry.

[neno_uci]

and please note that you must process input until the eof is reached

[jaracz]

"mn" can be greater than "mx", you should check it and replace them if necessary
and erase it:

Code: Select all

#ifndef ONLINE_JUDGE 
*stdin=*fopen("100.in","rt"); 
freopen("1000.out","w",stdout); 
#endif 

Regards

[asif_rahman0]

Don't worry.Read the problem carefully and do what the proccess tell there.Make sure ur code is little bit effecient as the input is 1,000,000.Check the output format.

BEST OF LUCK

[eg_frx]

Hi.

I'm a newbie @ Java.

I am trying to transplant the problems I solved in C++ to Java.

The following code always gives TLE:

Code: Select all

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

class Main
{
static String token( String delim ){ 
char c = delim.charAt(0); 
StringBuffer s = new StringBuffer(""); 
try{ 
while( delim.indexOf( (int) c ) != -1 && c != 65535 ) 
c = (char) System.in.read(); 
while( delim.indexOf( (int) c ) == -1 && c != 65535 ){ 
s.append( (char) c ); 
c = (char) System.in.read(); 
} 
}catch( Exception e ){ return (null); } 
if( s.toString().equals("") ) return null; 
return s.toString(); 
}

static int percentInt(){ 
String s = token(" \n\r\t " ); 
if( s == null ) return Integer.MIN_VALUE; 
try{ 
Integer i = new Integer( s ); 
return i.intValue(); 
}catch( Exception e ){} 
return Integer.MIN_VALUE; 
} 

    private static long a1, an, steps, max_steps, i, n;
    public static void main ( String[] args )
    {
        String in = null;
        StringTokenizer st = null;
        while (true)
        {
            a1 = percentInt();
            an = percentInt();
            System.out.print(a1+" "+an+" ");
            if (a1 > an) {
                steps = an;
                an = a1;
                a1 = steps;
            }
            max_steps = 1;
            for (i = a1; i <= an; ++i) {
                steps = 1;
                n = i;
                while ( n != 1 ) {
                    if ( n % 2 == 1)
                        n = n * 3 + 1;
                    else
                        n /= 2;
                    ++steps;
                }
                if (steps > max_steps)
                    max_steps = steps;
            }
            System.out.println(max_steps);
        }
    }
} 

I used the same algo in C++, and I got AC.

Could anyone help me on this?

Is java simply so much slower that I need to think of a clever algo?

Thx in adavance

[mikeboulos]

Here is my code, I have submitted it couple of times and still says Wrong answer, HELP PLEASE

#include <iostream>

using namespace std;

struct answers
{
int start,
end,
max;
struct answers * next;
};

void main()
{
int start, end, count, max;
struct answers * head = NULL;
struct answers * temp = NULL;

while ( cin >> start >> end )
{
max = 0;


for ( int i = start; i <= end; i++)
{
int n = i;
count = 0;

while (true)
{
count++;

if ( n == 1)
break;

if ( n%2 == 1)
n = n*3 +1;
else
n = n/2;
}
// Save answer
if ( count >= max)
{
max = count;

}
}
struct answers * node = new answers;

if ( head == NULL)
{
head = node;
node->next = NULL;
node->start = start;
node->end = end;
node->max = max;
temp = head;
}
else
{
temp->next = node;
node->next = NULL;
node->start = start;
node->end = end;
node->max = max;
temp = node;
}
}

cout.clear();
// Display Answer
temp = head;
while ( temp != NULL )
{
cout << temp->start << " " << temp->end << " " << temp->max << endl;
temp = temp->next;
}
while( head != NULL )
{
temp = head;
head = head->next;
delete temp;
}


}


Please reply soon

[chunyi81]

Next time, please see the sticky at the top of this forum before posting.

Mistake: start can be greater than end.

[kaw]

Yesterday, I have sent my program(Problem 100) and it got "Accepted".
But today I sent another program and got "Time Limit Exceeded".
I cannot the reason this program becomes "Time Limit Exceeded".
Please tell me what is wrong.

#include <cstdio>
#include <cstdlib>

#ifndef UINT
#define UINT unsigned int
#endif

//------------------------------------------------------------------------------
UINT CalcShusoku(UINT n)
{

register UINT res = 1,
i = n;
while (1 < i) {
if (i & 1)
i = i * 3 + 1;
else
i >>= 1;
res++;
}
return res;
}

//------------------------------------------------------------------------------
int main(int argc, char **argv)
{
register UINT org_begin, org_end,
plus,
i,
maximum;

while (scanf("%d %d\n", &org_begin, &org_end) == 2) {
register UINT begin = org_begin,
end = org_end;

plus = (begin <= end) * 2 - 1;

i = begin;
maximum = 0;
do {
register const UINT j = CalcShusoku(i);

if (maximum < j)
maximum = j;
i += plus;
} while (i != end);
printf("%d %d %d\n", org_begin, org_end, maximum);
}

return 0;
}


P.S. I am too bad for English. Please tell me by easly English

[Fadia Ismael]

Please, What is the error in this code?????????????????
C++

#include <iostream.h>
#include <stdlib.h>
void main(){
unsigned long int a, b, min, max, out=0;
cin>> a;
cin>> b;
if (a>b){
min=b;
max=a;
}
else{
min=a;
max=b;
}
if ( min<=0 || max>=1000000){
cout<<"Out of range"<<endl;
exit(1);}
for (unsigned long int j=min; min<=max; j++){
for (unsigned long int i=1; min!=1; i++){
if (min%2==0)
min=min/2;
else
min= 3*min + 1;
}
out= out>i? out : i;
min = j;
}
cout<<a<<" "<<b<<" "<<out<<endl;
}


and the question is problem 100..

[angga888]

Hi fadia ismael,

I guess the problem is with the scope of your variable

Code: Select all

for (unsigned long int i=1; min!=1; i++){ 
if (min%2==0) 
min=min/2; 
else 
min= 3*min + 1; 
} 
out= out>i? out : i; 

the variable 'i' is already out of scope when it is accessed by the line

Code: Select all

out= out>i? out : i;

Maybe you would move the variable 'i' declaration outside the loop

Code: Select all

unsigned long int i;
for (i=1; min!=1; i++){ 
if (min%2==0) 
min=min/2; 
else 
min= 3*min + 1; 
} 
out= out>i? out : i;

PS: Don't forget that the input can be more than one. You must read until EOF is encountered.

Good Luck!

[Fadia Ismael]

Thanks a lot, I've got it, but... why it give Accepted if I removed the word "unsigned" even it will not give an answer if we used large numbers??

[hacker]

I am getting the desired output for all the test-cases.
But it is not accepting my problem..

Code: Select all

#include<stdio.h>
int main()
{
	unsigned long int a,b,c,d, loopvar, cycle_length=1, max_cycle_length=1, i;

	clrscr();

	scanf("%ld",&a);
	scanf(" %ld",&b);

	printf("%ld %ld",a, b);

	if(a>b)
	{
		a=a+b;
		b=a-b;
		a=a-b;
	}

	loopvar = (b-a) + 1;
	c = a;
	d = a;

	for(i=1; i<=loopvar; i++)
	{

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

		if(cycle_length >= max_cycle_length)
		{
			max_cycle_length = cycle_length;
		}
		d++;
		c = d;
		cycle_length=1;
	}
	printf(" %ld",max_cycle_length);
    return 0;
}

}