해밍 경로 2 2초 1024MB

문제

N개의 음이 아닌 2^M 미만의 정수들 A_1, A_2, \dots, A_N이 주어진다. 각각의 정수들에 대하여 다른 정수들과의 가능한 최대 해밍 경로를 찾아야한다.

해밍 경로는 음이 아닌 두 정수들에 대하여 이진수로 변환 시 같은 위치에 대해 다른 수들의 개수이다. (필요의 따라 앞에 붙는 0들도 포함된다)

수식으로 표현하자면 다음과 같다: \smash{\displaystyle\max_{i \le j \le N}} hamming(A_i, A_j)

첫 번째 줄에 두 정수 N과 M이 입력된다 (1 \le N \le 2^M, 1 \le M \le 20).

두 번째 줄에 N개의 정수 A_i가 입력된다 (0 \le A_i \le 2^M).

N개의 정수를 공백으로 나누어 출력하시오. 각 i번째 정수는 A_i의 다른 정수들 간의 최대 해밍 경로이다.

입력

4space_bar 4keyboard_return
9space_bar 12space_bar 9space_bar 11

출력

2space_bar 3space_bar 2space_bar 3

입력

4space_bar 4keyboard_return
5space_bar 7space_bar 3space_bar 9

출력

2space_bar 3space_bar 2space_bar 3

입력

4space_bar 4keyboard_return
3space_bar 4space_bar 6space_bar 10

출력

3space_bar 3space_bar 2space_bar 3

3, 4, 6, 10은 이진수로 0011, 0100, 0110, 1010으로 표현된다. 3과 4, 그리고 4와 10은 해밍 경로가 3이며, 6은 모든 다른 정수와 해밍 경로가 2이다.

COCI 2022/2023 Contest #5 2번