CSE221 Lab 8 Solution

Submission Guidelines
1.You can code all of them either in Python, CPP, or Java. But you should choose a specific language for all tasks.
2.For each task write separate python files like task2.py, task3.py, and so on. For problems that have subproblems, name those like task1A.py, task1B.py, and so on.
3.For each problem, take input from files called
"inputX_Y.txt" and output at "outputX_Y.txt", where X is the task number and Y is the sample i/o number. For example, for problem 2 sample 1, the input file is this, "input2_1.txt". For problems that have subproblems, name the files like "input1a_1.txt", "output1a_1.txt" and so on. Same for output.
4.For each task include at least one input file (if any) in the submission folder.
5.Finally zip all the files and rename this zip file as per this format:LabSectionNo_ID_CSE221LabAssignmentNo_Spring2023.zip [Example:LabSection01_21101XXX_CSE221LabAssignment05_Spring
6.Don't copy from your friends.
7.You MUST follow all the guidelines, naming/file/zipping convention stated above.
Failure to follow instructions will result in a straight 50% mark deduction.
In the kingdom of Beluga, there are N cities connected by M roads, each with a maintenance cost associated with it. There is at least one path between any two cities. The king is concerned about the increasing maintenance cost and decides to take action.
He calls upon his council, and they suggest that they find a minimum-cost set of roads that connects all cities while minimizing the maintenance cost. Then the king decides to reduce the total maintenance cost by destroying some of the existing roads, instead of building new ones.
Since you are a very good programmer the king calls you. He asks you to find out what the lowest maintenance cost can be achieved after destroying a few roads while ensuring there still exists a path from each city to another.
Input
The first line of the input contains two space-separated integers, N and M (1 ≤ N ≤ 10^5, 1 ≤ M ≤ 10^6), representing the number of cities and roads in the kingdom of Beluga, respectively.
The next M lines each contain three space-separated integers, u, v, and w (1 ≤ u, v ≤ N, 1 ≤ w ≤ 10^9), where u and v denote the endpoints of a road and w represents its maintenance cost.
Output
The output should contain a single integer, the minimum total maintenance cost achievable.
Sample Input/Output:
Sample Input 1 Sample Output 1 Sample Graph 1
5 7
1 2
1 3
1 4
2 3
2 5
3 44 5 10
8
6
7
7
12
9 28
Samp le Input 2 Sample Output 2 Sample Graph 2
6 9
1 2
2 4
2 3
1 3
4 3
2 6
2 5
5 6
5 1 6
5
4
8
4
1
3
2
7 17
Once upon a time, there was a small frog named Freddy. Freddy was always fascinated by the stairs that led up to the top of the nearby hill. The stairs had N steps and Freddy dreamed of climbing all the way to the top.
Initially, Freddy is standing at the 0th stair. The only way to reach there is by climbing one or two steps at a time.
Can you write a code to determine the number of distinct ways in which the frog can climb from the 0th step to the Nth step?
Input
An integer N representing the total number of stairs (1 <= N <=
50).
Output
An integer representing the number of distinct ways in which the frog can climb from the 0th step to the Nth step.
Sample Input/Output:
Sample Input 1 Sample Output 1
3 3
Sample Input 2 Sample Output 2
4 5
Sample Input 3 Sample Output 3
5 8
Sample Input 4 Sample Output 4
50 20365011074
Sample Input Explanation:
In the first test case, there are three ways to climb the stairs i.e. {1,1,1} , {1,2} and {2,1}.
In the second test case, there are five ways to climb the stairs i.e. {1,1,1,1} , {1,1,2} , {2,1,1} , {1,2,1} , {2,2}.
Hint:
Can you relate the recurrence relation of this problem to
Fibonacci Numbers?
You have to find the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
Input Format:
The first line contains two integers N and X, where N (1 ≤ N ≤
10^3) represents the number of different coin denominations and amount(1 ≤ X ≤ 10^4) represents the target amount of money.
The second line contains N integers C1,C2 ,....,CN(1 ≤ Ci ≤ 10^4), representing the different coin denominations.
Output Format:
Output a single integer, the minimum number of coins required to make up the target amount. If it is not possible to make up the target amount using the given denominations, output -1.
Sample Input/Output:
Sample Input 1 Sample Output 1
3 11 1 2 5 3
Sample Input 2 Sample Output 2
2 11
2 5 4
Sample Input Explanation:
In the first test case, we can take 1,5,5 to make 11.
In the second test case, we can take 2,2,2,5 to make 11.