Algorithms

There are N cities in a state. You start your ride from the first city.
You have to visit all other cities exactly once and finally return to your origin city. After visiting each city, you collect the analysis report.
But when you reached the last unvisited city, you remembered that you did not collect the report from city K. So, now you decide to first collect the report from city K and then return to your home city.
Given the distances between each pair of cities, you are required to find the shortest possible distance of your whole journey.

INPUT

The input begins with T (Number of test cases).
Second line contains K (City No. Where you forgot to collect the report).
Third line contains N (Number of cities).
Next there are N lines, line have exactly N numbers denoting distance from city I to all N cities.

OUTPUT

For each test case, print the Minimum Distance of total journey.
Answer for each test case should come in a new line.

CONSTRAINTS

 

You are given a number $$X$$. You have to obtain the number $$X$$ starting from 0 by performing the following operations:

• Add or subtract 1 to the current number. The cost is $$A$$ units.
• Double the current number. The cost is $$B$$ units.

Without making the number negative at any time, find the minimum cost of obtaining the number $$X$$ when starting from 0.

Note:
The Current number cannot be negative at any time.

Input format

• The first line consists of a number $$T$$(the number of test cases).
• Then $$T$$ lines follow and each line has $$3$$ space-separated integers $$X$$,$$A$$ and $$B$$.

Output format

Print $$T$$ lines where each line consists of $$1$$ integer denoting the minimum cost.

Constraints

You are given a cubic dice with 6 faces. All the individual faces have a number printed on them. The numbers are in the range of 1 to 6, like any ordinary dice. You will be provided with a face of this cube, your task is to guess the number on the opposite face of the cube.

Example 1: Example 2:

Given a string you need to print all possible strings that can be made by placing spaces (zero or one) in between them. The output should be printed in sorted increasing order of strings

Example 1:

 

Example 2:

Your Task:  
You don't need to read input or print anything. Your task is to complete the function permutation() which takes the string S as input parameters and returns the sorted array of the string denoting the different permutation (DON'T ADD '(' and ')' it will be handled by the driver code only).

Expected Time Complexity: O(2^n)
Expected Auxiliary Space: O(1)

 

CONSTRAINTS:
1 < |S| < 10
S only contains lowercase and Uppercase English letters.

Given a String S, Find all possible Palindromic partitions of the given String.

Example 1:

Your Task:
You don't need to read input or print anything. Your task is to complete the function allPalindromicPerms() which takes a String S as input parameter and returns a list of lists denoting all the possible palindromic partitions.

 

Expected Time Complexity: O(N*2^N)
Expected Auxiliary Space: O(N²), where N is the length of the String

 

Constraints:
1 <= |S| <= 20

Swap given two numbers and print them. (Try to do it without a temporary variable.) and return it.

Example 1:

Example 2:

Your Task:  
You don't need to read input or print anything. Your task is to complete the function get() which takes a, b as inputs and returns the list of integers contains the new value of a and b after swap.

Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)

Constraints:
1 ≤ a, b ≤ 10⁶

Given the maximum possible area of the right angle triangle for a fixed length of hypotenuse. The task is to find the length of hypotenuse.

Note: If the answer comes in Decimal, find it's Floor value.

Example 1:
Example 2:

Your Task:
You don't need to read input or print anything. Your task is to complete the function getHypotenuse() which takes an Integer N as input and returns the answer.

Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)

Constraints:
1 <= N <= 10¹⁰

Print the multiplication table of a given number N. 

Example 1:

Example 2:

Your Task:  
You don't need to read input. Your task is to complete the function getTable() which takes an integer N as input parameter and returns a list of integers denoting the multiplication of table of N from 1 to 10. 

Expected Time Complexity: O(1)
Expected Auxiliary Space: O(1)

Constraints: 
1 <= N <= 10000

Consider a game where a player can score 3 or 5 or 10 points in a move. Given a total score n, find number of distinct combinations to reach the given score.

Input:
The first line of input contains an integer T denoting the number of test cases. T testcases follow.The first line of each test case is n.

Output:
For each testcase, in a new line, print number of ways/combinations to reach the given score.

Constraints:
1 ≤ T ≤ 100
1 ≤ n ≤ 1000

Example:

Given a A X B matrix with your initial position at the top-left cell, find the number of possible unique paths to reach the bottom-right cell of the matrix from the initial position.

Note: Possible moves can be either down or right at any point in time, i.e., we can move to matrix[i+1][j] or matrix[i][j+1] from matrix[i][j].

Example 1:

Example 2:

Your Task:
Complete NumberOfPath() function which takes 2 arguments(A and B) and returns the number of unique paths from top-left to the bottom-right cell.

Expected Time Complexity: O(A*B).
Expected Auxiliary Space: O(A*B).

Constraints:
1 ≤ A ≤ 15
1 ≤ B ≤ 15