11113 - Continuous Fractions

[Tariq Shahriar]

For this problem, I used

[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

[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?

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

[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?

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

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

[joeluchoa]

I not found my mistake. I've got several WA .

Some hint?

This is my code:

Code: Select all

Removed ofter AC

[joeluchoa]

I've got AC now!

[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");
				
				
				
			}
	 }

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

[mukeshtiwari]

so plz tell me abt recursive function ..i m not able to figure out for output formatting...

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

[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

[sapnil]

Whats wrong in my code plz help me.
here my code............

Code: Select all

...Code removed

Thanks
Keep posting
Sapnil