10096 - The Richest Man of the Universe

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
..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

little joey wrote:No, I see no point in changing the I/O again. There's enough information in this forum for everybody to succesfully solve this problem, I think, so a clarification is probably not necessary. But maybe the problemsetter should decide, if he still reads the boards.
I agree with little joey, the infromation in this thread should be enough to solve the problem.

Actually I think this problem is not well defined when some input value is zero, but you know, Shahriar Manzoor always likes to play this trick... :wink:
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.
Top
lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

10096

Post by lovemagic »

i don't know why my 10096 gets WA after rejudging!
my code gives these output for the inputs.
plz tell me are these right or wrong && if wrong what's the right?

input

48
S 0 0 0
S 2 2 0
S 2 0 0
S 3 0 1
S 10 10 5
S 8.48 6 3
S 8.49 6 3
S 9 2 1
S 9 1.999999 1
S 4 2 1
S 3.999999 2 1
S 3.999999 1.999999 1
S 2000 2000 1
S 2000 2000 500
S 10 10 4
S 4.0 2.0 1.414213562373
S .1 .1 .025
S 8.5 8.6267 3.05
S 8.5 8.62670274 3.05
S 1 1 .002
S 4 8 2
S 4 8 2.0000001
S 4.00000002 8.00000004 2.00000001
M 1 2 3
M 1 2 4
M 0 0 0
M 0 0 1
M 1 0 1
M .1 .1 .1
M 1 .00001 1
M 1 .0001 1
M 1 .001 1
M 1 .01 1
M 1 .1 1
M 2 3 4.9
M 2 3 4.99
M 2 3 4.999
M 2 3 4.9999
M 5 3 5
M 10 10 10
M 10 9.99 10
M 5 5.1 10
M 5 5.01 10
M 5 5.001 10
M 5 5 9.888888889
M 5 5 9.8
M 5 4.99 9.98
M 5 4.99 9.97



output

0.0000

2.8284

2.0000

Not enough space for fission.

Not enough space for fission.

Not enough space for fission.

4.3962

7.2195

Not enough space for fission.

2.4721

2.4721

Not enough space for fission.

2826.4271

1828.4271

Not enough space for fission.

Not enough space for fission.

0.0914

Not enough space for fission.

6.0107

1.4102

4.9443

Not enough space for fission.

4.9443

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

0.8045

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

0.9952

0.9984

0.9999

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

0.8847

0.8045

0.8046

0.9994

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

0.9993

0.9983

1.0000
No compaction has occurred.

0.9999
khobaib
Top
Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:
Contact Zuza

10096 fission?

Post by Zuza »

Can somebody explain me the process of fission in 10096? Does the initial virus (with the specs got from the input) splits in two viruses with radii equal one half the initial or we have to split up two viruses of input sizes?
Top
Kadaver
New poster
Posts: 4
Joined: Sat Oct 23, 2004 11:53 am
Location: Czech Republic
Contact:
Contact Kadaver

Post by Kadaver »

Good morning,

I tried to solve the problem and heeded the hints, you talked about on this forum, but it still gives me WA. In fission I'm using sqrt((l-r*sqrt(2))^2 + (w-r*sqrt(2)^2), which is hopefully right, and in fussion I add surface area covered by first circle to the surface area covered by second circle and then subtract the overlapped area.

The result of this is that it gives me the exactly same output as it gives to you on this forum, but the judge still keeps giving me WA as answer. I tried to print "No compaction occured" only when r1+r2<=d, but it didn't work, so I change my program to print it everytime I get 1.0000, but it didn't work either.

I really don't know, what to do now. Can you help me, please?

Thanks in advance...

Kadaver
Top
Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:
Contact Zuza

Post by Zuza »

No need to bother. I figured it out. r2=r1/sqrt(2)
Top
Kadaver
New poster
Posts: 4
Joined: Sat Oct 23, 2004 11:53 am
Location: Czech Republic
Contact:
Contact Kadaver

10096 Richest Man of the Universe - Fussion

Post by Kadaver »

Can somebody tell me, please, how the fussion part of the Richest Man of the Universe problem (i.e. 10096) has to be calculated? I tried to solve the problem, but I still get WA. In fission I'm using sqrt((l-r*sqrt(2))^2 + (w-r*sqrt(2))^2), which is hopefully right. In fussion I'm using the following code:

