문제
두 정수의 해밍 거리란, 각각을 이진수로 나타내었을 때 비트가 서로 다른 위치의 개수를 의미한다.
예를 들어, 9ドル$와 12ドル$의 해밍 거리를 구해 보자.
$$ \begin{aligned} 9 &= 1001_{(2)} \\ 12 &= 1100_{(2)} \end{aligned} $$
2ドル^0$의 자리와 2ドル^2$의 자리에서 비트가 서로 다르므로 해밍 거리는 2ドル$이다.
두 수의 자릿수가 다르다면 상위 비트에 0ドル$을 붙여서 비교한다. 예를 들어, 3ドル$과 11ドル$의 해밍 거리를 구해 보자.
$$ \begin{aligned} 3 &= 0011_{(2)} \\ 11 &= 1011_{(2)} \end{aligned} $$
2ドル^3$의 자리에서 비트가 서로 다르므로 해밍 거리는 1ドル$이다.
$A$ 이상 $B$ 이하의 정수 중에서, 해밍 거리가 최대인 두 정수를 구하시오.
출력
$A$ 이상 $B$ 이하의 정수 중에서, 해밍 거리가 최대인 두 정수를 공백으로 구분하여 출력한다.
그러한 정수 쌍이 여러 개라면 그중 아무거나 하나만 출력한다.
힌트
첫 번째 예제의 출력을 이진수로 나타내면 다음과 같다.
$$ \begin{aligned} 6 &= 0110_{(2)} \\ 9 &= 1001_{(2)} \end{aligned} $$
각 위치의 비트를 비교했을 때 서로 다른 비트의 수는 4ドル$개이므로 해밍 거리는 4ドル$이며, 이것이 최대이다.
두 번째 예제의 출력을 이진수로 나타내면 다음과 같다.
$$ \begin{aligned} 29 &= 11101_{(2)} \\ 26 &= 11010_{(2)} \end{aligned} $$
각 위치의 비트를 비교했을 때 서로 다른 비트의 수는 3ドル$개이므로 해밍 거리는 3ドル$이며, 이것이 최대이다.
W3sicHJvYmxlbV9pZCI6IjMzNjkyIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTc0XHViYzBkIFx1YWM3MFx1YjlhYyIsImRlc2NyaXB0aW9uIjoiPHA+XHViNDUwIFx1YzgxNVx1YzIxOFx1Yzc1OCBcdWQ1NzRcdWJjMGQgXHVhYzcwXHViOWFjXHViNzgwLCBcdWFjMDFcdWFjMDFcdWM3NDQgXHVjNzc0XHVjOWM0XHVjMjE4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YzVjOFx1Yzc0NCBcdWI1NGMgXHViZTQ0XHVkMmI4XHVhYzAwIFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjNzA0XHVjZTU4XHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICQ5JFx1YzY0MCAkMTIkXHVjNzU4IFx1ZDU3NFx1YmMwZCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhZDZjXHVkNTc0IFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+JCQgXFxiZWdpbnthbGlnbmVkfSA5ICZhbXA7PSAxMDAxX3soMil9IFxcXFwgMTIgJmFtcDs9IDExMDBfeygyKX0gXFxlbmR7YWxpZ25lZH0gJCQ8XC9wPlxyXG5cclxuPHA+JDJeMCRcdWM3NTggXHVjNzkwXHViOWFjXHVjNjQwICQyXjIkXHVjNzU4IFx1Yzc5MFx1YjlhY1x1YzVkMFx1YzExYyBcdWJlNDRcdWQyYjhcdWFjMDAgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3NFx1YmJjMFx1Yjg1YyBcdWQ1NzRcdWJjMGQgXHVhYzcwXHViOWFjXHViMjk0ICQyJFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YzIxOFx1Yzc1OCBcdWM3OTBcdWI5YmZcdWMyMThcdWFjMDAgXHViMmU0XHViOTc0XHViMmU0XHViYTc0IFx1YzBjMVx1YzcwNCBcdWJlNDRcdWQyYjhcdWM1ZDAgJDAkXHVjNzQ0IFx1YmQ5OVx1YzVlY1x1YzExYyBcdWJlNDRcdWFkNTBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsICQzJFx1YWNmYyAkMTEkXHVjNzU4IFx1ZDU3NFx1YmMwZCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVhZDZjXHVkNTc0IFx1YmNmNFx1Yzc5MC48XC9wPlxyXG5cclxuPHA+JCQgXFxiZWdpbnthbGlnbmVkfSAzICZhbXA7PSAwMDExX3soMil9IFxcXFwgMTEgJmFtcDs9IDEwMTFfeygyKX0gXFxlbmR7YWxpZ25lZH0gJCQ8XC9wPlxyXG5cclxuPHA+JDJeMyRcdWM3NTggXHVjNzkwXHViOWFjXHVjNWQwXHVjMTFjIFx1YmU0NFx1ZDJiOFx1YWMwMCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc0XHViYmMwXHViODVjIFx1ZDU3NFx1YmMwZCBcdWFjNzBcdWI5YWNcdWIyOTQgJDEkXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD4kQSQgXHVjNzc0XHVjMGMxICRCJCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjODE1XHVjMjE4IFx1YzkxMVx1YzVkMFx1YzExYywgXHVkNTc0XHViYzBkIFx1YWM3MFx1YjlhY1x1YWMwMCBcdWNkNWNcdWIzMDBcdWM3NzggXHViNDUwIFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM4MTVcdWMyMTggJEEkXHVjNjQwICRCJFx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGUgQSAmbHQ7IEIgXFxsZSAxMF57MTh9KSQ8XC9wPlxyXG5cclxuPHA+PHN0cm9uZz4kQSQsICRCJFx1YWMwMCAzMlx1YmU0NFx1ZDJiOCBcdWM4MTVcdWMyMTggXHViYzk0XHVjNzA0XHViOTdjIFx1YjExOFx1Yzc0NCBcdWMyMTggXHVjNzg4XHVjNzRjXHVjNWQwIFx1YzhmY1x1Yzc1OFx1ZDU1OFx1Yjc3Yy48XC9zdHJvbmc+PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+JEEkIFx1Yzc3NFx1YzBjMSAkQiQgXHVjNzc0XHVkNTU4XHVjNzU4IFx1YzgxNVx1YzIxOCBcdWM5MTFcdWM1ZDBcdWMxMWMsIFx1ZDU3NFx1YmMwZCBcdWFjNzBcdWI5YWNcdWFjMDAgXHVjZDVjXHViMzAwXHVjNzc4IFx1YjQ1MCBcdWM4MTVcdWMyMThcdWI5N2MgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzVlYyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOFx1YjdlY1x1ZDU1YyBcdWM4MTVcdWMyMTggXHVjMzBkXHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMWNcdWI3N2NcdWJhNzQgXHVhZGY4XHVjOTExIFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWQ1NThcdWIwOThcdWI5Y2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yzc1OCBcdWNkOWNcdWI4MjVcdWM3NDQgXHVjNzc0XHVjOWM0XHVjMjE4XHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD4kJCBcXGJlZ2lue2FsaWduZWR9IDYgJmFtcDs9IDAxMTBfeygyKX0gXFxcXCA5ICZhbXA7PSAxMDAxX3soMil9IFxcZW5ke2FsaWduZWR9ICQkPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWM3MDRcdWNlNThcdWM3NTggXHViZTQ0XHVkMmI4XHViOTdjIFx1YmU0NFx1YWQ1MFx1ZDU4OFx1Yzc0NCBcdWI1NGMgXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWJlNDRcdWQyYjhcdWM3NTggXHVjMjE4XHViMjk0ICQ0JFx1YWMxY1x1Yzc3NFx1YmJjMFx1Yjg1YyBcdWQ1NzRcdWJjMGQgXHVhYzcwXHViOWFjXHViMjk0ICQ0JFx1Yzc3NFx1YmE3MCwgXHVjNzc0XHVhYzgzXHVjNzc0IFx1Y2Q1Y1x1YjMwMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YmM4OFx1YzlmOCBcdWM2MDhcdWM4MWNcdWM3NTggXHVjZDljXHViODI1XHVjNzQ0IFx1Yzc3NFx1YzljNFx1YzIxOFx1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+JCQgXFxiZWdpbnthbGlnbmVkfSAyOSAmYW1wOz0gMTExMDFfeygyKX0gXFxcXCAyNiAmYW1wOz0gMTEwMTBfeygyKX0gXFxlbmR7YWxpZ25lZH0gJCQ8XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWJlNDRcdWQyYjhcdWI5N2MgXHViZTQ0XHVhZDUwXHVkNTg4XHVjNzQ0IFx1YjU0YyBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YmU0NFx1ZDJiOFx1Yzc1OCBcdWMyMThcdWIyOTQgJDMkXHVhYzFjXHVjNzc0XHViYmMwXHViODVjIFx1ZDU3NFx1YmMwZCBcdWFjNzBcdWI5YWNcdWIyOTQgJDMkXHVjNzc0XHViYTcwLCBcdWM3NzRcdWFjODNcdWM3NzQgXHVjZDVjXHViMzAwXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzM2OTIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJIYW1taW5nIERpc3RhbmNlIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgSGFtbWluZyBkaXN0YW5jZSBiZXR3ZWVuIHR3byBpbnRlZ2VycyBpcyBkZWZpbmVkIGFzIHRoZSBudW1iZXIgb2YgcG9zaXRpb25zIGF0IHdoaWNoIHRoZWlyIGNvcnJlc3BvbmRpbmcgYml0cyBkaWZmZXIgd2hlbiByZXByZXNlbnRlZCBpbiBiaW5hcnkgZm9ybS48XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGxldCYjMzk7cyBjYWxjdWxhdGUgdGhlIEhhbW1pbmcgZGlzdGFuY2UgYmV0d2VlbiAkOSQgYW5kICQxMiQ6PFwvcD5cclxuXHJcbjxwPiQkPGJyIFwvPlxyXG5cXGJlZ2lue2FsaWduZWR9PGJyIFwvPlxyXG45ICZhbXA7PSAxMDAxX3soMil9IFxcXFw8YnIgXC8+XHJcbjEyICZhbXA7PSAxMTAwX3soMil9PGJyIFwvPlxyXG5cXGVuZHthbGlnbmVkfTxiciBcLz5cclxuJCQ8XC9wPlxyXG5cclxuPHA+U2luY2UgdGhlIGJpdHMgYXQgdGhlICQyXjAkIGFuZCAkMl4yJCBwb3NpdGlvbnMgYXJlIGRpZmZlcmVudCwgdGhlIEhhbW1pbmcgZGlzdGFuY2UgaXMgJDIkLjxcL3A+XHJcblxyXG48cD5JZiB0aGUgbnVtYmVycyBoYXZlIGRpZmZlcmVudCBiaXQgbGVuZ3RocywgbGVhZGluZyB6ZXJvcyBhcmUgYWRkZWQgZm9yIGNvbXBhcmlzb24uIEZvciBleGFtcGxlLCBsZXQmIzM5O3MgY2FsY3VsYXRlIHRoZSBIYW1taW5nIGRpc3RhbmNlIGJldHdlZW4gJDMkIGFuZCAkMTEkOjxcL3A+XHJcblxyXG48cD4kJDxiciBcLz5cclxuXFxiZWdpbnthbGlnbmVkfTxiciBcLz5cclxuMyAmYW1wOz0gMDAxMV97KDIpfSBcXFxcPGJyIFwvPlxyXG4xMSAmYW1wOz0gMTAxMV97KDIpfTxiciBcLz5cclxuXFxlbmR7YWxpZ25lZH08YnIgXC8+XHJcbiQkPFwvcD5cclxuXHJcbjxwPlNpbmNlIHRoZSBiaXQgYXQgdGhlICQyXjMkIHBvc2l0aW9uIGlzIGRpZmZlcmVudCwgdGhlIEhhbW1pbmcgZGlzdGFuY2UgaXMgJDEkLjxcL3A+XHJcblxyXG48cD5GaW5kIHR3byBpbnRlZ2VycyBiZXR3ZWVuICRBJCBhbmQgJEIkIChpbmNsdXNpdmUpIHRoYXQgaGF2ZSB0aGUgbWF4aW11bSBIYW1taW5nIGRpc3RhbmNlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VHdvIGludGVnZXJzICRBJCBhbmQgJEIkIGFyZSBnaXZlbiwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UuICQoMSBcXGxlIEEgJmx0OyBCIFxcbGUgMTBeezE4fSkkPFwvcD5cclxuXHJcbjxwPjxzdHJvbmc+Tm90ZSB0aGF0ICRBJCBhbmQgJEIkIG1heSBleGNlZWQgdGhlIDMyLWJpdCBpbnRlZ2VyIHJhbmdlLjxcL3N0cm9uZz48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QcmludCB0d28gaW50ZWdlcnMgYmV0d2VlbiAkQSQgYW5kICRCJCAoaW5jbHVzaXZlKSwgc2VwYXJhdGVkIGJ5IGEgc3BhY2UsIHRoYXQgaGF2ZSB0aGUgbWF4aW11bSBIYW1taW5nIGRpc3RhbmNlLjxcL3A+XHJcblxyXG48cD5JZiB0aGVyZSBhcmUgbXVsdGlwbGUgc3VjaCBwYWlycywgcHJpbnQgYW55IG9uZSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5CZWxvdyBpcyB0aGUgb3V0cHV0IG9mIHRoZSBmaXJzdCBleGFtcGxlIHJlcHJlc2VudGVkIGluIGJpbmFyeS48XC9wPlxyXG5cclxuPHA+JCQ8YnIgXC8+XHJcblxcYmVnaW57YWxpZ25lZH08YnIgXC8+XHJcbjYgJmFtcDs9IDAxMTBfeygyKX0gXFxcXDxiciBcLz5cclxuOSAmYW1wOz0gMTAwMV97KDIpfTxiciBcLz5cclxuXFxlbmR7YWxpZ25lZH08YnIgXC8+XHJcbiQkPFwvcD5cclxuXHJcbjxwPlRoZSBudW1iZXIgb2YgZGlmZmVyaW5nIHBvc2l0aW9ucyBpcyAkNCQsIHNvIHRoZSBIYW1taW5nIGRpc3RhbmNlIGlzICQ0JCwgYW5kIHRoaXMgaXMgdGhlIG1heGltdW0uPFwvcD5cclxuXHJcbjxwPkJlbG93IGlzIHRoZSBvdXRwdXQgb2YgdGhlIHNlY29uZCBleGFtcGxlIHJlcHJlc2VudGVkIGluIGJpbmFyeS48XC9wPlxyXG5cclxuPHA+JCQ8YnIgXC8+XHJcblxcYmVnaW57YWxpZ25lZH08YnIgXC8+XHJcbjI5ICZhbXA7PSAxMTEwMV97KDIpfSBcXFxcPGJyIFwvPlxyXG4yNiAmYW1wOz0gMTEwMTBfeygyKX08YnIgXC8+XHJcblxcZW5ke2FsaWduZWR9PGJyIFwvPlxyXG4kJDxcL3A+XHJcblxyXG48cD5UaGUgbnVtYmVyIG9mIGRpZmZlcmluZyBwb3NpdGlvbnMgaXMgJDMkLCBzbyB0aGUgSGFtbWluZyBkaXN0YW5jZSBpcyAkMyQsIGFuZCB0aGlzIGlzIHRoZSBtYXhpbXVtLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==