Daddy's Journey to Platinum

The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin thrown in for good measure.
The cows want to know how many different ways it is possible to dispense a certain amount of money using various coin systems. For instance, using a system of {1, 2, 5, 10, ...} it is possible to create 18 units several different ways, including: 18x1, 9x2, 8x2+2x1, 3x5+2+1, and many others.
Write a program to compute how many ways to construct a given amount of money using supplied coinage. It is guaranteed that the total will fit into both a signed long long (C/C++) and Int64 (Free Pascal).

The number of coins in the system is V (1 <= V <= 25).
The amount money to construct is N (1 <= N <= 10,000).

Line 1: Two integers, V and N
Lines 2..: V integers that represent the available coins (no particular number of integers per line)

A single line containing the total number of ways to construct N money units using V coins.

3 10 
1 2 5

10

특정한 정수 집합으로 원하는 값을 만들어내는 경우의 수를 세는 문제로 coin change 문제이다. 

특정한 코인 값 c[i] =a 라고 하면, 원하는 값 target 를 만들 수 있는 방법은 이 코인이 없이 만들수 있는 경우의 수와 이 코인 값을 제외한 값을 만들수 있는 경우의 수의 합이 된다. 

 v(target, b) = v(target, a) + v(target-b, b) 

다만, 이 경우에는 코인의 수는 제한이 없기 때문에, 코인 값의 배수들에 해당하는 값들을 모두 확인해야 한다.

참고: subset sum problem ( link )

For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical. 

For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets
are identical:

• {3} and {1,2}

This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and
thus does not increase the count of partitions).
If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same
sum:

• {1,6,7} and {2,3,4,5}
• {2,5,7} and {1,3,4,6}
• {3,4,7} and {1,2,5,6}
• {1,2,4,7} and {3,5,6}

Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways. 

Your program must calculate the answer, not look it up from a table.

The input file contains a single line with a single integer representing N, as above.

The output file contains a single line with a single integer that tells how many same-sum partitions can be made from the set {1, 2, ..., N}. The output file should contain 0 if there are no ways to make a same-sum partition.

7

4

{1, 2, ..., N} 인 집합을 합이 같은 2개의 집합으로 나누는 경우의 수를 구하는 문제이다. 전체의 합은 N*(N+1)/2 이고 이것을 2개의 같은 값으로 나누는 것이기 때문에 N*(N+1)/4 = k. 즉, N % 4 = 0 or -1(3) 인 경우만 가능하다. 

이 경우의 수는 조건에 맞는 모든 부분집합을 찾아서 그 수를 구할 수 있다. N = 4K 인 경우는 A = { (1, 4), (5,8), ..., (4K+1, 4K+4)}, B = { (2, 3), (6,7), ... , (4K+2, 4K+3)} 의 두 집합으로 나눈뒤 한쪽의 특정한 값을 가진 수의 조합을 다른 쪽에서 같은 값을 가진 조합으로 변경해서, 다른 집합들을 찾을 수 있다. N = 4K+3 인 경우는 A = { (1,2), (5,5), ... (4K+1, 4K+2)}, B = { (0,3), (4, 7), ... , (4K, 4K+3)}으로 초기 집합을 나눌 수 있다.

부분 집합들을 직접 찾지 않고, 아래 같은 규칙을 이용해서 경우의 수를 세는 것도 가능하다.  다만 어떤 부분 집합이 가능한지는 알 수 없다.

A(i+1, K) 의 값은 새로운 수 (i+1)이 원하는 합을 만드는데 사용한 경우< A(i+1, K-(i+1))>와 사용하지 않는 경우<A(i, K)>의 합이 된다.  A(i+1, K) = A(i, K) + A(i+1, K-(i+1))

이 값들을 구하는데,  A(0,0) = 1. (empty set), A(k, 0) = 1(empty set) 을 가지고 시작해서 완성한다.

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum xx using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways:

• 2+2+5 
• 3+3+3 
• 2+2+2+3

The first input line has two integers n and x: the number of coins and the desired sum of money.

The second line has n distinct integers c_1,c_2,…,c_n: the value of each coin.

Print one integer: the number of ways modulo 10^9+7 

