All submissions for this problem are available.
Patrix - Number of Patterns possible for a given matrix.
Chef got a supercool smartphone recently. It has an option for Pattern lock. Now Chef wants to find the number of patterns possible connecting P points in a given Matrix of M rows and N columns.
Assume that any number of dots can be connected to arrive at a valid pattern i.e. even a single dot combination is perfectly valid.
The first line takes T, the number of test cases. Each of the test case takes 3 space separated numbers, first one takes M (number of rows), second one takes N (number of columns) and then the third one takes P, the number of dots need to be connected to a get a pattern.
Your program has to print Patrix for every test case in T lines.
While connecting two dots A and B, it is not possible to skip a non-connected dot C, if A,B,C are co-linear and C lies between A and B.
- 0 < T ≤ 101
- 0 < M , N ≤ 101
- 0 < P ≤ MxN
Note: It might not be possible to cover all the values in the pool of permitted numbers due to huge processing time. eg you might not be able to deliver the output for 100 x 100 dot matrix, while 100 x 1 would be possible. Hence, we advise you to optimise your code as much as possible to maximise the number of cases covered.
3 1 2
2 2 2
Test Case 1 : 3 rows, 1 column. The task is to print the number of two-dot combinations possible in a 3 x 1 dot-matrix. Patrix for connecting two dots is 4.
The 1st dot can be connected to the 2nd dot
The 2nd dot can be connected to the 1st dot
The 2nd dot can be connected to 3rd dot and,
The 3rd dot can be connected to the 2nd dot.
Test Case 2 : 2 rows, 2 columns. Patrix for connecting 2 points is, take any one point, it can be connected with three other dots to form a two dot pattern. So for 4 dots 4x3=12.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
Fetching successful submissions
If you are still having problems, see a sample solution here.