Hi, I am getting wrong answer
Please, check my code or tell me some fuzzy cases:
[c]
#include<stdio.h>
#include<math.h>
#define TOLERANCE 0.0000001
main()
{
long double possible_t,inside_root;
char found;
long long r,t,p,q;
while(1)
{
scanf("%lld %lld",&p,&q);
if(p==0 && q==0)
break;
if(p==q || p==0)
{
found=1;
r=1;
t=2;
goto finished;
}
found=0;
for(r=2;r<50000;r++)
{
inside_root=1.-(4.*q*r*(1.-r))/p;
if(inside_root<TOLERANCE)
continue;
possible_t=(1.+sqrt(inside_root))/2.;
t=(long long)possible_t;
if(fabs(possible_t-t)<TOLERANCE)
{
found=1;
goto finished;
}
}
finished:
if(found==1)
printf("%lld %lld\n",r,t-r);
else
printf("impossible\n");
}
}
[/c]
Thank you.undefined
10277 - Boastin' Red Socks
Moderator: Board moderators

My code is:
[c]
#include<stdio.h>
#include<math.h>
#define TOL 0.0000001
main()
{
long double posible_t,radicando;
char encontrado;
long long r,t,p,q;
while(1)
{
scanf("%lld %lld",&p,&q);
if(p==0 && q==0)
break;
if(p==q)
{
encontrado=1;
r=2;
t=2;
goto fuera;
}
if(p==0)
{
encontrado=1;
r=0;
t=2;
goto fuera;
}
encontrado=0;
for(r=1;r<=50000;r++)
{
radicando=1.-(4.*q*r*(1.-r))/p;
if(radicando<TOL)
continue;
posible_t=(1.+sqrt(radicando))/2.;
t=(long long)posible_t;
if(fabs(posible_t-t)<TOL && (r>=2 || (t-r)>=2) && t<=50000)
{
encontrado=1;
goto fuera;
}
}
fuera:
if(encontrado==1)
printf("%lld %lld\n",r,t-r);
else
printf("impossible\n");
}
}
[/c]
Please check it..

