100 - The 3n + 1 problem

[chunyi81]

Try this input:

1 3

You code gives:

1 3 2

But the correct output should be

1 3 8

[patrickriva]

Thank you very much I'll have a look at it!

Cheers

[Artikali]

i solve this problem, judge accepted
but if i enter from 1 to 1000000 result will be after 2-3 minutes
has every one solve this problem which results will be in 1-2 seconds
for long intervals

[Martin Macko]

i solve this problem, judge accepted
but if i enter from 1 to 1000000 result will be after 2-3 minutes
has every one solve this problem which results will be in 1-2 seconds
for long intervals

Read threads on this problem in the Volume I forum.

[mbd01]

Hi, I am absolutely new here. I wrote a program for problem#100 and the error message is "Wrong Answer"
The program is here........

#include<stdio.h>
main()
{
long int n,x,y;
int i,max;

while(fscanf(stdin,"%ld%ld",&x,&y)!=EOF)
{
printf("%ld %ld ",x,y);
if(y<x) { n=x;x=y;y=n;}
max=0;
for(;x<=y;x++)
{

n=x;
i=1;
do{
// printf("%ld ",n);
if(n%2==0)
n=n/2;
else
n=3*n+1;
i=i+1;
}while(n!=1);

if(max<i) max=i;

}
printf("%d\n",max);
}
}

Can anyone tell me for which input the answer is wrong?

[Dominik Michniewski]

Search on board and first read other threads connected with problem 100, and after that post new one.

Best regards
DM

[WDWD]

Hi

I have some problems with handling the input in 100. I dont know how or in which format I will receive it...
I use C++.

Thanks

[Martin Macko]

Hi

I have some problems with handling the input in 100. I dont know how or in which format I will receive it...
I use C++.

Thanks

There are two numbers (i and j) on each line in the input, which is terminated by EOF.
You can write something like this:

Code: Select all

int i, j;
while (cin>>i>>j) cout<<i<<" "<<j<<" "<<solve(i,j)<<endl;
return 0;

But mind that cin>> and cout<< are rather slow...

[Kamik]

hello, can anyone help me?
i got WA, but i tested with multiple inputs, i dont know why dont accept.

Code: Select all

#include <iostream>
#include <sstream>
#include <string>

int main(int argc, char *argv[])
{
	unsigned long int aux, aux2, inicio, fim, o_inicio, o_fim;
	char linha[20];
	int maximo, atual;
	std::istringstream *buffer;
	
	do
	{
		std::cin.getline(linha, 19);
		if(strcmp(linha,"") != 0)
		{
			buffer = new std::istringstream;
			buffer->str(linha);
			*buffer >> o_inicio >> o_fim;

			if(o_inicio > o_fim)
			{
				inicio = o_fim;
				fim = o_inicio;
			}
			else
			{
				inicio = o_inicio;
				fim = o_fim;
			}
			maximo = 0;
			for(aux = inicio; aux <= fim; aux++)
			{
				atual = 1;
				aux2 = aux;
				if(aux * 2 <= fim)
					continue;
				while(aux2 != 1)
				{
					if(aux2 % 2 != 0)
						aux2 = 3 * aux2 + 1;
					else
						aux2 = aux2 / 2;
					atual++;
				}
				if(atual > maximo)
					maximo = atual;
			}
			delete buffer;
			std::cout << o_inicio << " " << o_fim << " " << maximo << "\n";
		}
	} while(strcmp(linha,"") != 0);
	return 0;
}

[CGR]

This pb is driven me crazy..
WA, and I don't know why. I read all the topics but didn't find anything..

For this input :

1 1
1 2
2 1
3 3
3627 5749

I obtain :

1 1 1
1 2 2
2 1 2
3 3 8
3627 5749 238

This is my code :

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

class Main {

public static void main(String[] args) {

StringTokenizer st;
String s;
int i,j;

while ((s = readLn(50).trim()) != null) {
st= new StringTokenizer(s);
i= Integer.parseInt(st.nextToken());
j= Integer.parseInt(st.nextToken());
System.out.println(i+" "+j+" "+maiorCompCiclo(i,j));
}
}

static int compCiclo (int n) {
int cont = 1;

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

return cont;
}

static int maiorCompCiclo(int i, int j) {
int max=0, comp, menor, maior;

if (i<j) {menor=i; maior=j;}
else {menor=j; maior=i;}

for (int k=menor;k<maior+1;k++) {
comp = compCiclo(k);
if (comp>max) max = comp;
}

return max;
}

static String readLn (int maxLg) { ... }
}


Can anyone help me ?

[tan_Yui]

Hi, CGR.
Could you write your code fully?
Although I cannot satisfactorily read the Java code, I can check by using i/o with my Accepted code.

static String readLn (int maxLg) { ... }

Best regards.

[CGR]

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

class Main {

public static void main(String[] args) {

StringTokenizer st;
String s;
int i,j;

while ((s = readLn(100).trim()) != null) {
st= new StringTokenizer(s);
i= Integer.parseInt(st.nextToken());
j= Integer.parseInt(st.nextToken());
System.out.println(i+" "+j+" "+maiorCompCiclo(i,j));
}
}

static int compCiclo (int n) {
int cont = 1;

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

return cont;
}

static int maiorCompCiclo(int i, int j) {
int max=0, comp, menor, maior;

if (i<j) {menor=i; maior=j;}
else {menor=j; maior=i;}

for (int k=menor;k<maior+1;k++) {
comp = compCiclo(k);
if (comp>max) max = comp;
}

return max;
}

static String readLn (int maxLg) {

byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

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

if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg-1));
}
}

[tan_Yui]

I executed your code by using the I/O which I prepared.
Your code outputs incorrect answer for them.
Following is the I/O.
By the way, it should be efficient code because the limit of input number is huge, 1 million.
Brute force method will cause TimeLimitExceeded.

Input :

1 10
100 200
201 210
900 1000
1 999999
837799 837799
837800 999999
511936 837798
96 97
96 98
97 97
97 98
5000 500
312 232
13255 3711
200000 100000
1 1
2 2
2 3

Output should be :

1 10 20
100 200 125
201 210 89
900 1000 174
1 999999 525
837799 837799 525
837800 999999 476
511936 837798 468
96 97 119
96 98 119
97 97 119
97 98 119
5000 500 238
312 232 128
13255 3711 276
200000 100000 383
1 1 1
2 2 2
2 3 8

Best regards.

[TheLordFerada]

Hiho

I've got a compile error with the code at http://home.arcor.de/thelordferada/v1_100.c, but it compiles without any errors at my pc (gcc 3.3.3, athlon 1600+); can you help me

also is there a possibility to get the error-messages from the compiler after submission ?

thx TLF[/url]

[shamim]

you could get the compile error message from the compiler by maill, if you enabled that option, when registering.