10277 - Boastin' Red Socks

All about problems in Volume 102. 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
henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

10277 - Boastin' Red Socks

Post by henar2 » Mon Sep 02, 2002 6:10 pm

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
Location: Valladolid (Spain)

Post by henar2 » Thu Sep 05, 2002 3:43 pm

I have modify the above code to meet some things i hadn't taken into account, but i am still gettin WA :cry:
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
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even » Sun Sep 15, 2002 1:42 pm

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
Location: Valladolid (Spain)

Post by henar2 » Sun Sep 15, 2002 1:50 pm

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.
:D
I have just read the problem again and you are all right.
Thank you!!
:D

henar2
New poster
Posts: 30
Joined: Mon Nov 26, 2001 2:00 am
Location: Valladolid (Spain)

Post by henar2 » Sun Sep 15, 2002 2:06 pm

:( 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.. :o undefined

Even
Learning poster
Posts: 75
Joined: Thu Nov 22, 2001 2:00 am
Location: Taiwan

Post by Even » Sun Sep 15, 2002 4:20 pm

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.. :o 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
New poster
Posts: 3
Joined: Thu Feb 24, 2005 1:32 am

10277

Post by Rolando_de_Gilead » Thu Feb 24, 2005 2:22 am

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
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10277 - Boastin' Red Socks

Post by Shafaet_du » Mon Jul 04, 2011 8:33 pm

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

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

Re: 10277 - Boastin' Red Socks

Post by plamplam » Thu Jun 14, 2012 2:22 am

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

Post Reply

Return to “Volume 102 (10200-10299)”