## 11113 - Continuous Fractions

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

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 ]

Pregunt
New poster
Posts: 7
Joined: Thu Jun 16, 2005 8:17 am
Location: M
Contact:
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

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?
[ Common thing of every man is that, everyone thinks that he is uncommon ]

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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.

Tariq Shahriar
New poster
Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor
Sohel vai (Bengali word), Thanks for your kind information.
But, is my continuous fraction output of the input correct? Will you post your output?
[ Common thing of every man is that, everyone thinks that he is uncommon ]

Vexorian
Learning poster
Posts: 100
Joined: Sat Aug 26, 2006 5:50 am
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.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### 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..

joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil
I not found my mistake. I've got several WA .

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:24-25]

joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil
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:24-25]

mukeshtiwari
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,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");

}
}
``````

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
You can use a recursive function to print output, or you can do it iteratively. I usually find recursive functions are easier to write.

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india
so plz tell me abt recursive function ..i m not able to figure out for output formatting...

pineapple
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm
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.

ExUCI
New poster
Posts: 14
Joined: Sat Aug 12, 2006 3:31 am
Location: USA
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

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
Whats wrong in my code plz help me.
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 @@@