100 - The 3n + 1 problem

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

TheLordFerada
New poster
Posts: 3
Joined: Wed Oct 19, 2005 2:56 pm

Post by TheLordFerada » Wed Oct 19, 2005 7:42 pm

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
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm

Post by tat tvam asi » Thu Oct 20, 2005 11:42 pm

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
"... Quod est inferius, est sicut quod est superius,
et quod est superius est sicut quod est inferius
ad perpetranda miracula rei unius ... "

TheLordFerada
New poster
Posts: 3
Joined: Wed Oct 19, 2005 2:56 pm

Post by TheLordFerada » Sat Oct 22, 2005 1:53 am

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
New poster
Posts: 5
Joined: Mon Oct 31, 2005 9:45 am

why i get runtime error?

Post by silvere » Mon Oct 31, 2005 9:52 am

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.
butterfly.

silvere
New poster
Posts: 5
Joined: Mon Oct 31, 2005 9:45 am

Post by silvere » Mon Oct 31, 2005 9:54 am

the input() function is of no use.

sorry for that.
butterfly.

silvere
New poster
Posts: 5
Joined: Mon Oct 31, 2005 9:45 am

problem 100:runtime error.

Post by silvere » Mon Oct 31, 2005 9:56 am

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.
butterfly.

silvere
New poster
Posts: 5
Joined: Mon Oct 31, 2005 9:45 am

Post by silvere » Mon Oct 31, 2005 9:57 am

the input() function is of no use.

sorry for that.
butterfly.

vacho
New poster
Posts: 3
Joined: Thu Nov 03, 2005 9:33 pm

3+1 Restricted Function

Post by vacho » Thu Nov 03, 2005 9:46 pm

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
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Thu Nov 03, 2005 10:40 pm

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!
Impossible is nothing

vacho
New poster
Posts: 3
Joined: Thu Nov 03, 2005 9:33 pm

Post by vacho » Fri Nov 04, 2005 7:23 am

Thanks:)

vacho
New poster
Posts: 3
Joined: Thu Nov 03, 2005 9:33 pm

Post by vacho » Fri Nov 04, 2005 10:11 am

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
New poster
Posts: 4
Joined: Fri Nov 04, 2005 5:12 pm

a problem with 3n+1

Post by chenhuansheng » Sat Nov 05, 2005 1:50 pm

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
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Re: a problem with 3n+1

Post by SRX » Sat Nov 05, 2005 1:56 pm

you have too many error in your code
Can your compiler compile it successfully ?
studying @ ntu csie

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: why i get runtime error?

Post by tan_Yui » Sat Nov 05, 2005 7:54 pm

silvere wrote: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
New poster
Posts: 4
Joined: Fri Nov 04, 2005 5:12 pm

....

Post by chenhuansheng » Sun Nov 06, 2005 7:54 am

My programme compile successfully in TURBOR C

Post Reply

Return to “Volume 1 (100-199)”