출처: https://cses.fi/problemset/task/1623

문제 설명

There are n apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

입력

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

The next line has n integers p_1,p_2,…,p_n: the weight of each apple.

출력

Print one integer: the minimum difference between the weights of the groups.

입력 예

5
3 2 7 4 1

출력 예

1

제약조건

  • 1 <= n <= 20
  • 1 <= p_i <= 10^9

문제 풀이

입력받은 사과들을 양쪽에 각각 넣어보고 무게 차의 최소 값을 찾는다.

프로그램 내용

더보기 
long ans = 1e18;

void search_diff(int a, long b, vector<int> weight)
{
    if (a == weight.size()) {
        ans = min(ans, abs(b));
        return;
    }
    search_diff(a+1,b+weight[a], weight);	/// add apple to side A
    search_diff(a+1,b-weight[a], weight);	/// add apple to side B
}

int main()
{
    int N;		/// number of apple

    vector<int> weight(N,0);
    for(int idx=0; idx<N ; ++idx)
        cin >> weight[idx];

    search_diff(0,0, weight);

    cout << ans << endl;

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 2. Sorting and Searching  (0) 2019.09.24
CSES 1. Chessboard and Queens (1624)  (0) 2019.09.23
CSES 1. Creating Strings I (1622)  (0) 2019.09.23
CSES 1. Palindrome Reorder (1755)  (0) 2019.09.23
CSES 1. Coin Piles (1754)  (0) 2019.09.23

출처: https://cses.fi/problemset/task/1622 

문제 설명

Given a string, your task is to generate all different strings that can be created using its characters.

입력 

The only input line has a string of length n. Each character is between a–z.

출력

First print an integer k: the number of strings. Then print k lines: the strings in alphabetical order.

입력 예

aabac

출력 예

20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaa

제약조건

1 ≤ n ≤ 8

문제 풀이 내용

문자열을 읽어 들인다음, 정렬한다. next_permutation() 기능을 이용해서 새로운 문자열을 만들고 set<string>에 저장한다. set에 저장된 문자열 개수와 문자열들을 출력한다.

프로그램 내용

더보기 
int main()
{
    cin >> in_str;

    set <string> out_str;

    sort(in_str.begin(), in_str.end());

    do {
        out_str.insert(in_str);
    } while (next_permutation(in_str.begin(), in_str.end()));

    cout << out_str.size() << endl;
    for (auto it : out_str)  
	    cout << it << endl;

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Chessboard and Queens (1624)  (0) 2019.09.23
CSES 1. Apple Division (1623)  (0) 2019.09.23
CSES 1. Palindrome Reorder (1755)  (0) 2019.09.23
CSES 1. Coin Piles (1754)  (0) 2019.09.23
CSES 1. Trailing Zeros (1618)  (0) 2019.09.23

출처:https://cses.fi/problemset/task/1754

문제 설명

You have two coin piles containing a and b coins. On each move, you can either remove one coin from the left pile and two coins from the right pile, or two coins from the left pile and one coin from the right pile.


Your task is to efficiently find out if you can empty both the piles.

입력

The first input line has an integer t: the number of tests.

After this, there are t lines, each of which has two integers a and b: the numbers of coins in the piles.

출력

For each test, print "YES" if you can empty the piles and "NO" otherwise.

입력 예

3
2 1
2 2
3 3

출력 예

YES
NO
YES

제약조건

  • 1 <= t <= 10^5
  • 0 <= a,b <= 10^9

문제 풀이

두개의 입력 a, b를 이용해서 가능한 조건들을 검사한다.

먼저, 한번에 제거 가능한 숫자는 3개 이므로, 두개의 합이 3의 배수가 아니면 불가능하다. 왼쪽에서 2개 제거하는 수를 x, 오른쪽에서 2개 제거하는 수를 y로 해서 계산한다.

더할 수는 없으므로 하나라도 음수이면 불가능하다. (x < 0 || y <0)

한쪽의 입력이 다른 쪽의 2배보다 크면 불가능하다. (a > 2b || 2a < b)

두 입력의 차가 abs(a-b) = abs(x-y) 이면, 모두 없애는게 가능하므로, 이 조건까지 확인해서 결과를 출력한다.  

프로그램 내용

더보기 
#define MAX_T 100000
#define MAX_P 1000000000

int main()
{
    int a, b;
    int x, y;

	cin >> a >> b;
	x = (2*a-1*b)/3;
	y = (2*b-1*a)/3;

	if ((a+b) % 3 == 0)
		if ( a > 2*b || 2*a < b )
			cout << "NO" << endl;
		else if ( x < 0 || y < 0)
			cout << "NO" << endl;
		else if ( abs(a-b) == abs(x-y) )
        	cout << "YES" << endl;

        else
            cout << "NO" << endl;
    }
}

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Creating Strings I (1622)  (0) 2019.09.23
CSES 1. Palindrome Reorder (1755)  (0) 2019.09.23
CSES 1. Trailing Zeros (1618)  (0) 2019.09.23
CSES 1. Bit Strings (1617)  (0) 2019.09.22
CSES 1. Two Knights (1072)  (0) 2019.09.22

출처: https://cses.fi/problemset/task/1618

문제 설명

Your task is to calculate the number of trailing zeros in the factorial n!n!.

For example, 20!=2432902008176640000 and it has 4 trailing zeros.

입력

The only input line has an integer n.

출력 양식

Print the number of trailing zeros in n!.

입력 예

20

출력 예

4

제약조건

1 <= n <= 10^9

문제 풀이

팩토리얼에서 뒤에 나오는 0의 갯수는 N보다 작은 수중에서 곱해지는 5나 5의 거듭제곱수들이 몇번인가와 같다. 그래서, 5로 계속 나누면서 나오는 수들을 누적해서 출력한다. 엄밀하게는 2와 2의 거듭제곱수들의 빈도수와 비교해야 한다.

프로그램 내용

더보기 
#define MAX_N 1000000000

int main()
{
    int N;
    cin >> N; 

    /// count number of 5 less than N
    int count_5=0;
    int div=1;
    long base = N;

    while(div != 0)
        div = base / 5;
        count_5 += div;
        base = div;

	cout << count_5 << endl;

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Palindrome Reorder (1755)  (0) 2019.09.23
CSES 1. Coin Piles (1754)  (0) 2019.09.23
CSES 1. Bit Strings (1617)  (0) 2019.09.22
CSES 1. Two Knights (1072)  (0) 2019.09.22
CSES 1. Two Sets (1092)  (0) 2019.09.21

출처: https://cses.fi/problemset/task/1072

문제 설명

Your task is to count for k=1,2,…,n the number of ways two knights can be placed on a k×k chessboard so that they do not attack each other.

입력 

The only input line contains an integer n.

출력

Print n integers: the results.

입력 예

8

출력 예

0
6
28
96
252
550
1056
1848

제약조건

1 <= n <= 10000

문제 풀이 

N x N 체스보드에 두개의 knight를 올려 놓는 방법의 경우의 수는 첫번째 나이트를 놓을 수 있는 경우의 수(NxN)와 두번째 나이트를 올려 놓을 수 있는 경우의 수 (NxN-1)를 곱한 만큼이다. 이 중에서 두개의 knight가 서로 공격할 수 있는 경우는 3x2 혹은 2x3의 작은 보드의 마주보는 귀퉁이에 나이트들이 위치하는 경우이다. 이 작은 보드의 수는 2x3의 경우는 (N-1)(N-2), 3x2의 경우는 (N-2)(N-1) 이다. 4개의 귀퉁이가 있으므로 4[(N-2)(N-1)+(N-1)(N-2)]를 전체에서 제외하면 된다. 문제에서는 2개의 Knight 색깔을 구분하지 않으므로, 계산한 경우의 수/2를 하면 답이다.

W    
    B
혹은 
W  
   
  B

프로그램 내용

더보기 
#define MAX_N 10000

int main()
{

    for (long i=1;i<= N;i++)
        unsigned long long k_case;
        k_case = i*i*i*i - 9*i*i + 24*i -16;

        if (i==1)
            cout << 0 << endl;
        else
            cout << k_case/2 << endl;

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Trailing Zeros (1618)  (0) 2019.09.23
CSES 1. Bit Strings (1617)  (0) 2019.09.22
CSES 1. Two Sets (1092)  (0) 2019.09.21
CSES 1. Number Spiral (1071)  (0) 2019.09.21
CSES 1. Permutations (1070)  (0) 2019.09.19

출처: https://cses.fi/problemset/task/1092

문제 설명

Your task is to divide the numbers 1,2,…,n into two sets of equal sum.

입력 양식

The only input line contains an integer n.

출력

Print "YES", if the division is possible, and "NO" otherwise.

After this, if the division is possible, print an example of how to create the sets. First, print the number of elements in the first set followed by the elements themselves in a separate line, and then, print the second set in a similar way.

입력 예

Example 1.

7

 

Example 2.

6

출력 예

Example 1.

YES
4
1 2 4 7
3
3 5 6

 

Example 2.

NO

제약조건

1 <= n  <= 1e6

문제 풀이

입력받은 n 이 4k 혹은 4k+3 인 경우에만 YES가 된다. ( (n+1)*n/2/2 == 0 ) n이 4k+3 형태인 경우와 4k 형태인 경우로 나누고, 4개 혹은 3개 그룹을 같도록 나누어서 출력한다.

프로그램 내용

더보기 
#define MAX_N 1000000

int main()
{
    long long N;
    long long K;

    cin >> N;

    if ( (N+1)*N/2 % 2 != 0 )
        cout << "NO" << endl;

    if ( (N+1)*N/2 % 2 == 0 )
        cout << "YES" << endl;
        /// N = 4k + 3
        /// 2(k+1) ,
        /// 0, 3, 4, 7, ...
        if ( N % 4 == 3)
            K = (N+1) / 4;
            cout << 2*K -1 << endl;
            for (int i=0; i< K; i++)
                if ( i == 0)
                    cout << 4*i + 3 << " ";
                else
                    cout << 4*i << " " << 4*i + 3 << " ";
        /// 2(k+1)-1,
        /// 4k+2, 4k+1, 4(k-1)+2, 4(k-1)+1, ...
        /// 1, 2, 5, 6, ...
            cout << 2*K << endl;
            for (int i=1; i<= K; i++)
                cout << 4*(i-1)+1 << " " << 4*(i - 1) +2 << " ";

        if ( N % 4 == 0)
            K = N / 4;
            /// N = 4k
            /// 2(k+1) ,
            /// 1, 4, 5, 8, ...
            cout << 2*K << endl;
            for (int i=1; i<= K; i++)
                cout << 4*(i-1) + 1 << " " << 4*i << " ";

			/// N = 4k + 3
            /// 2(k+1) ,
            /// 2, 3, 6, 7, ...
            cout << 2*K << endl;
            for (int i=1; i<= K; i++)
                cout << 4*(i-1)+2 << " " << 4*(i - 1) +3 << " ";

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Bit Strings (1617)  (0) 2019.09.22
CSES 1. Two Knights (1072)  (0) 2019.09.22
CSES 1. Number Spiral (1071)  (0) 2019.09.21
CSES 1. Permutations (1070)  (0) 2019.09.19
CSES 1. Increasing Array (1094)  (0) 2019.09.19

출처: https://cses.fi/problemset/task/1071

문제 설명

A number spiral is an infinite grid whose upper-left square has number 1. Here are the first five layers of the spiral:

1 2 9 10 25
4 3 8 11 24
5 6 7 12 23
16 15 14 13 22
17 18 19 20 21

Your task is to find out the number in row y and column x.

입력

The first input line contains an integer t: the number of tests.

After this, there are tt lines, each containing integers y and x.

출력

For each test, print the number in row y and column x.

입력 예

3
2 3
1 1
4 2

출력 예

8
1
15

제약조건

  • 1 <= t  <= 10^5 
  • 1 <= y , x <= 10^9

 

문제 풀이 

(y, x) 위치를 입력 받아서, y 와 x 를 비교해서 더 큰 수를 기준으로 출발한다. x의 경우 홀수이면 (2k+1)^2에서 y만큼 줄이면 원하는 답이 되고, 짝수이면 (2k+1)^2+1 에서 y만큼 더하면 된다. y의 경우 짝수이면 (2k)^2에서 x 만큼 줄이고, 홀수이면 (2k)^+1에서 x만큼 더하면 된다.

프로그램 내용

더보기 
#define MAX_SQUARE 100000
#define MAX_ELEMENT 1000000000

int main()
{    
    long long x, y;
	cin >> y >> x;

    /// (1,1), (1,2), (1,3), ... , (1,t)
    /// (2,1), (2,2), (2,3), ... , (2,t)
    /// ... (1, (2k-1)) -> (2k-1)^2 , (2,(2k-1)) = (2k-1)^2 - (2-1) = 8
    /// ... (2k, 1) -> (2k)^2, (2k, 2) = (2k)^2 - (2-1) = 15
    if (x >= y) /// (2,3), (3,3)           
		if( x%2 == 1)	/// x = 2k-1,
			result[i] = x*x - (y-1);
		else
			result[i] = (x-1)*(x-1) + y;
	else /// y > x            
		if( y%2 == 0 ) /// y = 2k,
			result[i] = y*y - (x-1);
		else
			result[i] = (y-1)*(y-1) + x;

	for (int i=0; i< TestNum; i++)
        cout << result[i] << endl;

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Two Knights (1072)  (0) 2019.09.22
CSES 1. Two Sets (1092)  (0) 2019.09.21
CSES 1. Permutations (1070)  (0) 2019.09.19
CSES 1. Increasing Array (1094)  (0) 2019.09.19
CSES 1. Repetitions (1069)  (0) 2019.09.16

출처: https://cses.fi/problemset/task/1070

문제 설명

A permutation of integers 1,2,…,n is called beautiful if there are no adjacent elements whose difference is 1.

Given N, construct a beautiful permutation if such a permutation exists.

입력 양식

The only input line contains an integer N.

출력

Print a beautiful permutation of integers 1,2,…,n If there are several solutions, you may print any of them. If there are no solutions, print "NO SOLUTION".

입력 예

test1. 5 

test2. 3 

출력 예

test1. 4 2 5 3 1

test2. NO SOLUTION

제약조건

1 <=  n <= 1e6  

문제 풀이

N = 1 이면, 그냥 1을 출력 No distance, N=2 or N=3 -> No Solution, if N > 4 이면 짝수들을 2부터 2씩 커지는 순서로 N보다 작거나 같을 때까지 출력하고 1부터 나머지 홀수들을 2씩 증가시키면서 출력한다.

- 처음에는 next_permutation 함수를 써서 임의의 문자열에 대해서, 거리들을 측정했는데 숫자가 커지면서 TIME LIMIT EXCEEDED 가 나와서 그냥 만드는 방법으로 변경했다.

프로그램 내용

더보기 
int main()
{
    int N;
    cin >> N;

    vector <int> numbers;			/// 1 ~ N
    for (int idx=0; idx< N; ++idx)
        numbers.push_back(idx+1);

    if (N == 1)
        cout << 1 << endl;
    else if (N==2 ||N == 3)
        cout << "NO SOLUTION" << endl;
    else
        for (int i=1; i < N; i += 2)	/// odd index
            cout << numbers[i] << " ";
        for (int i=0; i < N; i += 2)	/// even index
            cout << numbers[i] << " ";

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Two Sets (1092)  (0) 2019.09.21
CSES 1. Number Spiral (1071)  (0) 2019.09.21
CSES 1. Increasing Array (1094)  (0) 2019.09.19
CSES 1. Repetitions (1069)  (0) 2019.09.16
CSES 1. Missing Number (1083)  (0) 2019.09.15

출처: https://cses.fi/problemset/task/1094 

문제 설명

You are given an array of N integers. You want to modify the array so that it is increasing, i.e., every element is at least as large as the previous element.

On each turn, you may increase the value of any element by one. What is the minimum number of turns required?

입력 양식

The first input line contains an integer N: the size of the array.

Then, the second line contains N integers x_1,x_2,…,x_n : the contents of the array

출력 

Print the minimum number of turns.

입력 예

5
3 2 5 1 7

출력 예

5

문제 풀이

Constraints

  • 1 <= n  <= 2⋅10^5 
  • 1 <= x_i <= 10^9

입력을 배열로 받아 들여서, 입력 받은 수 전체를 비교한다. 현재 수보다 다음 수가 작으면, 그 차이 만큼 더하고 기록을 누적한다. 입력 범위에 주의하면 충분하다.

프로그램 내용

더보기 
#define MAX_N 200000
#define MAX_X 1000000000

int main()
{
    long long N;
    cin >> N;

    long long arr[N];

    for (int i=0; i< N; ++i)
        cin >> arr[i];

    long long op_count = 0;
    for (int i=0; i< N - 1; ++i)
    {
        long long temp = arr[i] - arr[i+1];

        if (temp >= 0)
        {
            arr[i+1] += temp;
            op_count += temp;
        }
    }

    cout << op_count << endl;

 

 

Introductory problems ( link )

저작자표시 비영리 동일조건

'CSES' 카테고리의 다른 글

CSES 1. Number Spiral (1071)  (0) 2019.09.21
CSES 1. Permutations (1070)  (0) 2019.09.19
CSES 1. Repetitions (1069)  (0) 2019.09.16
CSES 1. Missing Number (1083)  (0) 2019.09.15
CSES - Introductory Problems  (0) 2019.09.14

출처: https://train.usaco.org/usacogate

문제 설명

Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.

In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.

You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.

입력

Line 1: N (1 <= N <= 1000), the number of records to be sorted
Lines 2-N+1: A single integer from the set {1, 2, 3}

출력

A single line containing the number of exchanges required

입력 예

9 
2 
2 
1 
3 
3 
3 
2 
3 
1

출력 예

4 

문제 풀이

정렬할 입력을 저장하면서, 1, 2, 3 숫자를 기록한다. bubble sort와 비슷한 방법으로 진행한다. 2보다 뒤쪽에 있는 1들을 2와 바꾼다. 3보다 뒤에 있는 1들을 3과 바꾼다. 마지막으로 3보다 뒤에 있는 2들을 3과 바꾼다. 

프로그램 내용

더보기 
#define MAX_N 1000

int main()
{
    int N;
    fin >> N;

    vector <int> in_Nums;
    int eachNum[3] = {0};

    for (int idx=0; idx< N ; ++idx)
        fin >> num;
        in_Nums.push_back(num);
        eachNum[num-1]++;		/// count 1, 2, 3

    /// exchange 1 with 2 until eachNum[0] 
    /// part(eachNum[0], 1 , 2, N)
    int cnt=0;
    for(int i= eachNum[0]; i< N; ++i)
        if(in_Nums[i] == 1)
        for(int j=0;j<eachNum[0];++j)
            if(in_Nums[j] == 2)
                swap(in_Nums[i],in_Nums[j]);

    /// exchange 1 with 3 until eachNum[0]
    for(int i= eachNum[0]; i< N; ++i)
        if(in_Nums[i]== 1)
        for(int j=0;j<eachNum[0];++j)
            if(in_Nums[j]==3)
                swap(in_Nums[i],in_Nums[j]);

    /// exchange 2 with 3 eachNum[0]+eachNum[1]
    for(int i= eachNum[0]+eachNum[1]; i< N; ++i)
        if(in_Nums[i]== 2)
        for(int j=0;j<eachNum[0]+eachNum[1];++j)
            if(in_Nums[j]==3)
                swap(in_Nums[i],in_Nums[j]);

 

Chapter 2. Bigger Challenges

저작자표시 비영리 동일조건

'USACO Training' 카테고리의 다른 글

Problem 2.3.4 Money Systems  (0) 2019.10.11
Problem 2.2.4 Subset Sums  (0) 2019.10.10
Problem 2.1.4 Ordered Fractions  (0) 2019.09.18
Problem 2.2.5 Runaround Numbers  (0) 2019.09.18
Problem 1.6.4 SuperPrime Rib  (0) 2019.09.16

+ Recent posts

티스토리툴바