No.1577 織姫と彦星2
タグ : / 解いたユーザー数 43
作問者 :
k1832
/ テスター :
kagasantwi
問題文
この問題は織姫と彦星と制約以外同じです。
織姫と彦星は一年に一度だけ会うことを許され、七夕の夜に天の川を渡ります。
これを寂しく思った二人は、自由に行き来ができるように、こっそり天の川に橋をかける作戦を立てました。
まず二人は、織姫側の岸に存在するN種類の石を使って橋が作れないかと考えました。
これらの石には不思議な力が宿っており、それぞれの石の性質を表す整数同士のハミング距離が1以下である場合にそれぞれの石を結合することができます。
（ハミング距離については後述します。）
天の川の両岸、つまり、織姫川の岸と彦星側の岸の地面も、同じく不思議な力を宿す石によってできています。
N種類の石の中から最低何種類の石を使えば、不思議な力によって結合された、頑丈な橋を作ることができるかを出力してください。
そのような橋が作れない場合は、 $-1$ を出力してください。
（それぞれの種類の石は無限個存在することとします。）
ハミング距離
二つの整数のハミング距離とは、二つの整数を2進数で表したときに、異なるビット数のことをいいます。
↓たとえば、3と13のハミング距離は3です。
0011（10進数では3）
1101（10進数では13）
入力
$N$
$start\ end$
$stone_0\ stone_1\ ...\ stone_{N-1}$
上記のような形式で、以下の情報が与えられます。
織姫側の石の性質： $start$
彦星側の石の性質： $end$
$i$ 番目の石の性質： $stone_i$
制約
$1 \le N \le 5 \times 10^4$
$0 \le start,\ end,\ stone_i \le 10^9$
$start,\ end,\ stone_i$ は全て異なる
サンプル
サンプル1
入力
5 2 0 8 10 5 9 7
出力
0
橋を作るために、以下のような方法があります。
- 2→10→8→0 それぞれ4ビットの二進数で表すと以下のようになります。
- 2→0 それぞれ2ビットの二進数で表すと以下のようになります。
0010
↓
1010
↓
1000
↓
0000
10
↓
00
この問題では、両岸の地面を作っている石のみで橋を作ることも許容されます。
よってこの入力サンプルに対しては、 $0$ が答えになります。
サンプル2
入力
3 2 4 6 8 1
出力
1
2→6→4とするのが最適です。
サンプル3
入力
3 7 6 9 1 5
出力
0
サンプル4
入力
10 21 26 27 24 18 16 17 20 13 1 12 15
出力
3
サンプル5
入力
2 2 1 5 9
出力
-1
どの石を使っても橋をかけることはできません。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。