Discussion @ 1619. Big Brother @ Timus Online Judge

SoSimple Please check my program. I got WA [16] // Problem 1619. Big Brother 17 Aug 2008 16:01

I don't know whats wrong with it

Program b;

{$APPTYPE CONSOLE}

uses
SysUtils;

var
n,k,i,m:integer;
Begin
readln(n);
for i:=1 to n do
begin
    readln(k,m);
    if k=m then
    begin
      writeln(1/(k+1):0:6);
    end
    else
      if m>k then writeln('0')
      else writeln(k/(k+m):0:6);
end;

End.

SabaRG Re: Please check my program. I got WA [15] // Problem 1619. Big Brother 17 Aug 2008 16:52

Why do you write :
if(k==m) return 1/(k+1)
?
if k=m=4, what do you return?

Edited by author 17.08.2008 16:52

SoSimple Re: Please check my program. I got WA [14] // Problem 1619. Big Brother 17 Aug 2008 17:11

because if any moment the Bob's money is greater than this of Alex,Alex breaks all the windows.

0 0 0 0 -- Alex's good deeds

1 1 1 1 -- Bob's good deeds

if the first time Bob do the good deed (or Mother gives the Bob first 1 euro),at this time Alex breaks all the windows. So first time Alexs deed must be choosen and so on. If you follow to this way you can get this formula for k=m.

problablity=1/(k+1);

Edited by author 17.08.2008 17:12

Edited by author 17.08.2008 17:13

Vedernikoff Sergey (HSE: EconomicsForever!) Re: Please check my program. I got WA [13] // Problem 1619. Big Brother 17 Aug 2008 17:18

Your formulae for the case k > m is not right...

SoSimple Re: Please check my program. I got WA [12] // Problem 1619. Big Brother 17 Aug 2008 17:23

Can You give an example test

kai_99 Re: Please check my program. I got WA [9] // Problem 1619. Big Brother 17 Aug 2008 17:25

void solve (int p)
{   float q;
     if (a[p].alex==a[p].bob) q=1.0/(a[p].alex+1.0);
     else q=a[p].alex/(a[p].bob+a[p].alex);
     cout<<q<<endl;}

Where am I wrong?

SoSimple Re: Please check my program. I got WA [8] // Problem 1619. Big Brother 17 Aug 2008 17:29

m>k the answer is 0;

kai_99 Re: Please check my program. I got WA [7] // Problem 1619. Big Brother 17 Aug 2008 17:30

Are you sure?

SoSimple thanks Vedernikoff Sergey (HSE: EconomicsForever!) [6] // Problem 1619. Big Brother 17 Aug 2008 17:36

thanks Vedernikoff Sergey (HSE: EconomicsForever!). I was wrong for this case. The answer is 0.5 for your test not 3/5.

kai_99 Re: thanks Vedernikoff Sergey (HSE: EconomicsForever!) [5] // Problem 1619. Big Brother 17 Aug 2008 17:38

SoSimple wrote 17 August 2008 17:36

thanks Vedernikoff Sergey (HSE: EconomicsForever!). I was wrong for this case. The answer is 0.5 for your test not 3/5.

Why?How?

Dimon Mordvinov Re: thanks Vedernikoff Sergey (HSE: EconomicsForever!) [4] // Problem 1619. Big Brother 17 Aug 2008 17:42

I think that if k>m then the answer doesn`t depend on k, isn`t it?

SoSimple Re: thanks Vedernikoff Sergey (HSE: EconomicsForever!) [3] // Problem 1619. Big Brother 17 Aug 2008 18:02

if k>m Probability=(k-m+1)/(k+1)

mai7 Re: thanks Vedernikoff Sergey (HSE: EconomicsForever!) [2] // Problem 1619. Big Brother 17 Aug 2008 23:28

How did you get it? Do you divide nubmer of successive sequences to number of possibe sequences?

SoSimple Re: thanks Vedernikoff Sergey (HSE: EconomicsForever!) [1] // Problem 1619. Big Brother 19 Aug 2008 17:34

Yes I have found it by this way

Denis Koshman Re: thanks Vedernikoff Sergey (HSE: EconomicsForever!) // Problem 1619. Big Brother 8 Sep 2008 03:54

You may think of it as of number of paths from (0;0) to (k;m) which do not cross main diagonal. There are a total of C(x, x+y) paths. If you try to find recurrent formula for f(x,x), you'll see that it is some sort of convolution over f(1)...f(x-1) which usually refers to Cathalan numbers (Sk = C(x, 2x) / (x+1)), so they are a good guess. Actually f(x,x) = Sx, it can be proven by induction. So, the probability for f(x,x) is 1/(x+1). Probability for f(x,y), y>x can be guessed and proven by induction as well. The general recurrent formula is:
f(x,y) = f(x-1,y) + f(x,y-1) for x>0, y>x
f(x, x) = f(x-1, x) for x>0
f(0,y) = 1 for y>=0

Edited by author 08.09.2008 03:58

Vedernikoff Sergey (HSE: EconomicsForever!) Re: Please check my program. I got WA [1] // Problem 1619. Big Brother 17 Aug 2008 17:27

Take almost any example and explore it. For example, your formula gives wrong answer on the input k=3 and m=2.

kai_99 Re: Please check my program. I got WA // Problem 1619. Big Brother 17 Aug 2008 17:29

What`s the right answer?

Edited by author 17.08.2008 17:31

Discussion of Problem 1619. Big Brother