10077 - The Stern-Brocot Number System

[azur]

Hello Everybody,

I tryed the problem number 10077,
It's about Stern-Brocot numbers.

But judge says always 'Wrong Answer'.

Before giving my code here, I want to know if there is other particular values like 1/0 et 0/1 that I didn't catch ?

Thanks,
Azur

PS : Sorry for my bad english, send me pm if you wanna give me grammar and vocabulary courses

[Ghust_omega]

Hi !! azur the input like 0/1 or 0/1 dont exists here some I/O
input:

Code: Select all

97 3
97 29
2141 3
2141 2143
1301 97
5 97
311 5
5 313
197 5
227 7
227 11
227 5
1 1

ouput

Code: Select all

RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRLL
RRRLLRLLLLLLLL
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRLR
LRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
RRRRRRRRRRRRRRRRRRRRRL
RRRRRRRRRRRRRLLRRLLRLLLL
LLLLLLLLLLLLLLLLLLLRRL
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRLLLL
LLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLRLR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRLLR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRLLRR
RRRRRRRRRRRRRRRRRRRRLRLRR
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRLLR

Hope it helps
Keep posting !!

[azur]

Hi,

I've tried with yours inputs and everything looks good for me !

I found exactly the same output.
Thinking that the problem could be the back space in the last line, i've changed a little my program.

But the judge says always 'Wrong Answer'.

Here is my code :

Code: Select all

#ifndef ONLINE_JUDGE 
#include <fstream.h>
#endif
#include <iostream.h>	

void SternBrocot(int x1,int y1)
{
	int a=0,b=1,c=1,d=0;
	int x=1,y=1;

	if (x1==0)
	{
		cout << "L";
		return ;
	}
		
	while ((x != x1) && (y != y1))
	{
		if (x1*y<y1*x) 
		{ 
			cout <<"L";
			c=x;
			d=y;
			x+=a;
			y+=b;
		}
		else
		{
			cout <<"R";
			a=x;
			b=y;
			x+=c;
			y+=d;
		}
	}
}

int main()
{
	int x1,y1;
	int NewLine=0;

	#ifndef ONLINE_JUDGE 
		ifstream cin("file.in");
	#endif 

	while (cin >> x1 >> y1)
	{
		if (!((x1 ==1) && (y1==1)))	
		{	
			if (NewLine==1)
				cout << endl;
			
			SternBrocot (x1,y1);
			NewLine=1;
		}
	} 

	return 0;
}

Where does my error come from ?

[Ghust_omega]

Hi !! azur this I/O help to you find the bug
input:

Code: Select all

1 2
1 3
1 4

ouput:

Code: Select all

L
LL
LLL

Hope it helps
Keep posting !!

[azur]

Thank you,
now it works

[mask_man]

#include<stdio.h>

int main()
{
int m,n,ru1,rd1,lu1,ld1,tu1,td1;
int i;
char str[100];

while(1)
{
scanf("%d%d",&m,&n);

if((m==1)&&(n==1))
break;
i=0;

lu1=0;
ld1=1;
ru1=1;
rd1=0;

tu1=lu1+ru1;
td1=ld1+rd1;

while((tu1!=m)&&(td1!=n))
{

if(((float)tu1/(float)td1)>(float)((float)m/(float)n))
{
str='L';

ru1=tu1;
rd1=td1;
}
if(((float)tu1/(float)td1)<((float)m/(float)n))
{
str='R';
lu1=tu1;
ld1=td1;
}

tu1=lu1+ru1;
td1=ld1+rd1;
i++;
}

str='\0';

printf("%s\n",str);

}

return 0;

}



//can any one say where is the run time error...........plz help me

[saiful_sust]

Hello mask_man
think simple

change this line

Code: Select all

char str[100];

to

Code: Select all

char str[10000];

[shubhamgarg1]

I am getting output limit exceeded . I have tried all these cases and my program runs fine. Plz help

Code: Select all

#include<stdio.h>

int main()
{
float a,b,i,j,k,l,m,n;
while(1)
{
scanf("%f%f",&a,&b);
if(a==1 && b==1)
break;

i=1;
j=1;
k=0;
l=1;
m=1;
n=0;

while(1)
{
    if(a==i && b==j)
    break;
    if((a/b)<(i/j))
{
putchar('L');

m=i;
n=j;
i=i+k;
j=j+l;
k=k;
l=l;

}
else
{
putchar('R');

k=i;
l=j;
i=i+m;
j=j+n;

m=m;
n=n;
}
}
putchar('\n');
}
return 0;
}

[brianfry713]

Try solving it without using floating point.

[e_ahmed]

whats wrong with my code? gets WA but matches the in/outs in this forum

Code: Select all

#include <iostream>
#include <stdio.h>
#include <cmath>
#define verysmall pow(10,-9)
using namespace std;
double N1,N2;
string s="";
int recur(double m,double n,double m1,double n1)
{
    double numerator=m+m1;
    double denumerator=n+n1;
    //cout<<"n="<<numerator<<" d="<<denumerator<<endl;
    if((numerator/denumerator)-(N1/N2)>verysmall)
    {
        s+="L";
        //cout<<s<<endl;
        recur(m,n,numerator,denumerator);
    }
    else if((numerator/denumerator)-(N1/N2)<0)
    {
        s+="R";
        recur(numerator,denumerator,m1,n1);
    }
    else return 0;
}

int  main()
{
    freopen("uva10077.txt","r",stdin);
    while(scanf("%d %d",&N1,&N2)==2)
    {
        s="";
        if(N1==1 && N2==1)break;
        recur(0,1,1,0);
        cout<<s<<endl;
    }
}

[brianfry713]

Don't read from a file.