완전히 다양화된 수열
시간 제한1초메모리 제한128 MB
n이 주어질 때 각 원소 m이 정확히 m개의 부분집합에 속하고 모든 부분집합의 크기가 짝수인 최소 길이 수열을 구성하거나 존재하지 않음을 판정합니다.
문제
양의 정수 n이 주어진다. N = {1, 2, ..., n}이라 하자. N의 부분집합으로 이루어진 수열 A1, ..., Ak가 다음 조건을 모두 만족하면 이 수열을 완전히 다양화된 수열이라고 한다.
- 각 부분집합 Ai는 짝수 개의 원소를 가진다.
- N의 각 원소 m에 대해, m을 포함하는 부분집합 Ai가 정확히 m개 있다.
수열의 항은 서로 같아도 된다. N = {1, 2, 3}일 때 {1, 3}, {2, 3}, {2, 3}으로 이루어진 수열은 조건을 만족한다.
조건을 만족하는 수열이 여러 개 있을 수 있다. 그중 길이 k가 가장 작은 수열을 최소 수열이라고 한다. 정수 n이 주어졌을 때 완전히 다양화된 수열이 존재하는지 판별하고, 존재한다면 최소 수열 하나를 출력하라.
입력
각 줄에 양의 정수 n이 하나씩 주어진다. n은 100 이하이다.
입력은 0이 주어지는 줄에서 끝나며, 0은 처리하지 않는다.
출력
각 n마다 답을 출력한다.
완전히 다양화된 수열이 존재하지 않으면 0을 출력한다.
존재하면 첫 줄에 최소 수열의 길이를 출력하고, 이어서 각 부분집합을 한 줄에 하나씩 출력한다. 각 부분집합 안의 원소는 오름차순으로 쓰고, 원소 사이에는 공백 하나를 둔다. 부분집합들은 사전순으로 출력한다.
각 n에 대한 출력 블록 사이에는 빈 줄을 하나 둔다. 답이 여러 개일 수 있으며, 그중 아무 최소 수열이나 출력해도 된다.