Daddy's Journey to Platinum

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가 된다.

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

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 인 경우는 초기 조건에서 출력한다.

A rotation of a string can be generated by moving characters one after another from beginning to end. For example, the rotations of acab are acab, caba, abac, and baca.

Your task is to determine the lexicographically minimal rotation of a string.

The only input line contains a string of length n. Each character is one of a–z.

Print the lexicographically minimal rotation.

acab

abac

1 <= n <=10^6

Booth algorithm (link) 을 구현해서 제일 빠른 문자열이 시작하는 위치를 계산한다.

입력 문자열을 2개 연결하고, 계산한 위치부터 원래 입력받은 문자열 길이만큼 출력한다.