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 »

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
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

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

Post by 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
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

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

Post by azur »

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 »

#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 »

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 »

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 »

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 »

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 »

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