No.3067 +10 Seconds Clock
タグ : / 解いたユーザー数 106
作問者 : 👑


問題文
あなたはとあるゲームのコースをプレイすることになりました.このコースには地点 の 個の地点があり,地点 がスタート,地点 がゴールです.
各整数 に対し,あなたは地点 から地点 へ移動することができます.これには 秒かかります.それ以外の方法での移動はできません.
このコースには制限時間があります.残りの制限時間はカウントという値によって表され,スタートした時点での値は です.以降, 秒経過するごとに ずつ減少していき,値が になるとゲームオーバーとなります.
また, 個の地点 には+10秒時計が設置されています.+10秒時計は,それが置かれた地点にいて,かつカウントの値が 以上である場合に獲得できます.獲得した瞬間にカウントの値が 増えます.カウントの値が になった瞬間に+10秒時計のある地点に到達した場合,+10秒時計は獲得できません.
あなたは,ゴールにたどり着くまでに獲得する+10秒時計の数をなるべく少なくしたいです.
ゲームオーバーになることなくゴールにたどり着くまでに獲得する+10秒時計の数の最小値を求めてください.ゲームオーバーになることなくゴールにたどり着けない場合はその旨を報告してください.
なお,+10秒時計を獲得するのにかかる時間は無視するものとします.また,ゴールにたどり着いたと同時にカウントが となった場合もゲームオーバーとなり,ゴールにたどり着けなかったとみなします.
制約
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる.
出力
ゴールにたどり着けない場合,-1
を出力せよ.ゴールにたどり着ける場合,獲得する+10秒時計の個数の最小値を出力せよ.
サンプル
サンプル1
入力
6 20 4 5 6 7 8 3 2 3 5
出力
2
次のように行動することで, 個の+10秒時計を獲得してゴールにたどり着くことができます.
- 地点 から地点 へ移動する.カウントは になる.
- 地点 で+10秒時計を獲得し,地点 から地点 へ移動する.カウントは となる.
- 地点 で+10秒時計を獲得せずに,地点 から地点 へ移動する.カウントは となる.
- 地点 から地点 へ移動する.カウントは となる.
- 地点 で+10秒時計を獲得し,地点 から地点 へ移動する.カウントは となる.
個以下の+10秒時計を獲得してゴールにたどり着くことはできません.上の例で最後の+10秒時計を獲得しなかった場合は地点 に到達した時点でカウントが になりますが,これはゴールにたどり着けたとはみなされないことに注意してください.
サンプル2
入力
3 10 10 1 1 2
出力
-1
ゴールにたどり着けません.+10秒時計のある地点に到達した時点でカウントの値が である場合,+10秒時計を獲得できないことに注意してください.
サンプル3
入力
5 4000000 20 20 20 20 3 2 3 4
出力
0
つも+10秒時計を獲得せずに,ゴールにたどり着けます.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。