Soluție HackerRank pentru Lexicographic paths, subdomeniul Combinatorics, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Lexicographic paths
- Domeniu: Combinatorics
- Limbaj: C++14
Challenge: Lexicographic paths
Subdomeniu: Combinatorics (combinatorics)
Scor cont: 50.0 / 50
Submission status: Accepted
Submission score: 1.0
Submission ID: 464734651
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/lexicographic-steps/problem
Cerință
Krishnakant is standing at (0,0) in the [Cartesian plane](http://en.wikipedia.org/wiki/Cartesian_coordinate_system). He wants to go to the point (x,y) in the same plane using only horizontal and vertical moves of 1 unit. There are many ways of doing this, and he is writing down all such ways. Each way comprises of few H moves and few V moves. i.e. moves in horizontal and vertical direction respectively. For example, if Krishnakant wants to go to point (2,2) from point (0,0), HVHV is one of the possible ways.
Given the value of K, he wants to know lexicographically K-th smallest way of going to (x,y) from (0,0).
Input Format
The first line contains an integer T , i.e., number of test cases.
Next T lines will contain integers x,y and K.
Output Format
For each test case, print lexicographically K-th smallest path.
Constraints
1 ≤ T ≤ 100000
1 ≤ x ≤ 10
1 ≤ y ≤ 10
0 ≤ K < text{number of paths}
Sample Input
2
2 2 2
2 2 3
Sample Output
HVVH
VHHV
Explanation
All the paths of going to (2,2) from (0,0) in lexicographically increasing order:
0. HHVV
1. HVHV
2. HVVH
3. VHHV
4. VHVH
5. VVHH
Cod sursă
//lexicographic-steps.cpp
//Lexicographic paths
//Weekly Challenges - Week 9
//Author: derekhh
#include<cstdio>
using namespace std;
int n, m;
int c[21][21];
void init()
{
for (int i = 1; i <= 20; i++)
{
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++)
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
int main()
{
init();
int t;
scanf("%d", &t);
while (t--)
{
int k;
scanf("%d%d%d", &n, &m, &k);
int cx = 0, cy = 0;
while (cx != n || cy != m)
{
int nH = n - cx, nV = m - cy;
if (nH == 0)
{
printf("V");
cy++;
}
else if (nV == 0)
{
printf("H");
cx++;
}
else
{
int temp = c[nH + nV - 1][nH - 1];
if (k >= temp && temp > 0)
{
printf("V");
k -= temp;
cy++;
}
else
{
printf("H");
cx++;
}
}
}
printf("\n");
}
return 0;
}