시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 13 9 9 69.231%

문제

0 이상 2N-1 이하의 모든 정수가 하나씩 있다. 또한 정수들을 담을 수 있는 상자가 2K개 있으며, 각 상자에는 1부터 2K까지의 자연수 번호가 차례대로 붙어 있다.

나는 가지고 있는 2N개의 정수들을 2K개의 상자에 넣으려고 한다. 나는 정수들이 골고루 분배되기를 원하므로, 각 상자에 들어 있는 정수의 개수는 서로 같아야 한다. 따라서 분배 결과 2K개의 상자 각각에는 2N-K개의 서로 다른 정수들이 들어 있게 된다. 그런데 안타깝게도 나는 완벽주의자이기 때문에, 모든 상자에 대해 그 상자 안에 들어 있는 모든 수를 각각 이진수로 나타냈을 때 1의 개수의 합이 서로 같도록 분배해야 한다.

입력

첫 번째 줄에 두 개의 자연수 N, K (1 ≤ K < N ≤ 16)이 공백을 사이로 두고 주어진다.

출력

2K개의 줄을 출력한다. 이 중 i(1 ≤ i ≤ 2K)번째 줄에는 i번 상자에 들어 있는 정수 2N-K개를 공백 하나를 사이로 두고 출력한다.

전체 출력에서 같은 수가 여러 번 나오면 안 되고, 각 상자마다 들어 있는 모든 수를 이진수로 나타냈을 때 나타난 1의 개수의 합이 모든 상자에 대해 동일해야 한다.

예제 입력

2 1

예제 출력

0 3
1 2

힌트

  • 1번 상자: 0 = 0(2), 3 = 11(2) 이므로, 1은 총 2개
  • 2번 상자: 1 = 1(2), 2 = 10(2) 이므로, 1은 총 2개

상자에 있는 수들이 중복되지 않고, 각 상자마다 그 안에 들어 있는 수를 이진수로 나타냈을 때 나타나는 1의 개수의 합이 2로 서로 같으므로, 이 분배는 완벽주의자인 나에게도 만족스러운 분배인 것이다.

출처

Contest > kriiicon > 제 3회 kriiicon ㅂ번