問題一覧 > 通常問題

No.602 隠されていたゲーム2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 60
作問者 : kzyKTkzyKT / テスター : nmnmnmnmnmnmnmnmnmnmnmnmnmnm
5 ProblemId : 1980 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-12-03 18:58:12

問題文

今年も父の机の引き出しを開けてみると別のゲームが隠されていた。
今回も勝手に遊んでみることにした。

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

キャラは現在いるマスからのマンハッタン距離が$d_1 \dots d_n$の好きなマスに移動できる。
$(x_1,y_1)$と$(x_2,y_2)$のマンハッタン距離は$|x_1-x_2|+|y_1-y_2|$で表される。

今、キャラが$(0,0)$のマスにいる。
$(0,0)$から$(x,y)$に移動しようと思ったが、もうすぐ父が帰って来るらしい。
どうしても$(x,y)$に移動したいので、あと$2$回だけ移動することにした。

$(x,y)$に移動するための最短移動回数を求めよ。
$2$回以内で移動できない場合は$-1$を出力せよ。

入力

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

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

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

出力

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

サンプル

サンプル1
入力
4
3 5 4 13
8 0
出力
2

$(3,0)→(8,0)$、$(4,0)→(8,0)$、$(13,0)→(8,0)$など

サンプル2
入力
1
5
-2 -3
出力
1

サンプル3
入力
1
14
51 4
出力
-1

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