Daddy's Journey to Platinum

Farmer John prides himself on having the healthiest dairy cows in the world. He knows the vitamin content for one scoop of each feed type and the minimum daily vitamin requirement for his cows. Help Farmer John feed the cows so they stay healthy while minimizing the number of scoops that a cow is fed.
Given the daily requirements of each kind of vitamin that a cow needs, identify the smallest combination of scoops of feed a cow can be fed in order to meet at least the minimum vitamin requirements.
Vitamins are measured in integer units. Cows can be fed at most one scoop of any feed type. It is guaranteed that a solution exists for all contest input data.

Line 1: integer V (1 <= V <= 25), the number of types of vitamins

Line 2: V integers (1 <= each one <= 1000), the minimum requirement for each of the V vitamins that a cow requires each day

Line 3: integer G (1 <= G <= 15), the number of types of feeds available

Lines 4..G+3:
V integers (0 <= each one <= 1000), the amount of each vitamin that one scoop of this feed contains. The first line of these G lines describes feed #1; the second line describes feed #2; and so on.

The output is a single line of output that contains:
 - the minimum number of scoops a cow must eat, followed by:
 - a SORTED list (from smallest to largest) of the feed types the cow is given

4
100 200 300 400
3
50 50 50 50
200 300 200 300
900 150 389 399

2 1 3

모든 feed를 한번씩만 줄 수 있으므로, 전체 feed에서 가능한 모든 조합을 찾아서, 최소화 되는 조합을 출력한다.  feed 의 종류가 많지 않으므로( <= 15), bitset을 이용해서 필요한 조합을 찾는다. bitset<16> (0), ... bitset<16> (1<<numG) 다만, bitset으로 설정된 조합에서 작은 수들이 먼저 나오는 조합은 숫자로 변경하면, 더 큰 수가 된다.

자물쇠 숫자 3개를 tuple<int, int, int>로 처리하고, 숫자 사이의 차이를 abs 이용해서 계산한다. 다만, modulo 연산에서 -를 지원하지 않기 때문에 dial number - 2 ( modulo -2) 보다 큰 경우도 고려한다. 3중 루프를 O(N^3)이지만 최대 dial number 100 을 생각하면, 속도에 문제가 될 것 같지는 않다. 필요하다면, key number 에서 5x5x5 로 가능한 숫자 배열을 작성하고, 그 배열 숫자들로만 루프를 돌리면 좀 더 빨라질 것 같다. 중복 제거를 위해서 set 에 무조건 입력하고, 중복이 제거된 결과의 수만 조회 했는데, 입력하기 전에 조회를 하고 없으면 입력하도록 하는것도 방법이 될 수는 있을 것 같다. 효율성은 find를 하고 없으면 입력하는것이 조금은 더 좋을 것 같다.

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) 을 가지고 시작해서 완성한다.