Proficient.
Put your skills to the test.

Problem summary

Two distinguishable counters A and B start on squares n−1 and n of a strip. A move shifts one counter one square left into a free square. Count the move sequences ending with A at p and B at q.

Constraints

1 ≤ p < q ≤ n ≤ 16.

Worked example

An independently prepared example for this explanation.

1 3 4

2

Solution analysis

1. Let dp[a][b] count sequences reaching the ordered positions a<b. Initialize dp[n−1][n]=1. A can move to a−1 while a>p; B can move to b−1 while b>q and b−1>a.
2. Process a and b in descending order. Both moves decrease a coordinate, so every predecessor is processed before its successors. Add counts to both legal next states.
3. For p=1,q=3,n=4, A needs two moves and B one. AAB and ABA are legal; BAA is blocked on its first move. The answer is 2.

Why it works

Counters never cross, so every reachable state has a<b. The two transitions are precisely the legal moves that do not pass their targets. Any sequence reaching a state has a unique final move from one of its predecessors; adding their counts counts every sequence once. Descending iteration respects the transition order.

Watch out. The counters are distinguishable. B cannot enter A’s square. Use 64-bit counts; even the unrestricted count of at most 28 moves fits.

An independently written complete program with standard headers.

#include<iostream>
using namespace std;
int main(){
    // Compute the exact archive answer using the method explained above.
    int p,q,n;
    cin>>p>>q>>n;
    long long dp[17][17]={};
    dp[n-1][n]=1;
    for(int a=n-1;a>=p;a--){
        for(int b=n;b>=q;b--){
            if(a>=b){
                continue;
            }
            if(a>p){
                dp[a-1][b]+=dp[a][b];
            }
            if(b>q&&b-1>a){
                dp[a][b-1]+=dp[a][b];
            }
        }
    }
    cout<<dp[p][q]<<'\n';
}