3 9
2 3 5

3

• 1 <= n  <= 100
• 1 <= x <= 10^6 
• 1 <= c_i <= 10^6

특정한 값(a)을 만드는 경우의 수를 dp(a) 라고 하고, 특정한 코인의 값을 coin(b)라고 하면, 코인 coin(b)를 추가해서 a값을 완성하는 경우와 사용하지 않고 완성하는 경우의 합으로 계산할 수 있다. 

dp(a, b) = dp(a, 0) + dp(a - coin(b)) 

0 값을 만드는 방법은 아무것도 고르지 않는 empty set의 한가지 경우 밖에 없으므로, dp(0) = 1이 된다. 

또, dp(coin(a)) = 1, 특정 코인 1개로 표현할 수 있는 방법 1에서 다른 경우들을 완성해서 목표로 하는 값을 찾는 문제이다. 

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 8 ways: 

• 2+2+5 
• 2+5+2 
• 5+2+2 
• 3+3+3 
• 2+2+2+3 
• 2+2+3+2 
• 2+3+2+2 
• 3+2+2+2

The first input line has two integers n and x: the number of coins and the desired sum of money.

The second line has n distinct integers c_1,c_2,…,c_n : the value of each coin.

Print one integer: the number of ways modulo 10^9+7

3 9
2 3 5

8

• 1 <= n <= 100 
• 1 <= x <= 10^6 
• 1 <= c_i <= 10^6

특정한 값을 만드는 경우의 수는 코인의 값을 포함하는 경우와 포함하지 않는 경우를 더하면 된다.

먼저, 초기 값으로 목표값이 0인 경우는 아무런 코인도 고르지 않는 empty set 한가지가 된다. (dp[0] = 1)  새로운 코인 값과 기존의 값이 목표값 보다 작은 모든 경우들을 합하면 목표값을 만드는 경우의 수가 된다.

목표값이 xValue가 될때까지 dp[]를 완성하면, dp[xValue] 이 원하는 경우의 수가 된다.

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to produce a sum of money x using the available coins in such a way that the number of coins is minimal.

For example, if the coins are {1,5,7}  and the desired sum is 11, an optimal solution is 5+5+1 which requires 3 coins.

The first input line has two integers n and x: the number of coins and the desired sum of money.

The second line has n distinct integers c_1,c_2,…,c_n: the value of each coin.

Print one integer: the minimum number of coins. If it is not possible to produce the desired sum, print -1.

3 11
1 5 7

3

• 1 <= n <= 100
• 1 <= x <= 10^6
• 1 <= c_i <= 10^6

코인의 종류와 목표값을 입력 받고, 코인들의 값을 입력 받는다. 목표값이 0인 경우 최소 코인은 0개가 되고, 목표값이 특정한 코인의 값과 같은 경우에 필요한 코인 최소 개수는 1개가 된다.  목표값을 1 부터 x 까지 이동해가면서 코인들을 포함 시키는 경우들에 대해서 검사해서 값을 변경한다. dp[x] 가 원하는 값이 된다. 

(dp[target], coin[j]) check dp[target-coin[j]] >0 

• dp[target] == initial value(-1) -> dp[target] = dp[target-coin[j]] + 1 
• dp[target] != initial value -> compare min(dp[target], dp[target-coin[j]] +1)

Your task is to count the number of ways to construct sum n by throwing a dice one or more times. Each throw produces an outcome between 1 and 6.

For example, if n=3, there are 4 ways:

• 1+1+1 
• 1+2 
• 2+1 
• 3

The only input line has an integer n.

Print the number of ways modulo 10^9+7.

3

4

1 <= n <= 10^6

주사위를 한번 던져서 나올 수 있는 수는 1~6까지 6가지 경우가 있으므로, 어떤 수 N을 만들기 위해서, 그 전까지 나왔던 경우의 수 (N-1) ~ (N-6)까지 합이 N을 만들 수 있는 경우의 수가 된다.

초기 조건으로 0~5까지 6개의 경우를 입력하고, 6 이상인 경우는 더해서 modulo 연산을 하고,  N이 1~5 인 경우는 초기 조건에서 출력한다.