問題一覧 > 通常問題

No.1576 Orihime and Hikoboshi

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 70
作問者 : k1832 / テスター : sugar_sentan a kagasantwi oirom0x210 Hikaru Nishiyama
お気に入りにしたユーザー ProblemId : 6661 / 自分の提出
問題文最終更新日: 2021-06-29 14:07:21
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

Orihime and Hikoboshi are allowed to meet only once a year, crossing the Milky Way on the night of Tanabata.
Feeling lonely about this, the two devised a plan to secretly build a bridge across the Milky Way so that they could travel back and forth freely.
First, the two wondered whether they could build a bridge using the N types of stones that exist on Orihime's bank.
These stones hold a mysterious power: two stones can be joined if the Hamming distance between the integers representing their properties is at most 1.
(The Hamming distance is explained below.)
The ground on both banks of the Milky Way, that is, Orihime's bank and Hikoboshi's bank, is also made of stones holding the same mysterious power.

Output the minimum number of types of stones, among the N types, that must be used to build a sturdy bridge joined by the mysterious power.
If no such bridge can be built, output $-1$.
(There are infinitely many stones of each type.)

Hamming distance
The Hamming distance between two integers is the number of bits that differ when the two integers are written in binary.
↓For example, the Hamming distance between 3 and 13 is 3.
0011 (3 in decimal)
1101 (13 in decimal)

Input

$N$
$start\ end$
$stone_0\ stone_1\ ...\ stone_{N-1}$

The following information is given in the format above.
Property of the stone on Orihime's side: $start$
Property of the stone on Hikoboshi's side: $end$
Property of the $i$-th stone: $stone_i$

Constraints
$1 \le N \le 10^3$
$0 \le start,\ end,\ stone_i \le 10^9$
$start,\ end,\ stone_i$ are all distinct

Sample

Sample 1
Input
5
2 0
8 10 5 9 7
Output
0

The bridge can be built in the following ways.

  • 2→10→8→0
    • Written as 4-bit binary numbers, these are as follows.
    0010
    ↓
    1010
    ↓
    1000
    ↓
    0000
  • 2→0
    • Written as 2-bit binary numbers, these are as follows.
    10
    ↓
    00
    In this problem, it is also allowed to build the bridge using only the stones that make up the ground on both banks.
    Therefore, for this sample input, the answer is $0$.

Sample 2
Input
3 
2 4
6 8 1
Output
1

2→6→4 is optimal.

Sample 3
Input
3
7 6
9 1 5
Output
0
Sample 4
Input
10
21 26
27 24 18 16 17 20 13 1 12 15
Output
3
Sample 5
Input
2
2 1
5 9
Output
-1

No bridge can be built no matter which stones are used.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。