834 - Continued Fractions

[haaaz]

Can someone kindly provide me some test cases for p834-Continued Fractions ?

Thank you.

[haaaz]

I still got WA.
Anyone can provide me some tricky test inputs?

[supermin]

I don't know whether this problem has tricky inputs,but I can offer you some cases:
5 8
[0;1,1,1,2]
1684 6441
[0;3,1,4,1,2,2,3,12]
1 9
[0;9]
2 4
[0;2]
4898 215
[22;1,3,1,1,2,1,6]

good luck!!

[boatfish]

I have considered the cases for negative numbers, but still WA. why??

Code: Select all

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

int main(){
	int a,b;
	float t;
	bool set;
	while(cin>>a>>b){
		set=false;
		t=a/float(b);
		if(t>=0){
			cout<<'['<<a/b<<';';
			a=a-a/b*b;
		}
		else{
			cout<<'['<<a/b-1<<';';
			a=fabs(b)-(fabs(a)-fabs(a/b*b));
			b=fabs(b);
		}
		while(a!=0){
			swap(a,b);
			cout<<a/b<<',';
			a=a-a/b*b;
			set=true;
		}
		if(set)
			cout<<"\b]\n";
		else
			cout<<"]\n";
	}
	return 0;
}

[shamim]

consider the case,
4 2

your program gives
[2;]

The semi colon should not appear.

[boatfish]

Hi, I have handled that, but still WA. Why?
[cpp]#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;

int main(){
int a,b;
float t;
while(cin>>a>>b){
t=a/float(b);
if(t>=0){
cout<<'['<<a/b<<';';
a=a-a/b*b;
}
else{
cout<<'['<<a/b-1<<';';
a=fabs(b)-(fabs(a)-fabs(a/b*b));
b=fabs(b);
}
while(a!=0){
swap(a,b);
cout<<a/b<<',';
a=a-a/b*b;
}
cout<<"\b]\n";
}
return 0;
}[/cpp]

[Observer]

I've just solved this problem. I note that there are NO negative numbers in the input! So don't worry about that.

[boatfish]

I've just solved this problem. I note that there are NO negative numbers in the input! So don't worry about that.

Then why I keep on WA?

[helmet]

THERE ARE NO NEGATIVE NUMBERS!!!

I didnt even consider the case...though if num/den is a whole number remember not to output the ';'.

[Wei]

Can anybody help me with these problems???
1.If the input is 2 1....What should I do for the output?? [2;]??? or what??
2.Is any negative number in the input????

[Ryan Pai]

1. My program crashed on this input
2. If the first number is negative my program crashes, if the denominator is negative it outputs the same numbers as if the denominator was positive, except they are all negative also.

From this I doubt that the judge's data includes true integers or negative numbers.

[Wei]

Well~~I know the problem......
Thx for your answering!!!!

[sohag144]

can anyone give me huge input/output for this problem.

[Timo]

Hi sohag144,
I have create random sample input and output from my AC program.
Hope it help you.

Input :

688 558
366 699
673 854
352 375
755 606
344 850
797 944
584 330
505 687
787 440
90 325
177 440
352 274
75 908
527 411
601 94
746 318
602 691
459 236
394 206
642 182
411 686
160 196
357 991
111 199
956 344
497 418
882 374
73 856
988 379
716 764
397 10
146 604
571 114
364 444
944 940
631 287
213 440
336 266
876 868
615 207
129 411
34 507
682 62
205 803
631 456
668 406
936 885
880 959
636 219
669 292
370 941
973 944
307 24
234 321
78 860
274 961
809 968
995 856
833 694
765 338
199 629
810 455
543 948
473 336
440 411
681 499
819 229
450 579
532 510
797 433
680 528
878 113
779 499
706 641
373 118
301 94
173 546
600 937
326 86
981 92
907 254
741 694
218 478
376 26
8 123
999 580
180 84
747 724
106 645
521 940
122 838
891 106
314 13
526 783
176 841
989 989
242 465
221 407
278 20


Output :

[1;4,3,2,2,1,2]
[0;1,1,10,11]
[0;1,3,1,2,1,1,4,1,1,2]
[0;1,15,3,3,2]
[1;4,14,1,9]
[0;2,2,8,10]
[0;1,5,2,2,1,2,3,2]
[1;1,3,2,1,12]
[0;1,2,1,3,2,3,1,1,2]
[1;1,3,1,2,1,2,1,1,3]
[0;3,1,1,1,1,3]
[0;2,2,17,5]
[1;3,1,1,19]
[0;12,9,2,1,2]
[1;3,1,1,5,3,3]
[6;2,1,1,5,1,2]
[2;2,1,8,6]
[0;1,6,1,3,4,5]
[1;1,17,6,2]
[1;1,10,2,4]
[3;1,1,8,1,1,2]
[0;1,1,2,45,3]
[0;1,4,2,4]
[0;2,1,3,2,6,6]
[0;1,1,3,1,4,1,3]
[2;1,3,1,1,9]
[1;5,3,2,3,3]
[2;2,1,3,1,3,1,2]
[0;11,1,2,1,1,1,6]
[2;1,1,1,1,5,4,3]
[0;1,14,1,11]
[39;1,2,3]
[0;4,7,3,3]
[5;114]
[0;1,4,1,1,4,2]
[1;235]
[2;5,28,2]
[0;2,15,4,1,2]
[1;3,1,4]
[1;108,2]
[2;1,33,2]
[0;3,5,2,1,2]
[0;14,1,10,3]
[11]
[0;3,1,11,17]
[1;2,1,1,1,1,6,2,2]
[1;1,1,1,4,1,1,6]
[1;17,2,1,5]
[0;1,11,7,5,2]
[2;1,9,2,3]
[2;3,2,3,2,1,3]
[0;2,1,1,5,3,1,1,4]
[1;32,1,1,4,3]
[12;1,3,1,4]
[0;1,2,1,2,4,2]
[0;11,39]
[0;3,1,1,33,1,3]
[0;1,5,11,2,1,4]
[1;6,6,3,7]
[1;4,1,138]
[2;3,1,3,1,17]
[0;3,6,4,1,1,3]
[1;1,3,1,1,4,2]
[0;1,1,2,1,14,3]
[1;2,2,4,1,3,3]
[1;14,5,1,4]
[1;2,1,2,1,6,1,5]
[3;1,1,2,1,3,2,1,2]
[0;1,3,2,21]
[1;23,5,2]
[1;1,5,3,1,1,1,2,2]
[1;3,2,9]
[7;1,3,2,1,8]
[1;1,1,3,1,1,2,3,1,2]
[1;9,1,6,4,2]
[3;6,4,1,3]
[3;4,1,18]
[0;3,6,2,2,5]
[0;1,1,1,3,1,1,4,8]
[3;1,3,1,3,2]
[10;1,1,1,30]
[3;1,1,3,36]
[1;14,1,3,3,1,2]
[0;2,5,5,4]
[14;2,6]
[0;15,2,1,2]
[1;1,2,1,1,1,1,15,2]
[2;7]
[1;31,2,11]
[0;6,11,1,3,2]
[0;1,1,4,9,3,1,2]
[0;6,1,6,1,1,1,2]
[8;2,2,6,1,2]
[24;6,2]
[0;1,2,21,2,2,2]
[0;4,1,3,1,1,19]
[1]
[0;1,1,11,1,2,1,4]
[0;1,1,5,3,5,2]
[13;1,9]

[sohag144]

thank you. but can you give me some extra input output,like
-5 3
1 3
3 1
-25 6
0 2
2 0

more like this. in question says: To ensure uniqueness, make bn > 1.
can you explain with example?