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

User avatar
Tariq Shahriar
New poster
Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor

11113 - Continuous Fractions

Post by Tariq Shahriar » Tue Oct 10, 2006 3:43 am

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:

Post by Pregunt » Tue Oct 10, 2006 5:54 am

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

User avatar
Tariq Shahriar
New poster
Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor

Post by Tariq Shahriar » Wed Oct 11, 2006 5:31 am

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 ]

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

Post by sohel » Wed Oct 11, 2006 8:29 am

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.

User avatar
Tariq Shahriar
New poster
Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor

Post by Tariq Shahriar » Wed Oct 11, 2006 9:08 am

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

Post by Vexorian » Thu Oct 12, 2006 6:13 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.

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

rejudgement

Post by sohel » Mon Oct 16, 2006 12:03 am

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

User avatar
joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil

Post by joeluchoa » Fri Oct 27, 2006 6:10 am

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]

User avatar
joeluchoa
New poster
Posts: 28
Joined: Sat Jul 31, 2004 12:11 am
Location: Brasil

Post by joeluchoa » Fri Oct 27, 2006 8:10 am

I've got AC now! :D
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

Post by mukeshtiwari » Tue Feb 13, 2007 6:49 pm

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:

Post by sclo » Tue Feb 13, 2007 9:14 pm

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

Post by mukeshtiwari » Wed Feb 14, 2007 9:00 pm

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

Post by pineapple » Thu Mar 01, 2007 8:43 am

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

Post by ExUCI » Tue Apr 10, 2007 9:12 am

Can someone post some input/outputs??
Also the limits, I'm getting Runtime Error [Signal 8] :evil: , 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:

Post by sapnil » Fri Mar 07, 2008 1:50 pm

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 @@@

Post Reply

Return to “Volume 111 (11100-11199)”