Diskurs
레이팅 미적용의견: 0
You are given \(n\) non negative integers \(a\)1, a2, . . . , a\(n\) less than \(2^{m}\). For each of them you
are to find the maximum possible hamming distance between it and some other element
of the array \(a\).
The hamming distance of two non negative integers is defined as the number of positions
in the binary representation of these numbers in which they differ (we add leading zeros if
necessary).
Formally, for each \(i\) calculate:
max
{1}{j} }_{n{hamming}{a}}^{, a{j}
Subtask 1 (20 points): \(m \le 10\)
Subtask 2 (25 points): \(m \le 16\)
Subtask 3 (25 points): No additional constraints.
The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 2^{m}\), \(1 \le m \le 20\)).
The second line contains \(n\) numbers \(a_{i}\) (\(0 \le a_{i} < 2^{m}\)).
Output \(n\) numbers seperated with spaces, where the \(i-th\) number is the maximum hamming distance
between \(a_{i}\) and some other number in \(a\).
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 20점 | \(m \le 10\) |
2 | 25점 | \(m \le 16\) |
3 | 25점 | No additional constraints. |
4 4
9 12 9 112 3 2 34 4
5 7 3 92 3 2 34 4
3 4 6 103 3 2 3Clarification of the third example:
The numbers 3, 4, 6, 10 can be represented as 0011, 0100, 0110, 1010, in binary. Numbers 3 and 4 differ at
3 places, same as numbers 4 and 10. On the other hand, the number 6 differs in at most 2 places with all
other numbers.
평가 및 의견
Diskurs
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Diskurs