100 - The 3n + 1 problem

[TheLordFerada]

well, thanks, but actually the button for updating is not available in the moment?!

is there another possibility to update the settings?

TLF

[tat tvam asi]

Hi,
it compiles fine at uva, got tle instead:
4053997 2005-10-20 21:37:53 Time Limit Exceeded 10.031 384 18742 C 100 - The 3n + 1 problem
peace, csn

[TheLordFerada]

Hi,
it compiles fine at uva, got tle instead:
4053997 2005-10-20 21:37:53 Time Limit Exceeded 10.031 384 18742 C 100 - The 3n + 1 problem
peace, csn

i don't suppose you have an idea whats the reason for that?
because it runs only around 9ms/40ms on my pc

TLF

[silvere]

compile and run ok with gcc under linux.

but when i submit my code,runtime error!

why?

thx.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define MAXNUMBER 1000000

int input(int *a,int *b)
{
	*a=0;
	*b=0;
	scanf("%d %d",a,b);
	if(*a<=0 || *b<=0)
	{
		return 0;
	}
	return 1;
}

int cycle_length(int i)
{
	int count=1;
	while(i!=1)
	{
		count++;
		if(i%2==0)
			i=i/2;
		else if(i%2==1)
			i=3*i+1;
		else
		{
			printf("error!");
			exit(0);
		}
	}
	return count;
}

int max(int *rh,int index)
{
	int i;
	for(i=0;i<=index;i++)
	{
		if(rh[i]>rh[i+1])
			rh[i+1]=rh[i];
	}
	return rh[index];
}


int main()
{
	int i,a,b;
	int j[MAXNUMBER];
	while(scanf("%d %d",&a,&b) == 2)
	{
		for(i=a;i<=b;i++)
		{
			j[i-a]=cycle_length(i);
		}
		printf("%d %d %d\n",a,b,max(j,b-a));
	}
	return 0;
}

maybe,the filename is *.cpp,but in fact i uses stdio.h header files belonging to c.

thx.

[silvere]

the input() function is of no use.

sorry for that.

[silvere]

compile and run ok with gcc under linux.

but when i submit my code,runtime error!

why?

thx.

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#define MAXNUMBER 1000000

int input(int *a,int *b)
{
	*a=0;
	*b=0;
	scanf("%d %d",a,b);
	if(*a<=0 || *b<=0)
	{
		return 0;
	}
	return 1;
}

int cycle_length(int i)
{
	int count=1;
	while(i!=1)
	{
		count++;
		if(i%2==0)
			i=i/2;
		else if(i%2==1)
			i=3*i+1;
		else
		{
			printf("error!");
			exit(0);
		}
	}
	return count;
}

int max(int *rh,int index)
{
	int i;
	for(i=0;i<=index;i++)
	{
		if(rh[i]>rh[i+1])
			rh[i+1]=rh[i];
	}
	return rh[index];
}


int main()
{
	int i,a,b;
	int j[MAXNUMBER];
	while(scanf("%d %d",&a,&b) == 2)
	{
		for(i=a;i<=b;i++)
		{
			j[i-a]=cycle_length(i);
		}
		printf("%d %d %d\n",a,b,max(j,b-a));
	}
	return 0;
}

maybe,the filename is *.cpp,but in fact i uses stdio.h header files belonging to c.


thx.

[silvere]

the input() function is of no use.

sorry for that.

[vacho]

