## 10277 - Boastin' Red Socks

Moderator: Board moderators

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am

### 10277 - Boastin' Red Socks

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
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
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

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
your output is wrong for 67 67

the correct answer should be 2 0
Last edited by Even on Sun Sep 15, 2002 1:45 pm, edited 1 time in total.

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
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
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am Wrong Answer again and again....

My code is:
[c]

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

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan
henar2 wrote: Wrong Answer again and again....

My code is:
[c]

#include<stdio.h>
#include<math.h>
#define TOL 0.0000001
main()
{
long long r,t,p,q;
while(1)
{
scanf("%lld %lld",&p,&q);
if(p==0 && q==0)
break;
if(p==q)
{
r=2;
t=2;
goto fuera;
}
if(p==0)
{
r=0;
t=2;
goto fuera;
}
for(r=1;r<=50000;r++)
{
continue;
t=(long long)posible_t;
if(fabs(posible_t-t)<TOL && (r>=2 || (t-r)>=2) && t<=50000)
{
goto fuera;
}
}
fuera:
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;
unsigned int q1;
double p;
double q;
double r1, r2;
int r;
int b;

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
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
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 .

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### 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.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson