## 100 - The 3n + 1 problem

Moderator: Board moderators

richardxx
New poster
Posts: 3
Joined: Fri Oct 20, 2006 7:51 am

OK, any guy willing to share your code?
Thx.

pankaj trivedi
New poster
Posts: 11
Joined: Wed Jun 21, 2006 5:11 pm
Contact:
Dont create new thread for the existing ones. Your problem has been discussed in the existing thread. anyways you need to print the output in the order it is given in input
Anything other than Accepted is irritating,even Presentation Error

http://acm.uva.es/problemset/usersjudge.php?user=40301

happyboyz
New poster
Posts: 1
Joined: Wed Oct 25, 2006 4:54 am
Location: Korea, of Republic
Contact:

#include<stdio.h>

void swap(int *p, int *q);

int calculation(int n);
int main(void)
{
int i, j, n, start, end;
int count, maximum = 0;

scanf("%d", &i);
scanf("%d", &j);

start = i;
end = j;

if(i > j)
{
swap(&i, &j);
}

n = i+1;

while(i <= n && n <= j)
{
count = calculation(n);

n++;

if(maximum < count)
maximum = count;
}

printf("%d %d %d", start, end, maximum);

return 0;
}

void swap(int *p, int *q)
{
int tmp;

tmp = *p;
*p = *q;
*q = tmp;
}

int calculation(int n)
{
int cnt = 1;

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

++cnt;
}

return cnt;
}[/b]

what is it wrong above source code??
I'm Korean.
I can't speak English.
I don't know that what is wrong abvove source code.
Input same SampleInput and Output same SampleOutput.
please teach me what is wrong abvove source code. [/b]

genti
New poster
Posts: 5
Joined: Sat Oct 28, 2006 2:24 pm

### Problem 100 WA

Why do I get a WA from the Compiler??? I've tried it, works everything fine, the results I get from my computer coincide with those of the output example. Any help or suggestion would be highly appreciated.
Thanks

Problem solved
Last edited by genti on Sun Oct 29, 2006 8:57 am, edited 2 times in total.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Did you read the umpty or so messages on this problem? The mistake you made must have been posted and answered at least a hunded times by now. Read the output secification carefully.

genti
New poster
Posts: 5
Joined: Sat Oct 28, 2006 2:24 pm
I made the necessary corrections so that the output order of i and j matches the input order, but I'm still getting WA. Reading other posts hasn't helped much.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Input will be terminated by EOF. So, use

Code: Select all

``while(scanf("%lu %lu",&i,&j)==2)``
And make sure that your code handles multiple cases correctly.
Ami ekhono shopno dekhi...
HomePage

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

nnahata
New poster
Posts: 6
Joined: Fri Sep 08, 2006 9:01 pm
Location: india
Contact:

### Thxs for suggesting..

Thxs pankaj......now i got mistake...

chaturvedi
New poster
Posts: 8
Joined: Mon Jul 10, 2006 9:31 am

### RTE 100

I am new to online judge.. Can anybody tell me when is generally input terminated, see in problems like Australian Voting the no. of people voting is not specified so I donot know how is the input terminated... I tried to use blank line to terminate the input in 3n+1 problem and it didnt work... I had solved the problem before by using the statement while(scanf("%d",&k)==1) for terminating the input... since I wanted to test whether the blank line thing works or not I tried it with 3n+1... It didnt work I got TLE....Heres my code.... the algo is correct as I have got it AC please check for the input procedure is correct or not...

#include <stdio.h>
#include <string.h>
void swap(unsigned long int *a,unsigned long int *b);

int senti=0;
int input(char *,char *);
int main()
{
unsigned long int j;
unsigned short int count;
unsigned long int k,l,m,temp;
char ch,ch1;int temp1,temp2;
char xy[100],yz[100];
int g;
while(1)
{

m=0;
senti=0;

g=input(xy,yz);

k=atol(xy);
l=atol(yz);

if (g==1)
return 0;

if(k>l)
swap(&l,&k);

if(k!=0)
{
for(j=k;j<=l;j++)
{
temp=j;
count=1;
if((2*j)>l){
while(temp!=1)
{
if((temp%2)==1)
temp=temp*3+1;
else
temp=temp/2;
count++;
}
}
if(m<count)
m=count;
}
}
if(senti==1)
swap(&l,&k);

if(k!=0 && l!=0)
printf("%li %li %li\n",k,l,m);

}

return 0;
}

void swap(unsigned long int *a,unsigned long int *b)
{
int hold=*a;
*a=*b;
*b=hold;
senti=1;
}

int input(char *x ,char *y)
{
char str[200];
int a;

char *temp;

gets(str);
temp=str;

for(a=0;str[a]==' ';a++);
temp=temp+a;

strcpy(str,temp);

if(strcmp(str,"")==0)
return 1;

for(a=0;str[a]!='\0';a++)
{
if(str[a]==' ')
{
strncpy(x,str,a);
x[a]='\0';

temp=str;

while(str[a+1]==' ')
a++;

temp=temp+a+1;
break;
}
}

for(a=0;temp[a]!=' ';a++);
temp[a]='\0';

strcpy(y,temp);
return 0;
}

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Most recent problems usually state the number of cases at the begining.

And for problems like 3*n+1, you have to test for the end of file condition which is usually done by

Code: Select all

``while ( scanf("%d %d",&a,&b) == 2 )``
, for this problem.

And there are many problems, deciding the number of input in a line or number of lines in a set of input must be determined.

for the first case, the function strtok() is useful and for the second case, sets are seperated by a blank line, so you must use gets to take a line of input and then determine if its blank or not.

And for this prob, there is no need to take input as char* first as

Code: Select all

``scanf("%d %d")``
will do the job.

Lingyis
New poster
Posts: 4
Joined: Sat Nov 18, 2006 8:41 am

### performance

On page 2 some people discussed the performance of some of the submissions takes 0.00 CPU seconds to run... using a precalculated table would indeed be very fast, but how then does the program take up only 64K of memory? (memory information is also displayed)

A 1,000,000 length int (or short, for that matter) array clearly takes up a lot more than 64k.

How it can be done?

For now, I'll have to assume they just keep resubmitting and making their precalculated array smaller and smaller until the they find the minimum number that the robot judge would accept their solution.

Lingyis
New poster
Posts: 4
Joined: Sat Nov 18, 2006 8:41 am

### performance

So I submitted one that uses a 1,000,000 sized array, calculations are done on the fly, i.e. no pre-caculations.

That finished running in 0.104s, a huge improvement from the previous naive straighforward no-tabulation implementation, which took 2.56s to run.

But it also took up 2344 kB.

But I would really appreciate if someone could point out how one can get it to under 0.02s using just 64 kB! Thanks in advance.

popinc
New poster
Posts: 2
Joined: Thu Nov 23, 2006 11:18 pm

### 100 runtime & mem usage

Can someone please shed some light on how to achieve good runtime and memory usage performance for problem 100, especially runtime?

There are a lot of gurus whose algorithms only cost less than 5ms, but my algorithm costs about 1s. I wonder how did they achieve this performance.

Thanks a lot

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm