CODEWITHSUNDEEP
algorithm
user2980096
user2980096

Reputation: 147

Count number of ways player 1 can win in a 2 player game

I came across this following question,

2 players play a game. In each turn both players receive points in the range -x to +x (both included). Player 1 starts from score p1 and player 2 starts from score p2. If they play a total of k turns, find the total number of ways in which player 1 can win the game i.e at the end of k turns, player 1 has more points than player 2.

So in short my understanding is that we need to find total number of combination set of points for player1 and player2 such that (sum of points set of player 1)-(sum of points set of player 2) >= p2-p1+1

I am not sure how to tackle this problem. Please suggest an approach. Thanks in advance.

Upvotes: 0

Views: 299

Answers (1)

Prune
Prune

Reputation: 77857

Solve this recursively. Using your variables, let's look at the cases:. Let

score_range = [-x : x]

Call the function win_count

Base case, k==1

if k == 1, there is one turn to go. The score difference is p2-p1. If player 2 scores n2 points in this round, then player 1 needs to finish with at least (p2 + n2) - p1 + 1 points this round. Now, how many combinations of that are available with p1, p2 in score_range ? You can compute that directly from the given integers.

Return that count as the functional value.

Recursion case, k > 1

Walk through all of the possible scores for this round. Recur to count possibilities for the remainder of the game.

count = 0
for n1 in score_range
    for n2 in score_range
        count += win_count(p1+n1, p2+n2, k-1, x)

Can you take it from there?

Upvotes: 1

Related Questions