Daddy's Journey to Platinum

You have n coins with certain values. Your task is to find all money sums you can create using these coins.

The first input line has an integer n: the number of coins.

The next line has n integers x1,x2,…,xn : the values of the coins.

First print an integer k: the number of distinct money sums.

After this, print all possible sums in increasing order.

4
4 2 5 2

9
2 4 5 6 7 8 9 11 13

1<= n <=100

1<= x_i <= 1000

가능한 최대값은 100*1000 (max_n, max_xi) 이다. 가능한 최대값과 같은 크기의 boolean 배열을 만든다. 각 코인마다 값들을 더해가면서 falst->true 로 변경한다. 만들어진 배열에서 true 경우를 세고, dp[u] == true 이면, u가 가능한 값이 된다.

Given an a×b rectangle, your task is to cut it into squares. On each move you can select a rectangle and cut it into two rectangles in such a way that all side lengths remain integers. What is the minimum possible number of moves?

The only input line has two integers a and b.

Print one integer: the minimum number of moves.

3 5

3

1 <= a, b <= 500

모두 정사각형이 되도록 직사각형을 자를때 최소 횟수를 구하는 문제이다. 가로로 자르는 경우와 세로로 자르는 경우로 나눠서 각각 한번 자를때마다, 최소값들을 갱신한다.

The edit distance between two strings is the minimum number of operations required to transform one string into the other.

The allowed operations are:

• Add one character to the string.
• Remove one character from the string.
• Replace one character in the string.

For example, the edit distance between LOVE and MOVIE is 2, because you can first replace L with M, and then add I.

Your task is to calculate the edit distance between two strings.

The first input line has a string that contains n characters between A–Z.

The second input line has a string that contains m characters between A–Z.

Print one integer: the edit distance between the strings.

LOVE
MOVIE

2

1 <= n,m <= 5000

두개의 문자열을 행과 열로 하는 테이블을 생각한다. src[i] == dest[j]는 변경할 필요가 없으며 값을 변경하지 않아도 된다. 문자열이 다르면, dist[i][j] = min({dist[i][j-1], dist[i-1][j], dist[i-1][j-1]) + 1 로 계속 변경해서 테이블을 완성한다.

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으로 설정된 조합에서 작은 수들이 먼저 나오는 조합은 숫자로 변경하면, 더 큰 수가 된다.

4개의 점으로 만들어진 사각형에 점을 추가해서 새로운 사각형을 만드는 과정을 진행한다. 점을 추가하는 규칙은 사각형의 중앙과 각 변의 중앙에 추가한다. 이 과정을 N번 시행한후 점의 수를 출력한다.

N

N번의 과정이후의 점의 수

1

9

1 <= N  <= 15

각 과정에서 늘어나는 사각형의 수, 변의 수, 점의 수들을 단계적으로 계산한다.

- 새로운 사각형은 원래 있던 사각형*4가 된다.

- 새로운 변은 원래 있던 변의 수*2(변의 중점으로 인한 분할) + 사각형*4 (면의 중점과 각변을 연결하는 선)

- 새로운 점은 각 변의 수(새로운 중점)와 사각형의 수(중점) 만큼 추가된다.  

You know that an array has n integers between 1 and m, and the difference between two adjacent values is at most 1.

Given a description of the array where some values may be unknown, your task is to count the number of arrays that match the description.

The first input line has two integers n and mm: the array size and the upper bound for each value.

The next line has n integers x_1,x_2,…,x_n : the contents of the array. Value 0 denotes an unknown value.

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

3 5
2 0 2

3

Explanation: [2,1,2], [2,2,2] , and [2,3,2]

• 1 <= N <= 10^5
• 1 <= M <= 100
• 0 <= x_i <= M 

배열에서 어떤 위치의 숫자는 바로 전 위치의 숫자 값에 따라서 결정된다(+1, -1, 0). 이렇게 가능한 경우의 배열을 x_0 부터 x_n-1까지 계속해서 더해서 만든다. 단, 이렇게 더하는 과정에 커지는 숫자는 modulo 연산으로 일정하게 만든다.

You are in a book shop which sells n different books. You know the price and number of pages of each book.

You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy each book at most once.

N X // Number of books, maximum total price

h_i // books price

s_i // number of pages

the maximum number of pages.

4 10
4 8 5 3
5 12 8 1

13

• 1<= N <= 1000
• 1<= X <= 1e5
• 1<= h_i, s_i <= 1000 

Knapsack 문제이다. 어떤 특정한 책을 선택했을 때 페이지와, 그 책을 고르지 않았을 경우에 얻을 수 있는 페이지의 최대값을 비교해서 큰 값을 선택하도록 한다.

Consider an N x N grid whose squares may have traps. It is not allowed to move to a square with a trap.

Your task is to calculate the number of paths from the upper-left square to the lower-right square where you only can move right or down.

First line: N /// grid size

N line : grid information ( . : empty cell, * : trap)

Print the number of paths modulo 1e9 + 7

4
....
.*..
...*
*...

3

1 <= N <= 1000

어떤 특정한 cell ( path[i][j] ) 까지 도착하는 경로는 왼쪽에서 온 경우( path[i-1][j])와 위쪽에서 온 경우(path[i][j-1])의 합으로 결정된다. 제일 처음 출발하는 cell부터 목표로 하는 cell 까지 cell이 trap(*)인 경우는 제외하고 더해서 만들어 간다. 

1~N개의 집 칠하는데, 옆집과는 다른 색으로 칠하는데 필요한 최소 비용. 집의 배치는 원형으로 생각해서 첫집과 마지막집이 이웃이 되도록 한다.

집의 수와 각각의 집을 칠하는데 필요한 비용

필요한 최소 비용 

3
26 40 83
49 60 57
13 89 99

110

• 1<= N <= 1000
• 1 <= a_i <= 1000

RGB거리 문제에서 약간의 변형이 있다. 집들의 시작과 끝이 연결되어 초기조건을 한번 정하는 것으로 결정할 수 없도록 변형됐다. 기본 아이디어는 초기조건과 거기에 따른 제한 조건을 만족하는 최소의 값들을 찾어서, 비교하도록 했다.

첫집을 특정한 색으로 칠하는 경우에 그 색을 제외한 다른 색들은 아주 큰값으로 설정해서 다음번 집 계산에서 선택되지 않도록 해서 마지막 집까지 최소값을 구한다. 마지막집을 칠하는 최소값에서 첫집과 같은 색깔로 칠하는 경우는 배제하고 최소값을 구한다.  

You are given an integer n. On each step, you may subtract from it any one-digit number that appears in it.

How many steps are required to make the number equal to 0?

The only input line has an integer n.

Print one integer: the minimum number of steps.

27

5

Explanation: An optimal solution is  27 , 20(-7), 18(-2), 10(-8), 9(-1) - 0 (-9)

• 1 <= n <= 10^6

어떤 수의 자리수 중에서 가장 큰 숫자를 찾아서, 그 숫자들을 계속 빼주는 방법이다. 

최적의 경우의 수는 각 자리의 수를 빼서 나온 수의 경우의 수 +1 중에서 가장 작은 것이 된다. 

입력 N 의 크기를 생각해보면, 기록할 필요 없이 가장 큰 자리수를 찾아서 빼내고, 다시 재귀적으로 돌려도 충분할 것 같다.