10077 - The Stern-Brocot Number System

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

Moderator: Board moderators

Post Reply
azur
New poster
Posts: 3
Joined: Mon Nov 01, 2004 12:39 pm

10077 - The Stern-Brocot Number System

Post by azur » Mon Nov 01, 2004 12:41 pm

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 :)

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Thu Nov 04, 2004 4:49 am

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
New poster
Posts: 3
Joined: Mon Nov 01, 2004 12:39 pm

Post by azur » Sat Nov 06, 2004 9:15 pm

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 ?

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Sun Nov 07, 2004 3:45 am

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
New poster
Posts: 3
Joined: Mon Nov 01, 2004 12:39 pm

Post by azur » Fri Nov 12, 2004 5:54 pm

Thank you,
now it works :wink:

mask_man
New poster
Posts: 2
Joined: Mon Mar 17, 2008 8:11 pm

10077 where is the RTE

Post by mask_man » Mon Mar 17, 2008 8:36 pm

#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
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

Re: 10077

Post by saiful_sust » Wed Dec 31, 2008 5:17 pm

Hello mask_man
think simple
change this line

Code: Select all

char str[100];

to

Code: Select all

char str[10000];

shubhamgarg1
New poster
Posts: 3
Joined: Sun Nov 30, 2014 1:07 pm

Re: 10077 - The Stern-Brocot Number System

Post by shubhamgarg1 » Fri Dec 12, 2014 9:26 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10077 - The Stern-Brocot Number System

Post by brianfry713 » Fri Dec 12, 2014 11:05 pm

Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

e_ahmed
New poster
Posts: 1
Joined: Sun Feb 16, 2014 8:44 am

Re: 10077 - The Stern-Brocot Number System

Post by e_ahmed » Wed Mar 11, 2015 6:14 pm

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;
    }
}
Last edited by brianfry713 on Tue Mar 31, 2015 12:03 am, edited 1 time in total.
Reason: Added code block

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10077 - The Stern-Brocot Number System

Post by brianfry713 » Tue Mar 31, 2015 12:03 am

Don't read from a file.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 100 (10000-10099)”