def C(n, r): ans = f(n) / f(r) / f(n-r) return ans

def solve(x, y, k): ans = "" while k > 0: if k < C(x+y-1, y): ans += "H" x -= 1 else: ans += "V" k -= C(x+y-1, y) y -= 1 ans += x * "H" ans += y * "V" return ans

C++

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

ll nCr(ll n, ll k){
    if(n==0 && k==0) return 0;
    ll res = 1;
    if ( k > n - k )
        k = n - k;
    for (ll i = 0; i < k; ++i){
        res *= (n - i);
        res /= (i + 1);
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1;
    cin>>t;
    ll x, y, k;
    while(t--){
        cin>>x>>y>>k;
        while(1){
            if(x==0 && y==0) break;
            else if(x==0){
                cout<<"V";
                y--;
            }
            else if(y==0){
                cout<<"H";
                x--;
            }
            else {
                if(nCr(x+y-1, x-1) > k){
                    x--;
                    cout<<"H";
                }
                else {
                    k = k - nCr(x+y-1, x-1);
                    y--;
                    cout<<"V";
                }
            }
        }
        cout<<"\n";
    }
    return 0;
}

Iterative solution. The first lexigraphic solution is always x 'H's followed by y 'V's. If we consider when the leftmost V moves left, for y = 2 it's 1,3,6,10,15..., for y=3 it's 1,4,10,20,35... In general it's the yth figurate number. Figurate numbers are choose(n+y - 1, y) so the reason for this should be apparent (the leftmost V moves after all combinations to its right are exhausted).

The V's to the right follow the same pattern, repeated every time the V to the left moves.

So, solution is find maximum yth figurate number less than k. The index of this number tells us where the leftmost V is. Subtract that from k. Then find maximum y-1st figurate number less than the remainder, and so on.

13, 14, 15, 16 timed out.

Any clue on this ??

include

int X, Y, order, odr, limit, bfound= 0;

int f[50];

void calAns(int idx, int x, int y);

void init();

void init()

{

int i;

order = 0;

odr = 0;

limit = 0;

bfound = 0;

for(i = 0; i<50; i++)

    f[i] = 0;

}

int main()

{

int T, tc;

scanf("%d",&T);

for(tc = 1; tc<= T; tc++)

{

    init();

    scanf("%d",&X);

    scanf("%d",&Y);

    scanf("%d",&order);

    limit = X + Y;

    calAns(0, 0, 0);

}

return 0;

}

void calAns(int idx, int x, int y)

{

int i;

if(x == X && y == Y)

{

    if(odr == order)

    {

        for(i = 0; i < limit; i++)

        {

            if(f[i])

                printf("H");

            else

                printf("V");

        }

        printf("\n");

        bfound = 1;

    }

    odr++;

    return;

}

if(x > X || y > Y)
    return;

if(bfound == 0){
    f[idx] = 1;
    calAns(idx+1, x+1, y);
    f[idx] = 0;
    calAns(idx+1, x, y+1);
}

}

reminds me of a question on project euler :P