[c] r1sqr = sqr(r1);
r2sqr = sqr(r2);
dsqr = sqr(d);
alpha = acos( (r1sqr + dsqr - r2sqr) / (2 * r1 * d) );
beta = acos( (r2sqr + dsqr - r1sqr) / (2 * r2 * d) );
surface1 = PI * r1sqr;
surface2 = PI * r2sqr;
surfaceU1 = (r1sqr / 2) * (2 * alpha - sin(2 * alpha));
surfaceU2 = (r2sqr / 2) * (2 * beta - sin(2 * beta));
surfaceBeforeFussion = surface1 + surface2;
surfaceAfterFussion = surface1 + surface2 - surfaceU1 - surfaceU2;
return (surfaceAfterFussion / surfaceBeforeFussion);
[/c]

thus, I add surface area of the first circle to the surface area of the second circle and then subtract their overlapped area, which I compute from circle segments of each circle.
I think, that in some situations this code isn't giving right results (either by rounding or for some other mystical reasons), but I don't know how to substitute it. Could you, please, help me with this? I would be most grateful.

Kadaver
Top
..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. »

Have you searched the forum before posting??
http://online-judge.uva.es/board/viewto ... ight=10096
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.
Top
Kadaver
New poster
Posts: 4
Joined: Sat Oct 23, 2004 11:53 am
Location: Czech Republic
Contact:
Contact Kadaver

Post by Kadaver »

Yes, I have... And I have also posted a message there. My program gives the same results as the programs there and I have tried to add/remove different conditions to get Accepted, but still, it isn't working. But there's not a word about fussion in the thread you posted me. And I think that fussion is the wrong part in my program. I think that there is a rounding error after all those arccosines and multiplies and divisions. I think that there is some other way to calculate it, but I can't find it. Could you possibly help me with that?
Top
arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:
Contact arif_pasha

Post by arif_pasha »

i got the following for your input.. but still wa. can AC ones post their output for those test case?

Code: Select all

0.0000

2.8284

2.0000

Not enough space for fission.

Not enough space for fission.

4.5873

4.5966

7.6084

7.6084

2.6513

2.6513

2.6513

2826.4271

1828.4271

6.1421

2.0000

0.0914

6.0111

6.0111

1.4102

5.3026

5.3026

5.3026

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

0.8045

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

0.9952

0.9984

0.9999

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

0.8847

0.8045

0.8046

0.9994

1.0000
No compaction has occurred.

1.0000
No compaction has occurred.

0.9993

0.9983

1.0000
No compaction has occurred.

0.9999
Top
arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:
Contact arif_pasha

Post by arif_pasha »

Hi, i am also gettin a lots of wa's

can anyone answer my following questions

1.>
what do you print in fusion part, if the ratio is 0.99995...?
0.9999
or
1.0000
or
1.0000
No compaction occured.

2.>
[fission] let the radius of two new circles are "r". I "printed not enough space" if either L<2r or W<2r or distance d<2r. is it correct?

thnx in advance..
Top
nukeu666
New poster
Posts: 44
Joined: Sun Feb 13, 2005 1:13 am
Location: India
Contact:
Contact nukeu666

Post by nukeu666 »

could any of the people who got accepted please help out with this problem
ive tried all the inputs on these forums and guess im getting them right
google
Top
dipaly
New poster
Posts: 20
Joined: Tue Sep 19, 2006 6:18 pm
Location: bangladesh
Contact:
Contact dipaly