I try to modify your code and find the answer...henar2 wrote:Wrong Answer again and again....
My code is:
[c]
#include<stdio.h>
#include<math.h>
#define TOL 0.0000001
main()
{
long double posible_t,radicando;
char encontrado;
long long r,t,p,q;
while(1)
{
scanf("%lld %lld",&p,&q);
if(p==0 && q==0)
break;
if(p==q)
{
encontrado=1;
r=2;
t=2;
goto fuera;
}
if(p==0)
{
encontrado=1;
r=0;
t=2;
goto fuera;
}
encontrado=0;
for(r=1;r<=50000;r++)
{
radicando=1.-(4.*q*r*(1.-r))/p;
if(radicando<TOL)
continue;
posible_t=(1.+sqrt(radicando))/2.;
t=(long long)posible_t;
if(fabs(posible_t-t)<TOL && (r>=2 || (t-r)>=2) && t<=50000)
{
encontrado=1;
goto fuera;
}
}
fuera:
if(encontrado==1)
printf("%lld %lld\n",r,t-r);
else
printf("impossible\n");
}
}
[/c]
Please check it..undefined
1...use long double for long long...
2...check if the radicando is sqr first
3...r begin from 2
-
- New poster
- Posts: 3
- Joined: Thu Feb 24, 2005 1:32 am
10277
I have a problem with this program. When the input is: "12 2499550020" and j = 49992 the line: "if ( ((n == r2) && n>1) || ((m==r1) && m>1))" says "WRONG", but it is true, I had used the debugger and n=r2 = 4.0000000000000 and if I solve the equation with a calculator it's also true. Someone can help me?
-------------------------------------------------------------------------------------
#include <stdio.h>
#include <math.h>
int readinput (unsigned int p[], unsigned int q[]) {
int i=0;
while(q!=0) {
scanf("%d %d",&p, &q);
if (q!=0) {
i++; }
}
return i;}
void solve (long double a, long double b, long double c, double *r1,double *r2 ) {
*r1= (-b + sqrt(b*b-4*a*c)) /(2*a);
*r2= (-b - sqrt(b*b-4*a*c)) /(2*a);
}
void main() {
int i=0, j=1, num;
int end ;
double m, n;
unsigned int p1[30];
unsigned int q1[30];
double p[30];
double q[30];
double r1, r2;
int r[30];
int b[30];
num = readinput (p1, q1);
for (i=0; i<num; i++) {
p=p1;
q=q1;}
for (i=0; i<num; i++) {
end=0;
while (!end && j<50000) {
solve(((p/q)-1), (1-(p[i]/q[i]) + 2*(p[i]/q[i])*j), ((p[i]/q[i])*j*j - (p[i]/q[i])*j), &r1, &r2) ;
m = floor (r1);
n = floor (r2);
if ( ((n == r2) && n>1) || ((m==r1) && m>1)) {
end=1;}
j++; }
if (j!=50000) {
if ( m ==r1 && n ==r2 && r1>r2 && (r2+j-1) >1) {
r[i] = r2;}
else if ( m ==r1 && n ==r2 && r2>r1 && (r1+j-1) >1 ) {
r[i] = r1;}
else if ( m ==r1 && (r1+j-1) >1) {
r[i] = r1;}
else if ( n==r2 && (r2+j-1) >1) {
r[i] = r2;}
b[i]=j-1;
printf ("%d %d\n", r[i], b[i]);}
else
printf ("Impossible\n");
}
}
----------------------------------------------------------------------------
Thanks.
-------------------------------------------------------------------------------------
#include <stdio.h>
#include <math.h>
int readinput (unsigned int p[], unsigned int q[]) {
int i=0;
while(q!=0) {
scanf("%d %d",&p, &q);
if (q!=0) {
i++; }
}
return i;}
void solve (long double a, long double b, long double c, double *r1,double *r2 ) {
*r1= (-b + sqrt(b*b-4*a*c)) /(2*a);
*r2= (-b - sqrt(b*b-4*a*c)) /(2*a);
}
void main() {
int i=0, j=1, num;
int end ;
double m, n;
unsigned int p1[30];
unsigned int q1[30];
double p[30];
double q[30];
double r1, r2;
int r[30];
int b[30];
num = readinput (p1, q1);
for (i=0; i<num; i++) {
p=p1;
q=q1;}
for (i=0; i<num; i++) {
end=0;
while (!end && j<50000) {
solve(((p/q)-1), (1-(p[i]/q[i]) + 2*(p[i]/q[i])*j), ((p[i]/q[i])*j*j - (p[i]/q[i])*j), &r1, &r2) ;
m = floor (r1);
n = floor (r2);
if ( ((n == r2) && n>1) || ((m==r1) && m>1)) {
end=1;}
j++; }
if (j!=50000) {
if ( m ==r1 && n ==r2 && r1>r2 && (r2+j-1) >1) {
r[i] = r2;}
else if ( m ==r1 && n ==r2 && r2>r1 && (r1+j-1) >1 ) {
r[i] = r1;}
else if ( m ==r1 && (r1+j-1) >1) {
r[i] = r1;}
else if ( n==r2 && (r2+j-1) >1) {
r[i] = r2;}
b[i]=j-1;
printf ("%d %d\n", r[i], b[i]);}
else
printf ("Impossible\n");
}
}
----------------------------------------------------------------------------
Thanks.
-
- Experienced poster
- Posts: 147
- Joined: Mon Jun 07, 2010 11:43 am
- Location: University Of Dhaka,Bangladesh
- Contact:
Re: 10277 - Boastin' Red Socks
After 10wa,2tle,and plenty of hours,finally got accepted. I would like to share some little hints. From basic concept of probability we can easily see
R/(R+B)*(R-1)/(R+B-1)=p/q;
==>R*(R-1)/(R+B)*(R+B-1)=p/q;
Now make the upper portion of the both fractions same and so you will get (R+B)*(R+B-1)=C where C is the constant value you get after making upper parts same. loop from R=2 to R=50000 and solve the equation from B. try to minimize R+B. to avoid overflow use unsigned long long and divide by gcd whenever you can. special case: if P is 0 ans=0,2. and remember R+B must be less than 50000.
This might not be the best way but certainly works
.
R/(R+B)*(R-1)/(R+B-1)=p/q;
==>R*(R-1)/(R+B)*(R+B-1)=p/q;
Now make the upper portion of the both fractions same and so you will get (R+B)*(R+B-1)=C where C is the constant value you get after making upper parts same. loop from R=2 to R=50000 and solve the equation from B. try to minimize R+B. to avoid overflow use unsigned long long and divide by gcd whenever you can. special case: if P is 0 ans=0,2. and remember R+B must be less than 50000.
This might not be the best way but certainly works

UVa stats: http://felix-halim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
Re: 10277 - Boastin' Red Socks
I solved it with almost the same method described by Shafaet_DU although I was not that unlucky to get a lot of wrong answers, but no need to calculate the gcd and divide it to avoid overflow. Use binary search to solve the quadratic equation. Instead of an equation consisting of R and B, I think this is much easier to solve.
R*(R-1)/Z*(Z-1) = p/q;
Where Z = R + S
Now loop from Z = 2 to 50000 and find R using binary search.
R*(R-1)/Z*(Z-1) = p/q;
Where Z = R + S
Now loop from Z = 2 to 50000 and find R using binary search.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson