公式

B - Hamming Distance is not 1 解説 by evima

Hints
Hint 1 If there is a pair of two integers differing in only one digit in binary representation, only one of them can be included in $S$.
Hint 2 Only one of $2n$ and $2n+1$ can be included in $S$.
Hint 3 We found that "approximately" half of the integers between $L$ and $R$ can be included in $S$. Try to find a good construction that includes "approximately" half in $S$.
Hint 4 Depending on the parity of $L$ and $R$, it may be possible to include slightly more than half in $S$. Try to modify the construction from Hint 3 without breaking the conditions.
Hint 5 When $L$ is odd and $R$ is even, there are cases where we can include more than half of the elements in $S$. Try experimenting with small values of $L,R$ and guess the condition.
Hint 6 Try constructing under the condition guessed in Hint 5. Also, think about what happens when we try to construct when that condition is not satisfied.

投稿日時:
最終更新: