Page 60 of 93
(100)Sorry, can someone tell me where I did wrong
Posted: Thu Feb 08, 2007 2:26 pm
by jack1082
This is my code to problem 100, but I got a WA, can someone tell me where I did wrong?
#include<stdio.h>
#include<stdlib.h>
int main(void) {
int i,j,num,tmp,cycle,n=1;
scanf("%d %d",&i,&j);
if ((0<i<1000000) && (0<j<1000000)) {
int p=i>j?j:i;
int q=i<j?j:i;
for (num=p;num<=q;num++) {
tmp=num;
cycle=1;
while(tmp!=1) {
if (!(tmp%2)){tmp=tmp/2;}
else {tmp=tmp*3+1;}
cycle+=1;
}
n=n>=cycle?n:cycle;
}
printf("%d %d %d\n",i,j,n);
}
}
Posted: Thu Feb 08, 2007 2:43 pm
by helloneo
Posted: Thu Feb 08, 2007 4:35 pm
by jack1082
This is my code to problem 100, but I got a WA, can someone tell me where I did wrong? Thanks!
#include<stdio.h>
#include<stdlib.h>
int main(void) {
int i,j,num,tmp,cycle,n=1;
scanf("%d %d",&i,&j);
if ((0<i<1000000) && (0<j<1000000)) {
int p=i>j?j:i;
int q=i<j?j:i;
for (num=p;num<=q;num++) {
tmp=num;
cycle=1;
while(tmp!=1) {
if (!(tmp%2)){tmp=tmp/2;}
else {tmp=tmp*3+1;}
cycle+=1;
}
n=n>=cycle?n:cycle;
}
printf("%d %d %d\n",i,j,n);
}
}
Posted: Sat Feb 10, 2007 1:58 pm
by newton
What is #100 problem ending input condition ?
Posted: Sun Feb 11, 2007 6:42 pm
by arakdev
I have solved it and got correct answers , but how much ases it should process and read, the termination condition wasn't mentioned in the problem. If we want to get all inputs at a time , how we undrestand the end of input ?
Posted: Sun Feb 11, 2007 6:54 pm
by helloneo
wondering about other people's code runtimes
Posted: Wed Feb 14, 2007 11:52 am
by rich_correia
Hi
I just started solving a couple problems today. As I was wondering about the site I noticed that, while my runtime to problem 100, (the 3n+1 thing), was something relatively lengthy other people had runtimes of 0 and 0.001, something like that, very fast.
Do they write parts of the code in assembler? What gives?
Rich
Posted: Wed Feb 14, 2007 12:05 pm
by rio
pre-calculate teq, and fast i/o.
Posted: Wed Feb 14, 2007 12:06 pm
by rich_correia
sorry dude, what does precalculated teq mean?
Posted: Sat Feb 17, 2007 7:57 am
by Debashis Maitra
precalculated teq means precalculated output
Posted: Mon Feb 19, 2007 7:30 am
by newton
it takes about 4.017 sec to exicute the programe in OJ.
it is so much, how can i minimize my time limit?
any new algorithm?
plz help me.
Code: Select all
#include <stdio.h>
int main(void)
{
long i,j,m,temp,total,max;
while(scanf("%ld %ld",&i,&j)==2)
{
printf("%ld %ld ",i,j);
max=0;
if(i>j)
{
temp=i;
i=j;
j=temp;
}
for(m=i;m<=j;m++)
{
temp=m;
total=0;
while(1)
{
if(temp==1 && temp)
{
total++;
break;
}
total++;
if(temp % 2 == 0)
temp/=2;
else
temp=( 3 * temp + 1 );
}
if(total>max)
max=total;
}
printf("%ld\n",max);
}
return 0;
}
Posted: Mon Feb 19, 2007 12:34 pm
by shamim
You could use precalculation and memoization.
That is, precalculate all the values first. Now, when finding the cycle length for 32 you need to find that of 16. So, there is no need to calculate the cycle length of 16 twice.
Posted: Thu Feb 22, 2007 2:53 am
by Roby
AND print the formatted output directly
But I a little bit curious about the fast I/O... I always use gets to make my solution faster... but it was "less" faster than I thought... So, can someone give me an example how to make fast I/O parser? Thanks.
Posted: Thu Feb 22, 2007 6:28 am
by Vexorian
In a less esoteric way of doing things, 100 has a fast solution in which you keep an array as a table for solutions you got already. For example f(15) requires your to solve f(46) so if you later go through f(46) you don't have to calculate f(46) again since the program 'remembers' the solution for it.
A good thing to do is to solve
http://acm.uva.es/problemset/v3/371.html after solving 100 and notice the differences.
help!!
Posted: Tue Feb 27, 2007 1:43 am
by statefull
Hi all!
Judge don't want accept my program
always WA.... The examples in page works fine
Somebody that resolved the problem could put some example with the solutions
thanks
EDIT:
OK i obtein accepted jeje I put examples:
INPUT
1 1
1 2
1 3
1 4
100 500
1 10000
3432 2991
2391 2931
787843 100
OUTPUT
1 1 1
1 2 2
1 3 8
1 4 8
100 500 144
1 10000 262
3432 2991 199
2391 2931 217
787843 100 509
regards
