100 - The 3n + 1 problem

[emotional blind]

Again SiLwS,

This is not the first thread of 100.
Look at the top of vol 1
There is a big thread having more than 140 posts,
and it is strictly asked

Code: Select all

If you get WA in problem 100, read me before post!

But i think not only WA any kind of problem about 100,
it can help

good luck

[klam]

im sorry but this thread is really long and i think it should get ride of post that really dont matter. It's extremely cumbersome going one by one to find if the question has been resolved or not.

I got WA for a program and im still confuse as to how the judge actually goes throu it, is it:

input
output
input
output

or

input
input
output
output

yes, yes it has been discussed but there's always people that says the first one others say the second one, does anyone really have a real answer?.... and how about the end of line? if you're running a program for this last case it's really possible to get an endl after the last output... if that's counted as WA then............. *sighs*

[mf]

I got WA for a program and im still confuse as to how the judge actually goes throu it, is it:

input
output
input
output

or

input
input
output
output

What do you mean by this?
There's exactly one input file, which your program reads on the standard input. After your program terminates, all the output it made to the standard output will be compared with expected output file. If they are the same, you'll get AC. That's all there is about testing.

[klam]

I got WA for a program and im still confuse as to how the judge actually goes throu it, is it:

input
output
input
output

or

input
input
output
output

What do you mean by this?
There's exactly one input file, which your program reads on the standard input. After your program terminates, all the output it made to the standard output will be compared with expected output file. If they are the same, you'll get AC. That's all there is about testing.

well I know what a judge does, maybe i didnt express myself correctly?
according to you the program has to read all lines before making any output? if this is the case, then each answer (which is generally one per line) has to be store in some place until all lines of input are read and then you put all your stored output.

I could've swore I read someone saying you read one line then you output the result, then you read the next line and output the next result and so on... which would make more sense to me.

EDITED: I just found out, for those of you still wondering the answer is actually alternated with the input.

[mf]

It doesn't matter to the judge, whether you read all the test cases before any processing, or solve case by case.
The latter is better, because it needs less memory. (the memory is, you know, limited; 32 Mb by default)

[MrRusof]

I think this is just fine, but judge says WA, are there any test cases available? What is the problem?

Code: Select all

class Main
{	

