Page 1 of 2
11113 - Continuous Fractions
Posted: Tue Oct 10, 2006 3:43 am
by Tariq Shahriar
For this problem, I used
Posted: Tue Oct 10, 2006 5:54 am
by Pregunt
Maybe you forgot to write "p / q" after "Case n:", i. e.
Case 1:
75 / 34
..........1......
2.+.-------------
............1....
....4.+.---------
..............1..
........1.+.-----
................1
............5.+.-
................1
Posted: Wed Oct 11, 2006 5:31 am
by Tariq Shahriar
Wow! though this is a big mistake, but not all.
the highest input is less than 10^20 i.e 99,999,999,999,999,999,999 [20 digit]. but unsigned long long can hold only
(2^64)-1=18446744073709551615 [20 digit]. but less than the 81553255926290448384 from the highest input. so, if the input is
99999999999999999999 99999999999999999998
then what will i do?
Posted: Wed Oct 11, 2006 8:29 am
by sohel
Fortunately ( or unfortunately ) long long will suffice.
In the real time contest, I initially thought, one has to use big int division to solve the problem..
.. but later seeing many ACs, i used assert() to investigate the input size.
And found out that long long is enough.
This contest had some faulty input size and unmentioned range..
.. but the set was very good.
Posted: Wed Oct 11, 2006 9:08 am
by Tariq Shahriar
Sohel vai (Bengali word), Thanks for your kind information.
But, is my continuous fraction output of the input correct? Will you post your output?
Posted: Thu Oct 12, 2006 6:13 am
by Vexorian
yes, considering you are showing p / q then your output is correct.
Coincidentally, none of those cases includes a fraction bar of an even length. And that's the only catch I can think this problem had. So I can suggest you to make sure it is going to work:
The statement says how to handle them:
The number on a fraction numerator must be printed center justified. That is, the number of spaces at either side must be same, if possible; in other case, one more space must be added at the right side.
Edit: Somehow, I didn't think about it, yes if the problem statement's max value was used then we would require bigints, I think that if the administrators find this out they are gonna update the input so I am gonna make a bigint solution just in case.
rejudgement
Posted: Mon Oct 16, 2006 12:03 am
by sohel
I think the judge data has been modified followed by a rejudge..
Now, only valid solutions will get ACed..
Now, I have to recode my one as i used long long last time..
Posted: Fri Oct 27, 2006 6:10 am
by joeluchoa
I not found my mistake. I've got several WA .
Some hint?
This is my code:
Posted: Fri Oct 27, 2006 8:10 am
by joeluchoa
I've got AC now!
Posted: Tue Feb 13, 2007 6:49 pm
by mukeshtiwari
hi everybody can any one suggest me how to print in this format...i m able to figure out numbers for example 75/34 the number is 2 4 1 5 but i m not able to format this problem's ouput plz help me...here is my code to figure out numbers...
Code: Select all
#include<stdio.h>
int gcd(int u,int v)
{
int t;
while(v!=0)
{
t=u%v;
u=v;
v=t;
}
return(u);
}
main()
{
int p,q,t,v;
int a[1000];
int i=0,j;
while(scanf("%d%d",&p,&q) && (p&&q))
{
i=0;
a[i]=p;
//printf("%d %d\n",p,q);
while(q!=1)
{
//printf("mukesh\n");
a[i++]=p/q;
//printf("p=%d q=%d a[%d]=%d ",p,q,i-1,a[i-1]);
t=p%q;
p=q;
q=t;
v=gcd(p,q);
p=p/v;
q=q/v;
}
a[i++]=p-1;
//printf("p=%d q=%d t=%d\n",p,q,t);
for(j=0;j<i;j++)
printf("%d ",a[j]);
printf("\n");
}
}
Posted: Tue Feb 13, 2007 9:14 pm
by sclo
You can use a recursive function to print output, or you can do it iteratively. I usually find recursive functions are easier to write.
Posted: Wed Feb 14, 2007 9:00 pm
by mukeshtiwari
so plz tell me abt recursive function ..i m not able to figure out for output formatting...
Posted: Thu Mar 01, 2007 8:43 am
by pineapple
I think this is a very nice problem.
we should output the result exactly,and it doesn't exist PE.
But I think the input is not so good,it makes this problem too complex.
10^20 > p > q > 0
This asks us to use bigint to solve it,it will take much time to calculate p/q
and the swap of p,q.
if the input statement could be the following:
2^63 > p > q > 0
I think the percentage of AC will be higher.
Posted: Tue Apr 10, 2007 9:12 am
by ExUCI
Can someone post some input/outputs??
Also the limits, I'm getting Runtime Error [Signal 8]
, and I can't imagine what kind of input can break my code like that
Thanx in advance
Posted: Fri Mar 07, 2008 1:50 pm
by sapnil
Whats wrong in my code plz help me.
here my code............
Thanks
Keep posting
Sapnil