問題一覧 > 通常問題

No.1576 織姫と彦星

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 63
作問者 : k1832 / テスター : sugar_sentan a kagasantwi oirom0x210 Hikaru Nishiyama
2 ProblemId : 6661 / 自分の提出
問題文最終更新日: 2021-06-29 14:07:21

問題文

織姫と彦星は一年に一度だけ会うことを許され、七夕の夜に天の川を渡ります。
これを寂しく思った二人は、自由に行き来ができるように、こっそり天の川に橋をかける作戦を立てました。
まず二人は、織姫側の岸に存在するN種類の石を使って橋が作れないかと考えました。
これらの石には不思議な力が宿っており、それぞれの石の性質を表す整数同士のハミング距離が1以下である場合にそれぞれの石を結合することができます。
（ハミング距離については後述します。）
天の川の両岸、つまり、織姫川の岸と彦星側の岸の地面も、同じく不思議な力を宿す石によってできています。

N種類の石の中から最低何種類の石を使えば、不思議な力によって結合された、頑丈な橋を作ることができるかを出力してください。
そのような橋が作れない場合は、 −1 を出力してください。
（それぞれの種類の石は無限個存在することとします。）

ハミング距離
二つの整数のハミング距離とは、二つの整数を2進数で表したときに、異なるビット数のことをいいます。
↓たとえば、3と13のハミング距離は3です。
0011（10進数では3）
1101（10進数では13）

入力

N
start end
stone0 stone1 ... stoneN−1

上記のような形式で、以下の情報が与えられます。
織姫側の石の性質： start
彦星側の石の性質： end
i 番目の石の性質： stonei

制約
1≤N≤103
0≤start, end, stonei≤109
start, end, stonei は全て異なる

サンプル

サンプル1
入力
5
2 0
8 10 5 9 7
出力
0

橋を作るために、以下のような方法があります。

  • 2→10→8→0
    • それぞれ4ビットの二進数で表すと以下のようになります。
    0010
    ↓
    1010
    ↓
    1000
    ↓
    0000
  • 2→0
    • それぞれ2ビットの二進数で表すと以下のようになります。
    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もしくは右上の雲マークをクリックしてアカウントを作成してください。