3882번 - 스무고개
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 7 | 3 | 2 | 100.000% |
문제
어떤 방에 n개의 물건이 있고, 각 물건은 특징을 가지고 있다. 각 특징은 예 또는 아니오로 대답할 수 있는 질문이다.
특징은 총 종류가 m개가 있다. 이러한 특징을 이용하면 이 방에 있는 모든 물건을 설명할 수 있다. 즉, 모든 물건은 길이가 일정한 불리언 수열로 나타낼 수 있다. 모든 물체는 다른 물체와 적어도 한 특징이 다르다.
상근이는 어떤 물체를 확인하려고 한다. 따라서, 그 물체의 특징을 알고 있는 사람에게 질문을 할 것이다. 모든 질문은 특징 중 하나이고, 모든 답변은 예 또는 아니오이다. 상근이는 답변을 들은 후에 다음 질문을 고를 수 있다.
상근이는 질문은 하나 할 때 마다 100원씩 내야 한다. 주머니 사정이 넉넉하지 않은 상근이는 돈을 가능한 적게 내려고 한다. 상근이는 모든 물체의 특징을 알고 있다. 하지만, 찾으려고 하는 물체의 특징은 알고 있지 못한다. 따라서, 상근이는 질문을 하기 전에 전략을 세울 수 있다.
물체의 특징이 주어졌을 때, 최대 몇 번의 질문을 하면 모든 물체를 구별할 수 있는지 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 특징의 개수 m과 물체의 개수 n이 주어진다. (0 < m ≤ 11, 0 < n ≤ 128) 다음 n개의 줄에는 각 물체의 특징이 주어진다. 특징은 길이가 m인 이진 문자열로 각 값은 1(예) 또는 0(아니오)이다. 두 물체의 특징이 같은 경우는 없다.
출력
각 테스트 케이스에 대해서, 최대 몇 번의 질문을 하면 모든 물체를 구별할 수 있는지 출력한다. 가능한 질문을 적게 해야 한다.
예제 입력
8 1 11010101 11 4 00111001100 01001101011 01010000011 01100110001 11 16 01000101111 01011000000 01011111001 01101101001 01110010111 01110100111 10000001010 10010001000 10010110100 10100010100 10101010110 10110100010 11001010011 11011001001 11111000111 11111011101 11 12 10000000000 01000000000 00100000000 00010000000 00001000000 00000100000 00000010000 00000001000 00000000100 00000000010 00000000001 00000000000 9 32 001000000 000100000 000010000 000001000 000000100 000000010 000000001 000000000 011000000 010100000 010010000 010001000 010000100 010000010 010000001 010000000 101000000 100100000 100010000 100001000 100000100 100000010 100000001 100000000 111000000 110100000 110010000 110001000 110000100 110000010 110000001 110000000 0 0
예제 출력
0 2 4 11 9