11113  Continuous Fractions
Moderator: Board moderators
 Tariq Shahriar
 New poster
 Posts: 17
 Joined: Wed Mar 01, 2006 8:34 pm
 Location: 2nd floor
11113  Continuous Fractions
For this problem, I used
[ Common thing of every man is that, everyone thinks that he is uncommon ]
 Tariq Shahriar
 New poster
 Posts: 17
 Joined: Wed Mar 01, 2006 8:34 pm
 Location: 2nd floor
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?
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?
[ Common thing of every man is that, everyone thinks that he is uncommon ]
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.
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.
 Tariq Shahriar
 New poster
 Posts: 17
 Joined: Wed Mar 01, 2006 8:34 pm
 Location: 2nd floor
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:
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:
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.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.
rejudgement
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..
Now, only valid solutions will get ACed..
Now, I have to recode my one as i used long long last time..
I not found my mistake. I've got several WA .
Some hint?
This is my code:
Some hint?
This is my code:
Code: Select all
Removed ofter AC
Last edited by joeluchoa on Fri Oct 27, 2006 8:10 am, edited 1 time in total.
http://acm.uva.es/problemset/usersnew.php?user=47903
All men are like grass,and all their
glory is like the flowers of the field;
the grass withers and the flowers fall,
but the word of the Lord stands forever.
[1 Peter 1:2425]
All men are like grass,and all their
glory is like the flowers of the field;
the grass withers and the flowers fall,
but the word of the Lord stands forever.
[1 Peter 1:2425]
I've got AC now!
http://acm.uva.es/problemset/usersnew.php?user=47903
All men are like grass,and all their
glory is like the flowers of the field;
the grass withers and the flowers fall,
but the word of the Lord stands forever.
[1 Peter 1:2425]
All men are like grass,and all their
glory is like the flowers of the field;
the grass withers and the flowers fall,
but the word of the Lord stands forever.
[1 Peter 1:2425]

 Learning poster
 Posts: 63
 Joined: Tue Mar 07, 2006 6:51 pm
 Location: india
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,i1,a[i1]);
t=p%q;
p=q;
q=t;
v=gcd(p,q);
p=p/v;
q=q/v;
}
a[i++]=p1;
//printf("p=%d q=%d t=%d\n",p,q,t);
for(j=0;j<i;j++)
printf("%d ",a[j]);
printf("\n");
}
}

 Learning poster
 Posts: 63
 Joined: Tue Mar 07, 2006 6:51 pm
 Location: india
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.
and the swap of p,q.
if the input statement could be the following:
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.
This asks us to use bigint to solve it,it will take much time to calculate p/q10^20 > p > q > 0
and the swap of p,q.
if the input statement could be the following:
I think the percentage of AC will be higher.2^63 > p > q > 0
Whats wrong in my code plz help me.
here my code............
Thanks
Keep posting
Sapnil
here my code............
Code: Select all
...Code removed
Thanks
Keep posting
Sapnil
Last edited by sapnil on Mon Jul 28, 2008 2:37 pm, edited 1 time in total.
"Dream Is The Key To Success"
@@@ Jony @@@
@@@ Jony @@@