No.467 隠されていたゲーム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 79
作問者 : kzyKTkzyKT / テスター : tubo28tubo28

7 ProblemId : 1163 / 出題時の順位表

問題文

父の机の引き出しを開けたら、綺麗に包装されてリボンがついている箱を偶然見つけてしまった。
勝手に開けてみると、ゲームが入っていた。面白そうだったので、こっそり遊んでみることにした。

このゲームは正方形のマスが敷き詰められた無限に広いフィールドをキャラクターを移動させてプレイする。
製作者の性格が悪いため移動が少し面倒である。

キャラは現在いるマスからのチェビシェフ距離$(L_\infty-$距離$)$が$d_1 \dots d_n$の好きなマスに移動できる。
$(x_1,y_1)$と$(x_2,y_2)$のチェビシェフ距離は$max(|x_1-x_2|,|y_1-y_2|)$で表される。$($チェビシェフ距離:wikipedia$)$

今、キャラが$(0,0)$のマスにいる。
$(0,0)$から$(x,y)$に移動する最短移動回数を求めよ。
移動不可能の場合は$-1$を出力せよ。

入力

$n$
$d_1 \dots d_n$
$x \ y$

$1$行目に移動できる距離の個数$n$が与えられる。
$2$行目に$d_i$が空白区切りで与えられる。
$3$行目に目的のマスの座標$(x,y)$が空白区切りで与えられる。

入力はすべて整数で与えられる。
$1 \le n \le 15$
$1 \le d_i \le 10^9 \ (d_i$はすべて異なる$)$
$-10^9 \le x,y \le 10^9$

出力

$(x,y)$までの最短移動回数を出力せよ。
移動不可能の場合は$-1$を出力せよ。

サンプル

サンプル1
入力
3
3 4 5
12 12
出力
3

例 $(0,0) \ → \ (3,3) \ → \ (7,7) \ → \ (12,12)$

サンプル2
入力
2
5 9
4 0
出力
2

例 $(0,0) \ → \ (9,0) \ → \ (4,0)$

サンプル3
入力
1
1
45 14
出力
45

提出ページヘ