분할하기

시간 제한0.5초메모리 제한512 MB

요약
집합 {0,...,2^N-1}을 크기 K와 2^N-K인 두 부분집합으로 나누되 각각이 비트 OR에 대해 닫혀 있도록 하는 분할이 존재하는지 판정하고, 존재하면 하나를 출력한다.
난이도

보통10점 중 7점

유형
비트 연산, 조합론, 수학, 완전 탐색
정답자
아직 제출이 없습니다

문제

집합 SS에 대하여, a,b∈S⟹(a∣b)∈Sa,b \in S \Longrightarrow (a \mid b) \in S가 성립할 때, 그리고 그럴 때에만 SS를 좋은 집합이라고 한다. 여기서 ∣\mid는 Bitwise-or를 의미한다. 예를 들어 {1,3}\{1, 3\}은 좋은 집합이다. (1∣1)=1(1 \mid 1) = 1, (1∣3)=3(1 \mid 3) = 3, (3∣3)=3(3 \mid 3) = 3이 모두 {1,3}\{1, 3\}의 원소이기 때문이다. 다만 (1∣2)=3(1 \mid 2) = 3이므로 {1,2}\{1, 2\}는 좋은 집합이 아니다.

전체 집합 U={0,1,⋯ ,2N−1}U = \{0, 1, \cdots, 2^N - 1\}의 부분집합 AA에 대하여, AA의 원소 개수가 KK이고 AA와 U∖AU \setminus A가 모두 좋은 집합일 때, 그리고 그럴 때에만 AA를 N,KN, K-분할이라고 한다.

NN과 KK가 주어질 때, N,KN, K-분할이 존재하는지 밝히고, 존재한다면 그 예를 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에 자연수 NN과 KK가 사이에 공백을 두고 주어진다.

출력

N,KN, K-분할이 존재하지 않으면 첫 번째 줄에 NO를 출력한다.

N,KN, K-분할이 존재하면 첫 번째 줄에 YES를 출력한다. 또한 두 번째 줄에 N,KN, K-분할인 집합의 원소를 오름차순으로 출력한다.

N,KN, K-분할인 집합이 여러 개 존재하면 아무거나 출력해도 정답으로 인정된다.

제한

모든 입력 데이터는 다음 조건을 만족한다.

  • 1≤N≤121 \le N \le 12
  • 1≤K≤2N1 \le K \le 2^N

예제4

  1. 예제 1

    입력
    1 1
    
    예상 출력
    YES
    0
    
  2. 예제 2

    입력
    2 4
    
    예상 출력
    YES
    0 1 2 3
    
  3. 예제 3

    입력
    3 3
    
    예상 출력
    YES
    1 4 5
    
  4. 예제 4

    입력
    3 5
    
    예상 출력
    YES
    0 2 3 6 7