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

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

NxN grid위에 위치한 두 점(a, b), (c, d) 사이의 거리를 r = abs(a-c) + abs(b-d)로 정의한다.  문제에서는 각 집에서 가장 가까운 치킨집까지의 거리를 그 집의 치킨거리로 하고, 모든 집의 치킨 거리의 합을 도시의 치킨 거리로 한다.

치킨집의 수를 줄이고, 이때 도시의 치킨거리 최소값을 구하는 문제이다.

N M

NxN

0 - 길, 1 - 집, 2 - 치킨집

도시 치킨 거리 최소값

5 2

0 2 0 1 0

1 0 1 0 0

0 0 0 0 0

2 0 0 1 1

2 2 0 1 2

10

2 <= N <=50 , 1 <= M <=13

N x N Grid를 읽어 들이면서 집의 위치와 치킨집의 위치를 vector<pair<int, int>> 에 저장한다.

치킨집 배열에서 M개를 고르고, 이 때 각 집들에서 치킨 거리를 구하고, 그 합을 비교해서 최소값을 찾는다.

M개를 고르기 위해서, bitset을 이용해서, 치킨집들을 선택한다. 

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 (면의 중점과 각변을 연결하는 선)

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

There are n cities and mm roads between them. Unfortunately, the condition of the roads is so poor that they cannot be used. Your task is to repair some of the roads so that there will be a decent route between any two cities.

For each road, you know its reparation cost, and you should find a solution where the total cost is as small as possible.

The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,…,n.

Then, there are m lines describing the roads. Each line has three integers a, b and c: there is a road between cities a and b, and its reparation cost is c. All roads are two-way roads.

Every road is between two different cities, and there is at most one road between two cities.

Print one integer: the minimum total reparation cost. However, if there are no solutions, print "IMPOSSIBLE".

5 6
1 2 3
2 3 5
2 4 2
3 4 8
5 1 7
5 4 4

14

1 <= n <= 1e5

1<= m <= 2*1e5

1 <= a, b <= n

1 <= c <= 1e9

도시들을 정점으로하고 연결하는 도로들을 간선으로 하는 최소 신장 트리(Minimum Spanning Tree) 문제이다. 

간선의 비용을 기준으로 작은 것부터 도시들을 계속해서 연결해 나간다. 도시 하나를 연결할때 연결된 도시수를 기록한다. 모든 도시가 연결된다면 필요한 최소 간선의 수는 도시의 수보다 1 작은 값이 되야 한다. 이 값보다 크다면, 연결할 수 없는 도시가 존재하므로 "IMPOSSIBLE"을 출력하고, 연결되면 연결하면서 기록한 비용을 출력한다.

Consider a game where two players remove sticks from a heap. The players move alternately, and the player who removes the last stick wins the game.

A set P={p1,p2,…,pk} determines the allowed moves. For example, if P={1,3,4}, a player may remove 1, 3 or 4 sticks.

Your task is find out for each number of sticks 1,2,…,n if the first player has a winning or losing position.

The first input line has two integers n and k: the number of sticks and moves.

The next line has k integers p1,p2,…,pk that describe the allowed moves. All integers are distinct, and one of them is 1.

Print a string containing n characters: W means a winning position, and L means a losing position.

10 3
1 3 4

WLWWWWLWLW

1 <= n <= 1e6

1 <= k <= 100

1 <= p_i <= n

움직일 수 있는 수 집합 P에 1이 항상 들어있으므로, 첫번째 위치는 플레이어 1이 이기는 위치가 된다. 다른 p_i개의 경우도 플레이어 1이 모든 스틱을 제거할 수 있으므로, 이 위치들도 모두 이기는 위치가 된다. 

다음 단계로 P_i에 2가 없는 경우에 플레이어 1이 2의 위치에 있다면, 제거할 수 있는 스틱은 1이 되고, 다른 플레이어가 스틱이 1개가 남은 위치가 되고, 다른 플레이어도 최선의 전략을 선택하기 때문에 이경우는 지게된다.

즉, 임의의 위치 i에서 p_i를 통해 움직일 수 있는 위치가 L이라면, 현재의 위치는 W이 된다.

그냥 1~N까지 위치를 움직이며, p_i들을 빼서 비교하는 방법을 사용하면 O( N*K )가 되고, 문제에서 나오는 조건으로는 1e8정도이므로 충분하다.

There are n cities and initially no roads between them. However, every day a new road will be constructed, and there will be a total of m roads.

A component is a group of cities where there is a route between any two cities using the roads. After each day, your task is to find the number of components and the size of the largest component.

The first input line has two integers n and m: the number of cities and roads. The cities are numbered 1,2,…,n 

Then, there are m lines describing the new roads. Each line has two integers a and b: a new road is constructed between cities a and b.

You may assume that every road will be constructed between two different cities.

Print m lines: the required information after each day.

5 3
1 2
1 3
4 5

4 2
3 3
2 3

• 1 <= n < 1e5
• 1 <= m < 2 * 1e5
• 1 <= a, b <= n

connected component count & component size 를 찾는 문제이다. 그래프에서 connected component를 찾는 방법은 DFS, BFS, Union find 등의 방법을 사용한다. 전체 node를 검사하는 경우 시간복잡도는 O(nm)) 이지만, n=1e5, m=2x1e5 의 입력에서 시간초과가 나오므로, 중간에 계산량을 줄이는 방법이 필요해진다.

이 문제는 road(edge)가 추가되므로 추가된 부분과 연결된 부분만 계산한다. 

즉, 모든 edge를 검사할 필요 없이, 이번에 추가되는 edge와 연결된 vertex들에 대해서, 같은 component에 있는 지 확인하고, 있다면 component 숫자나 최대 크기를 변경할 필요가 없고, 서로 다른 component에 있는 경우에는 component 숫자를 줄이고, 새롭게 만들어진 component 크기와 원래 최대 크기를 비교해서 최대크기를 갱신하면 된다.

There are n heaps of sticks and two players who move alternately. On each move, a player chooses a non-empty heap and removes 1, 2, or 3 sticks. The player who removes the last stick wins the game.

Your task is to find out who wins if both players play optimally.

The first input line contains an integer t: the number of tests. After this, t test cases are described:

The first line contains an integer n: the number of heaps.

The next line has n integers x_1, x_2, ... x_n : the number of sticks in each heap.

For each test case, print "first" if the first player wins the game and "second" if the second player wins the game.

3
4
5 7 2 5
2
4 1
3
4 4 4

first
first
second

• 1 <= t <= 2*1e5
• 1 <= n <= 2*1e5
• 1 <= x_i <= 1e9 
• the sum of all n is at most 2*1e5 

Nim Game의 변형문제이다.

제외할 수 있는 숫자가 1~k개로 제한되는 경우에는 (k+1) modulo 결과를 Nim Sum 이라고 한다.

• Nim Sum == 0 : 나중에 하는 사람이 승리하는 전략이 존재
• Nim Sum != 0 : 먼저하는 사람이 승리하는 전략이 존재

대항해시대4의 경우에 동전을 제거하는 게임이 나오는데 같은 원리를 적용하면, 승리할 수 있다. (컴퓨터가 이 전략을 적용하기 때문에 최초에 남는 동전에 따라 게임 결과가 정해져 있다고 생각하면 된다.)