Kicstart 2017 Practice Problem B. Vote

Abridged problem statement

In an election where candidate A receives N votes and candidate B receives M votes with N > M, what is the probability that A will be strictly ahead of B throughout the count.

 Problem Statement

Constraints

1 ≤ T ≤ 100

Small dataset

0 ≤ M < N ≤ 10

Large dataset

0 ≤ M < N ≤ 2000

Approach  

This problem is a combinatorics problem which can be solved using the Bertrand's Ballot Theorem. The closed form solution for this problem is

(N - M) / (N + M)

For more information refer to this article Bertrand's ballot theorem.

Code

#include <iostream>
#include <iomanip>
#include <fstream>
using namespace std;
int main(){
  int t, m, n;
  freopen("inputlarge.in", "r", stdin);
  freopen("outputlarge.txt", "w", stdout);
  cin>>t;
  for(int cases = 1; cases <=t; cases++){
    float ans;
    cin>>n>>m;
    ans = 1.0 * (n - m) / (n + m);
    cout<<"Case #"<<cases<<": "<< setprecision(8)<<ans<<endl;
  }
  return 0;
}