10096(10 WA):-( help plz

Post by dipaly »

hi everyone. I get 10 WA in 10096.

I have some qns.
if there is any special case for fission & fussion?

for fussion if d==r1+r2; .. what should be the output?
if 0(zero) can be a input?from prev.. post i saw that the output for this input
S 0.0 0.0 0.0 is 0.0000----> is it correct?

in fission if the initial virus's radious R >(l,w) then what should i do:

for fission i do following work in my code

Code: Select all

void fission(double l, double w, double R)
{
	if(w>l)
	{
		double t=l;
		l=w;
		w=t;
	}
	if(R > 0 && R<=l && R<=w)
	{
		double r = R/sqrt(2);
		if((l>=4*r) && (w>=2*r))
		{
			double a = l-2*r , b = w-2*r;
			double c = sqrt(a*a + b*b);
			printf("%.4lf\n",c);
		}
		else 
			printf("Not enough space for fission.\n");
	}
	else if(R==0&&w==0&&l==0)
	{
		double g=0;
		printf("%.4lf\n",g);
	}
	else 
		printf("Not enough space for fission.\n");	
}


[/b]for fussion i do following job..
void len(double r, double R, double d)
{
if(d >= (r+R))
{
printf("1.0000\nNo compaction has occured.\n");

}

else
{
if(r !=0 && R !=0 && d != 0)
{
double a1 = (d*d) + (r*r) - (R*R) ,a2 = d*d+R*R-r*r,a3=2*d*r,a4=2*d*R;
double b1 = a1/a3, b2 = a2/a4 ,b3 = -d+r+R ,b4=d+r-R,b5=d-r+R,b6=d+r+R;
double c1 = r*r*acos(b1),c2=R*R*acos(b2),c3=b3*b4*b5*b6;
double c4 = (sqrt(c3))/2;
double z = c1+c2-c4;
double com = (M_PI*r*r +M_PI*R*R -z) / (M_PI*r*r+M_PI*R*R);
if(com==1.0000)
printf("1.0000\nNo compaction has occurred.\n");
else
printf("%.4lf\n",com);
}
else
printf("1.0000\nNo compaction has occurred.\n");
}
}


plz help me :(
:( :cry:
everything is so hard to me
Top
arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:
Contact arif_pasha

Post by arif_pasha »

After a lot of tries and of course a lot of WA's i decided to give up this problem.. :cry: :cry: :cry:
Top
Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

This problem shouldn't be that hard, should it? I tried it about a year ago and gave up back then. I just tried it again and I can't get an AC.

I was about to recode it in C and see if it helped, but then decided against it. It's not worth it. I might try it when it becomes one of the last unsolved problems for me. "Might" being the key word.

Can someone explain to me what zeros would mean as any part of the input? Zero radius virus? Or a zero length box? It is obvious they are there, because of the wording. I guess we should deal with corner cases, but this is just introducing nonsense to make a problem "harder". I don't get it. And, I am guessing here, I have to use the exact order of operations that the problemsetter used or something. And the same rounding. I am using acos(), maybe he used asin() or something... Blah.

I guess 16 people solved it, so I shouldn't complain. 16 people. Come on...
Top
andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
Contact andysoft

Post by andysoft »

Hello, men!
I tried to solve this one myself with no help, then I read the thread - result is the same - WA. I have now decided to write here for help... Watch my code please and say, where am I wrong, if my input is the same as little joey's on the previous page (except wrong composed cases with 'M').

Thank you all in advance:

Code: Select all

program Project3;

{$APPTYPE CONSOLE}

uses
  SysUtils, Math;

var
  r1,r2,be,ce,alpha,beta,s,ae,d,l,w,ans,r,l1,l2: extended;
  c: char;
  ci,cn: integer;


begin

  readln (cn);

  for ci := 0 to cn - 1 do
  begin
    if ci>0 then
      writeln;

    read (c);

    if c='M' then
    begin
      readln (r1,r2,d);

      if r1+r2 <= d then
      begin
        writeln ('1.0000');
        writeln ('No compaction has occurred.');
        continue
      end;

      if d<=abs(r1-r2) then
        s := min (pi*r1*r1,pi*r2*r2)
      else
      begin
        ae := (r1*r1 - r2*r2 + d*d)/(2*d);
        be := d - ae;
        ce := sqrt (r1*r1 - ae*ae);
        alpha := 2*arctan (ce/ae);
        if alpha<0 then
          alpha := alpha + pi;
        beta := 2*arctan (ce/be);
        if beta<0 then
          beta := beta + pi;
        s := (r1*r1*(alpha-sin(alpha)) + r2*r2*(beta-sin(beta)))/2.0
      end;
      ans := (pi*r1*r1 + pi*r2*r2);
      ans := (ans - s) / ans;

      writeln (ans:0:4);

      if abs(ans-1)<1e-5 then
        writeln ('No compaction has occurred.');

    end
    else
    begin
      readln (l,w,r);

      d := sqrt(l*l+w*w-r*sqrt(8)*(l+w)+r*r*4);

      if (r<>0) and ((sqrt(w*w+l*l) - d < 1e-5) or (l-sqrt(2)*r < 1e-5) or (w-sqrt(2)*r < 1e-5)) then
      begin
        writeln ('Not enough space for fission.');
        continue
      end;

      ans := d;


      writeln (ans:0:4);
      


    end;


  end;

  writeln

end.
Now I lay me down to sleep...
my profile
Top
Post Reply

Return to “Volume 100 (10000-10099)”