You have types of coins available in infinite quantities where the value of each coin is given in the array . Can you determine the number of ways of making change for units using the given types of coins? For example, if , and , we can make change for units in three ways: , , and .
Given , , and , print the number of ways to make change for units using any number of coins having the values given in .
Input Format
The first line contains two space-separated integers describing the respective values of and .
The second line contains space-separated integers describing the respective values of (the list of distinct coins available in infinite amounts).
Constraints
Each is guaranteed to be distinct.
Hints
Solve overlapping subproblems using Dynamic Programming (DP):
You can solve this problem recursively but will not pass all the test cases without optimizing to eliminate the overlapping subproblems. Think of a way to store and reference previously computed solutions to avoid solving the same subproblem multiple times.
Consider the degenerate cases:
How many ways can you make change for cents?
How many ways can you make change for cents if you have no coins?
If you're having trouble defining your solutions store, then think about it in terms of the base case .
The answer may be larger than a -bit integer.
Output Format
Print a long integer denoting the number of ways we can get a sum of from the given infinite supply of types of coins.
Sample Input 0
4 31 2 3
Sample Output 0
4
Explanation 0
There are four ways to make change for using coins with values given by :
Thus, we print as our answer.
Sample Input 1
10 42 5 3 6
Sample Output 1
5
Explanation 1
There are five ways to make change for units using coins with values given by :
Thus, we print as our answer.
#!/bin/python
import sys
def getWays(n, c):
arr = [0 for h in range(n+1)]
arr[0] = 1
for k in c:
for i in range(1,n+1):
if n>=k:
if i>=k:
arr[i] += arr[i-k]
return arr
# Complete this function
n, m = raw_input().strip().split(' ')
n, m = [int(n), int(m)]
c = map(long, raw_input().strip().split(' '))
# Print the number of ways of making change for 'n' units using coins having the values given by 'c'
ways = getWays(n, c)
print ways[-1]
A series is defined in the following manner: Given the nth and (n+1)th terms, the (n+2)th can be computed by the following relation T(n+2) = (Tn+1)^2 + T(n) So, if the first two terms of the series are 0 and 1: the third term = 1^2 + 0 = 1 fourth term = 1^2 + 1 = 2 fifth term = 2^2 + 1 = 5 ... And so on. Given three integers A, B and N, such that the first two terms of the series (1st and 2nd terms) are A and B respectively, compute the Nth term of the series. Input Format You are given three space separated integers A, B and N on one line. Input Constraints 0 <= A,B <= 2 3 <= N <= 20 Output Format One integer. This integer is the Nth term of the given series when the first two terms are A and B respectively. Sample Input : 0 1 5 Output : 5 Solution #!/bin/python t1,t2,n = map(int,raw_input().split()) for i in range(1,n-1): ans = t1 + t2**2 t1 = t2 t2= ans print(ans)
Consider two non-negative long integers, a and b , where a<= b . The bitwise AND of all long integers in the inclusive range between a and b can be expressed as a & (a + 1) & ... & (b - 1) & b, where & is the bitwise AND operator.
Given an array of integers, find and print the maximum number of integers you can select from the array such that the absolute difference between any two of the chosen integers is . Input Format The first line contains a single integer, , denoting the size of the array. The second line contains space-separated integers describing the respective values of . Constraints The answer will be . Output Format A single integer denoting the maximum number of integers you can choose from the array such that the absolute difference between any two of the chosen integers is . Sample Input 0 6 4 6 5 3 3 1 Sample Output 0 3 Explanation 0 We choose the following multiset of integers from the array: . Each pair in the multiset has an absolute difference (i.e., and ), so we print the number of chosen integers, , as our answer. Sa...
Comments
Post a Comment