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

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

Post by richardxx » Fri Oct 20, 2006 5:59 pm

No one can answer that?

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

pankaj trivedi
New poster
Posts: 11
Joined: Wed Jun 21, 2006 5:11 pm
Contact:

Post by pankaj trivedi » Fri Oct 20, 2006 9:41 pm

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:

Problem #100 3n+1 Problem Wrong Answer-> please Help

Post by happyboyz » Wed Oct 25, 2006 7:11 am

#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.
please understand me.
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

Post by genti » Sat Oct 28, 2006 2:27 pm

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.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Oct 28, 2006 2:38 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

Post by genti » Sat Oct 28, 2006 3:25 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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sat Oct 28, 2006 7:49 pm

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

Post by helloneo » Mon Oct 30, 2006 8:07 am


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

Thxs for suggesting..

Post by nnahata » Tue Oct 31, 2006 6:11 pm

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

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

RTE 100

Post by chaturvedi » Fri Nov 03, 2006 8:07 pm

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;
}

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sat Nov 04, 2006 9:32 am

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

Post by Lingyis » Sat Nov 18, 2006 8:52 am

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

Post by Lingyis » Sat Nov 18, 2006 10:28 am

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

Post by popinc » Mon Nov 27, 2006 9:39 pm

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Nov 27, 2006 9:51 pm

Dont open a new thread if there is one already. About reducing time - you can store suppose 100000 values, and while calculating, if 'n' is less than or equal to this value, then you can use the value from the stored table.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 1 (100-199)”