10277 - Boastin' Red Socks

[henar2]

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

[henar2]

I have modify the above code to meet some things i hadn't taken into account, but i am still gettin WA
Could somebody tells me if this output is correct for the input:

Input:

0 45
67 67
3 324


Output:

0 2
2 2
611 5734

Thank you in advance.

[Even]

your output is wrong for 67 67

the correct answer should be 2 0

[henar2]

Thank you for your comment..
I was watching the status web page and I saw you sending the problem, and in 5 minutes I received the topic reply notification, first with 0 2 and then with 2 0.

I have just read the problem again and you are all right.
Thank you!!

[henar2]

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

[Even]

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

I try to modify your code and find the answer...

1...use long double for long long...
2...check if the radicando is sqr first
3...r begin from 2

[Rolando_de_Gilead]

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.

[Shafaet_du]

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 .

[plamplam]

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.