Daddy's Journey to Platinum

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out. 

Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

A single line with the three integers A, B, and C.

A single line with a sorted list of all the possible amounts of milk that can be in bucket C when 
bucket A is empty.

8 9 10

1 2 8 9 10

water jug problem 이라고 불리는 물통 사이에서 물을 옮기는 문제이다. 여기서는 물통 3개를 이용하므로, 3 water jug problem이라고 할 수 있다. 시작할때 가지고 있는 물의 양(0, 0, C)에서 물통 사이에서 한번에 옮길 수 있는 6가지 경우들을 재귀적으로 검색한다. 한번 검색한 곳은 다시 검색하지 않도록 확인해서, 검색을 종료하도록 한다. 문제 조건에 따라서 물통 A가 비어 있을때 물통 C의 양을 기록해서 출력한다.

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)

You are given an array containing n positive integers.

Your task is to divide the array into k subarrays so that the maximum sum in a subarray is as small as possible.

The first input line contains two integers n and k: the size of the array and the number of subarrays in the division.

The next line contains n integers x_1,x_2,…,x_n: the contents of the array.

Print one integer: the maximum sum in a subarray in the optimal division.

5 3
2 4 7 3 5

8

Explanation: An optimal division is [2,4],[7],[3,5] where the sums of the subarrays are 6,7,8. The largest sum is the last sum 8.

• 1 <= n <= 2x10^5 
• 1 <= k <= n 
• 1 <= x_i <= 10^9

입력받은 수열의 합과 최대값을 기록한다.

수열을 가장 작은 크기로 분할하는 것은 모두 1개씩으로 분할 하는 것이다. 이때는 수열 내 원소의 최대값을 출력한다. 가장 크게 분할하면 전체를 하나로 분할하는 경우이므로, 수열의 합을 출력한다.

나머지 분할에서 나오는 값들은 이 두 값의 사이에 존재하게 되므로, high/low로 생각하고 중간값들로 분할 가능한지 확인해서, 가능한 경우에서 최소값을 출력한다.

Given an array of n integers, your task is to count the number of subarrays where the sum of values is divisible by n.

The first input line has an integer n: the size of the array.

The next line has n integers a_1,a_2,…,a_n: the contents of the array.

Print one integer: the required number of subarrays.

5
3 1 2 7 4

1

• 1 <= n <= 2x10^5
• - 10^9 <=  a_i <= 10^9

배열의 입력값을 modulo 연산을 해서 더한 값을 저장한다. 이 값들은 입력하기 전에 한번더 modulo 연산을 하도록 하고, 음수인 경우는 양수가 되도록 한다. 이렇게 만들어진 값들을 map에 입력해서, 이 합의 배열의 차가 0이 되는 경우의 수를 센다. 

Given an array of n integers, your task is to count the number of subarrays having sum x.

The first input line has two integers n and x: the size of the array and the target sum x.

The next line has n integers a_1,a_2,…,a_n : the contents of the array.

Print one integer: the required number of subarrays.

5 7
2 -1 3 5 -2

2

• 1 <= n <= 2x10^5
• −10^9 <= x, a_i <= 10^9

배열을 입력 받아서, 그 값들을 누적하고, 이렇게 만들어진 합들을 key 로 하는 map을 만든다. 

pre_sum[i] == tSum or pre_sum - tSum == pre_sum[j] 인 경우가 우리가 찾는 sub-array가 된다.

이런 경우들을 세서 출력한다.