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

문제 설명

Given N, B, and D: Find a set of N codewords (1 <= N <= 64), each of length B bits (1 <= B <= 8),
such that each of the codewords is at least Hamming distance of D (1 <= D <= 7) away from each
of the other codewords.

입력

N, B, D on a single line

출력

N codewords, sorted, in decimal, ten per line.

입력 예

16 7 3

출력 예

0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127

문제 풀이

Hamming Distance 계산하는 방법에 대한 문제이다. 각각의 bit 값을 비교하기 위해서, 2로 계속 나누고 달라질때마다 distance를 증가시키는 방법으로 계산한다. 0 부터 숫자를 키워가면서 distance > D인 경우들을 계속 추가시켜서 기록하고, 출력할때 10개 단위로 출력한다.

프로그램 내용

더보기 
int getHammingDistance(int a, int b)
{
    int ret=0;

    while( a> 0 || b>0)
    {
        if( a%2 != b%2)
            ret++;
        a /= 2;
        b /= 2;
    }
    return ret;
};

...

  ans.push_back(0);
    /// check hamming distance > D, put result
    for(int i=0;i < maxB ;i++)
    {
        bool ok= true;

        /// compare hamming distance with last code
        for(int j=0;j!=ans.size();j++)
        {
            /// distance < D
            if( getHammingDistance(i,ans[j]) < D )
            {
                ok = false;
                break;
            }
        }
        /// distance >= D
        if(ok)
        {
            ans.push_back(i);
        }

        /// Max output number
        if(ans.size() >= N)
        {
                break;
        }
    }

 

Chapter 2. Bigger Challenges ( link )

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

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

Problem 2.2.3 Preface Numbering  (0) 2021.01.21
Problem 2.1.3 The Castle  (0) 2021.01.07
Problem 1.2.5 Greedy Gift Givers - 2  (0) 2021.01.03
Problem 2.1.6 Healthy Holsteins  (0) 2020.02.11
USACO Training - Chapter 6. Contest Practice  (0) 2020.01.01

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

문제 설명

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가 가능한 값이 된다.

프로그램 내용

더보기 
vector<bool> dp(n*1000+1);
...
for (int c : coins) 
{
	for (int i = dp.size() - 1; i > 0; i--) 
	{
            if (dp[i]) 
                dp[i + c] = 1; 
            d[c] = 1; 
	}
}
...

 

Dynamic Programming ( link )

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

'CSES' 카테고리의 다른 글

CSES 6. Tree Algorithms  (0) 2021.07.21
CSES 5. Range Queries  (0) 2021.07.21
CSES 3. Rectangle Cutting (1744)  (0) 2020.07.28
CSES 3. Edit Distance (1639)  (0) 2020.03.18
CSES 4. Road Reparation (1675)  (0) 2020.01.20

+ Recent posts

티스토리툴바