	///Punto de entrada del programa...
	public static void main(String args[])
	{	
		long a;
		long i, j, x;
		int y, secuenciaMayor;
		String sin, sout = "";
		boolean primero = true;
		while(true)
		{
			sin = leerLinea();
			
			if(sin == null || sin.length() == 0 || sin == "")
				break;
		/*	else if(!primero)
				///sout += "\n";
				System.out.println();
			else if(primero)
				primero = false;
		*/	
			i = Integer.parseInt(sin.substring(0, sin.indexOf(' ')));
			j = Integer.parseInt(sin.substring(sin.indexOf(' ') + 1));	
		
	///		sout += (i + " " + j + " ");
			
			System.out.print(i + "  " + j + "  ");
			
			x = min(i,j);
			j = max(i,j);
			secuenciaMayor = 0;
		
	///		sout += (x + "  " + j + "  ");
		
			///Collatz para todos los n

[tmdrbs6584]

the input can be,

Code: Select all

10 1

[clearls]

I don't understand why it's telling wrong answer when i m submitting can anyone help me please ??????
here is the whole program :

#include <cstdio>
#include <iostream>
using namespace std;
unsigned long * temp;
unsigned long i,j,hindex,hvalue;
unsigned long no_Zero;
unsigned long result(unsigned long n)
{
unsigned long count=1;
unsigned long t=n;
while(n!=1)
{
// cout <<n<< " ";
if(n%2==1)
{
n=3*n+1;
}
else
{
n=n/2;
}

// cout << n <<"_";
if(n < j and n >= i)
{
if(temp[n-i] == 0)
{
no_Zero=no_Zero-1;
temp[n-i]=1;
}

}
count++;
}
if(count > hvalue)
{
hindex=t;
hvalue=count;
}

if(temp[t-i] == 0)
{
no_Zero=no_Zero-1;
temp[t-i]=count;
}

return count;
}
unsigned long no_of_zeros()
{
/* unsigned long count=1;
for(unsigned long k=0;k<=j-i;k++)
{
if(temp[k]==0)
{
count=count+1;
}
}
count=count-1;
return count;*/
return no_Zero;
}
void output(void)
{
unsigned long mem=j-i+1;
unsigned long counter=j-i;
temp = new unsigned long[mem];
no_Zero=mem;
hindex=0;
hvalue=0;
for(unsigned long k=0;k<=(j-i);k++)
{
temp[k]=0;
}
while(no_of_zeros() > 0 || counter==0 )
{
// cout <<"No of zeros " <<no_of_zeros() << " " << "Next zero "<<next_zero() <<" " ;
if(temp[counter]==0)
result(counter+i);
counter--;
}
if(i < j)
{
cout << i <<" "<< j <<" "<< hvalue ;
}
else
{
cout << j <<" "<< i <<" "<< hvalue ;
}
}

int main(int argc , char ** argv)
{
unsigned long swp=0;
while(scanf("%ld%ld",&i,&j)!=EOF)
{
if(i > j)
{
swp=i;
i=j;
j=swp;
}
output();
cout << endl;
}
return 0;
}

[chunyi81]

Try this input:

10 1

Correct output is:

10 1 20

You are printing i and j after you have swapped the values in i and j, but you are supposed to print the values of i and j in the order given in the input.

Code I am referring to:

Code: Select all

void output(void) 
{ 
unsigned long mem=j-i+1; 
unsigned long counter=j-i; 
temp = new unsigned long[mem]; 
no_Zero=mem; 
hindex=0; 
hvalue=0; 
for(unsigned long k=0;k<=(j-i);k++) 
{ 
temp[k]=0; 
} 
while(no_of_zeros() > 0 || counter==0 ) 
{ 
// cout <<"No of zeros " <<no_of_zeros() << " " << "Next zero "<<next_zero() <<" " ; 
if(temp[counter]==0) 
result(counter+i); 
counter--; 
} 
if(i < j) 
{ 
cout << i <<" "<< j <<" "<< hvalue ; 
} 
else 
{ 
cout << j <<" "<< i <<" "<< hvalue ; 
} 
} 

int main(int argc , char ** argv) 
{ 
unsigned long swp=0; 
while(scanf("%ld%ld",&i,&j)!=EOF) 
{ 
if(i > j) 
{ 
swp=i; 
i=j; 
j=swp; 
} 
output(); 
cout << endl; 
} 
return 0; 
}

You call output function after you swap i and j which prints i and j. For the input I gave above your code will print 1 10 20 which is wrong.

Next time use code tags to make your code more readable.

[clearls]

Thank a lot !!
for ur valuble suggestion

Me gratefull to u !!

[msq]

Code: Select all

#include <iostream>

using namespace std;

void swap (unsigned long &a, unsigned long &b) {
	unsigned long temp;
	temp = a;
	a = b;
	b = temp;
}

unsigned long cycle_length (unsigned long n) {
	unsigned long length=1;
	do {
		length++;
		if (n%2!=0)
			n = 3*n+1;
		else
			n /= 2;
	} while (n!=1);
	return length;
}

unsigned long max_length(unsigned long a, unsigned long b) {
	unsigned long i,maxlength=0;
	for (i=a;i<=b;i++) {
		if (cycle_length(i)>maxlength)
			maxlength=cycle_length(i);
	}
	return maxlength;
}

int main () {
	unsigned long i,j;
	while (cin >> i >> j) {
		cout << i << " " << j << " ";
		if (i>j)
			swap (i,j);
		cout << max_length(i,j) << endl;
	}
	return 0;
}

I can't figure out what's wrong with my code :|
I am swapping vars... I output them in correct way... :/

[emotional blind]

input:
1 1
output:
1 1 1

[Aaron Zapashniy]

I'm newbie here and have to introduce myself. My name is Alex, 28 y.o. from Hungary. I have been looking for such kind of forum for a long time and at least I'm here. Hope that I'll become a member of this community and finally get the answers on all my questions, and may be my experience will be useful for all the ppl around. My Geek code QA7fMi9imv2udB.

[msq]

thx emotional blind...
Ii still don't know why I usen do while instead of while do. Anyway my prog is accepted. It runs for 3.6s so now I will try to speed it up

[webgoudarzi]

Ive tried my hardest to make this code perfect and yet i still get that it gives me a wrong answer.

Please... Im going to explode if someone doesnt help me. My rating here is probably already horrible because of 6 wrong answers...GRRR

Code: Select all

#include <iostream>
using namespace std;

class MaxCycle
{
public:
	int getMax(long i, long j);

private:
	long j;
	long i;

};

int MaxCycle::getMax(long i, long j)
{
	long long temp = 0;
	long long max = 0;
	long long count = 1;
	if ( i > j )
	{
		temp = i;
		i = j;
		j = temp;
	}
	for (int min = i; min <= j; min++)
	{
		count = 1;
		long long answer = min;

		do
		{
			if ( answer == 1 )
			{
				continue;
			}

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

			count++;

		} 

		while ( answer != 1);



		if ( count > max )
		{
			max = count;
		}
	}

	return max;
}




int main ()
{
	int firstNumber;
	int secondNumber;

	cin >> firstNumber;
	cin >> secondNumber;

	MaxCycle M1;
	int result = M1.getMax(firstNumber,secondNumber);

	cout << firstNumber;
	cout << " ";
	cout << secondNumber;
	cout << " ";
	cout << result;
	cout << "\n";
	return 0;
}