When I submit the code I get reply - resticted function:( Can anyone tell me what does it mean?

here is the code

#include<fstream>

using namespace std;

int main(){
unsigned int n=0,m=0;

ifstream input("input.txt");
ofstream output("output.txt");


while(input >> n >> m ){
if(n>m){
unsigned int temp = n;
n=m;
m=temp;}

int max = 0;

for (unsigned int i = n; i <= m ; i++) {
int count = 1;
int num = i;

while( num > 1)
{
if(num % 2 == 1) num = 3 * num + 1;
else num = num / 2;
count++;

}
if(count > max)
max = count;

output << n << " "<< m << " "<< max << endl;
}
return 0;

}

[tywok]

On this online judge you are not allowed to use any function that opens a file. Every kind of input/output must go through the normal stdin. In your case you should just include iostream and change the "input"s for "cin"s and the "output"s for "cout"s and of course erase the lines

Code: Select all

ifstream input("input.txt");
ofstream output("output.txt"); 

I hope you understood!
Welcome on board!

[vacho]

Thanks:)

[vacho]

Ok I changed the output then what is the problem now?I get WA

here:

#include <iostream>
#include <vector>
using namespace std;

int main(){
unsigned int n=0,m=0;
int max=0;
vector<unsigned int> vec;

while(cin >> n >> m) {
if(n>m){
unsigned int temp=n;
n=m;
m=temp;
}
vec.push_back(n);
vec.push_back(m);
max = 0;
for (unsigned int i = n; i <= m ; i++) {

int count = 1;
int num = i;

while( num > 1)
{
if(num % 2 == 1) num = 3 * num + 1;
else num = num / 2;
count++;

}
if(count > max)
max = count;
}
vec.push_back(max);
}

for(int i = 0; i < vec.size() - 2; i += 3)
cout << vec << " " << vec[i + 1] << " " << vec[i + 2] << endl;
return 0;
}

[chenhuansheng]

When I submit the code I get reply - complie error
Here is my code.

#include <stdio.h>
#include <stdlib.h>

int input(char *, int, int ,int);
unsigned long three_plus(unsigned long, unsigned long);

main()
{
int i = 0, x, y;
char a[10];
unsigned long *p = NULL, n, m;
clrscr();
printf("input the integers end of 'enter':\n");
while (1)
{
x = wherex();
y = wherey();
if (input(a, 10, x, y) == -1)
break;
m = atol(a);
if (m<0 || m>1000000)
{
printf("input error.\n");
continue;
}
gotoxy(strlen(a)+2, y);
input(a, 10, x+strlen(a)+1, y);
n = atol(a);
p = (long *)realloc(p, 2*(++i)*sizeof(long));
p[2*(i-1)] = m;
p[2*(i-1)+1] = n;
printf("\n");
}
for (; i!=0; i--, p=p+2)
{
printf("%ld %ld %ld\n", p[0], p[1], three_plus(p[0], p[1]));
}
}

unsigned long three_plus(unsigned long m, unsigned long n)
{
unsigned long i, j, k, max, len=1;
if (m < n)
{
i = m;
max = n;
}
else
{
i = n;
max = m;
}
for (; i<=max; i++)
{
j = i;
k = 1;
while (1)
{
if (j == 1)
break;
else if (j%2 == 0)
j /= 2;
else
j = 3*j+1;
k++;
}

if (k > len)
len = k;
}
return len;
}

int input(char *name, int n, int x0, int y0)
{
int i, x, y;
char a, buf[1*1*2];
gettext(x0, y0, x0, y0, buf);
for (i=0; i<n-1; i++)
{
x = wherex();
y = wherey();
if ((a=getche()) == '\r') /*如果是ENTET, 则输入结束*/
break;
else if (a == '\b')
{
if (i == 0) /*开始时光标不回退*/
{
gotoxy(x, y);
i -= 1;
puttext(x-1, y, x-1, y, buf);
continue;
}
puttext(x-1, y, x-1, y, buf);
i -= 2; /*光标回退*/
continue;
}
name = a;
}
name = '\0';
if (i == 0)
return -1; /*没有输入则返回-1*/
else
return 0; /*有输入返回0*/
}

[SRX]

you have too many error in your code
Can your compiler compile it successfully ?

[tan_Yui]

compile and run ok with gcc under linux.

but when i submit my code,runtime error!

why?

thx.

Although I can't find the concrete causes of RE, I found one mistake.
Your code uses the variable a & b as a<=b, but this problem doesn't say such condition.
Such input (a>b) will exist.
If your code meet such input, the code will do illegal process.

Best regards.

[chenhuansheng]

My programme compile successfully in TURBOR C