Saturday, 25 July 2015

FUNPROB

Standard

Yanu in Movie theatre

Link to the question : FUNPROB 

RECOMMENDED QUESTION :

Try solving this question after solving this.

SOURCE CODE :

#include<stdio.h>
int main()
{
     int m=1,n=1;
     double x,y;
     while(m!=0 && n!=0)
     {
         scanf("%d%d",&n,&m);
         if(n!=0 && m!=0)
         {
             if(n>m || m==0)
                printf("0.000000\n");
             else if(n==0)
                printf("1.000000\n");
             else
             {
                 x=m;
                 y=n;
                 printf("%.6lf\n",(x-y+1.0)/(x+1.0));
             }

         }
     }
     return 0;
}

3 comments:



  1. At first it is obvious that if N>M probability is zero.

    now I want to use indication on N to prove. consider M>0 I want to prove for every N=<M we have res = (M-N+1) / (M+1) for N=0 it is obvious that probability is 1.

    For N=1 put every body with 5$ in a queue in arbitrary order, now for the one person with 10$ you could put him every where except in front of the queue so you have between M+1 places that are available you have M+1-1 choices. so for N=1 you have : res = (M-1+1) / (M+1)

    suppose formula is correct for every N=<k I want to prove that if N=k+1 formula is still correct. for that put M people with 5$ and k people with 10$ in a arbitrary queue. we suppose that res = (M-K+1) / (M+1) is the probability of working this queue and every body could have his ticket. consider one of the working queues in this queue if a 10$ person is behind 5$ person remove both of them and do this recursively until there is no 5$ person. this will work because as I said above the first person of the queue is a 10$ one, and also I said that N<M the probability of putting the K+1 person in the queue is choosing one place among M-k+1 because we remove k 10$ person from the queue. and it is like what we said for N=1 so we have probability of putting K+1th 5$ person in the queue is : ((M-k) - 1 +1) / ((M - k) +1)(*) and by indication we have that probability of a working queue for N=k is : (M-k +1) / (M +1)( * ) from () and ( * *) we have probability of putting K+1 people with 10$ and M people with 5$ in a queue with questions condition is :

    [((M-k) - 1 +1) / ((M - k) +1)] * [(M-k +1) / (M +1)] = ((M-k) - 1 +1) / (M +1) = (M-(k+1) +1) / (M +1)

    And it is end of the proof :).

    ReplyDelete
  2. Your proof is kinda complicated. I'd suggest you to look up a special case of Bertrand Ballot Theorem where tie is possible. Thanks anyway.

    ReplyDelete