ronith
11/11/2018 - 6:52 AM

Volleyball Match

If you are not familiar with the rules of volleyball, here's a brief:

  • 2 teams play in total
  • During the course of the game, each team gets points, and thus increases its score by 1.
  • The initial score is 0 for both teams. The game ends when
  • One of the teams gets 25 points and another team has < 24 points ( strictly less than 24).
  • If the score ties at 24:24, the teams continue to play until the absolute difference between the scores is 2. Given the final score of a game in the format A:B i.e., the first team has scored A points and the second has scored B points, can you print the number of different sequences of getting points by teams that leads to this final score?

Solution: At first, there are a few tricky cases that should be considered. The answer in each of these cases is 0

A = 24, B = 25, or vice versa. The game hasn't ended in this case. The both A and B are less than 25. A = B One of the teams's scores is greater than 25 and the difference between the teams' scores is different from 2. After checking these cases, let's calculate a number of games that has the intermediary score of X : Y over all the possible pairs (X, Y) where the both X and Y are not greater than 25. Let's name it S(X, Y). By intermediary we mean the the game doesn't have to be ended with this score (but this score CAN correspond to some ended game, as well).

We can calculate S(X, Y) using the recurrent formula: S(X, Y) = S(X - 1, Y) + S(X, Y - 1) in the general case, starting with S(0, 0) = 1. As we can see, it's quite similar to the Pascal Triangle, so we can use the number of combinations instead of the recurrent formula. Nevertheless, the writer of the problem considers recurrent formula the simplest solution.

Now, if both A and B aren't greater than 25, we can just output the value of S(A-1, B) or S(A, B-1) (depending on who is the winner of the game) modulo 109 + 7.

What happens if A or B (or both) are greater than 25. That means the the score of 24 : 24 was reached during the game. Then, the score of 25 : 25 was also reached. Otherwise it would mean that the game ends with the score of 24 : 26 or 26 : 24. There are two ways to reach 25 : 25 from 24 : 24. Then, the score of 26 : 26 was also reached, and again there're two ways to go from 25 : 25 to 26 : 26. This goes on, till the score of min(A, B) : min(A, B) is reached. Then, one of teams gains two points in a row and the game ends. There are always two ways to get C : C from C-1 : C-1.

So, according to the simplest combinatorial rules, if max(A, B) is greater than 25, the answer is S(24, 24) * 2min(A, B) - 24.

Volleyball Match.cpp
content_copyfile_download
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define mod 1000000007


int pow (int n) {
    if (!n)
        return 1;
    if (n== 1)
        return 2;
    int q= pow(n/2);
    q= (1LL*q*q)%mod;
    if (n%2)
        return (q+q)%mod;
    return q;
}

int main() {
    int a, b;
    cin>>a>>b;
    
    if (a<b)
        swap(a,b);
    if ((a<25&&b<25)|| (a>25 && a-b!= 2) || (a== 25 && b==24) || (a== b)) {
        cout<< "0\n";
        return 0;
    }
    int dp[26][26];
    dp[0][0]= 1;
    for (int i=0;i<26;i++) {
        for (int j=0;j<26;j++) {
            if (i+j) {
                dp[i][j]= 0;
                if (i>0)
                    dp[i][j]+= dp[i-1][j];
                if (j)
                    dp[i][j]+= dp[i][j-1];
                dp[i][j]%= mod;
            }    
        }
    }
    if (a== 25) {
        cout<< dp[a-1][b]<<endl;
        return 0;
    }
    int ans= dp[24][24];
    ans= (1LL*ans*pow(b-24))%mod;
    cout<<ans<<endl;
    
}