No.531 エヌスクミ島の平和協定
タグ : / 解いたユーザー数 362
作問者 :
はむこ
/ テスター :
👑 
Nafmo2
問題文
エヌスクミ島は、特殊な生態系で平和が保たれている。
・$n$匹の動物が住んでいる。
・動物$i$は、動物$i+1$を捕食しえる（$1 \le i \le n-1$）。
・動物$n$は、動物$1$を捕食しえる。
動物たちは捕食されたくないので、相互に抑止力となる取り決めをした。
つまり、常に全ての動物が、捕食者であるならば被捕食者でもある状況を保つことに合意した。
今、エヌスクミ島の動物たちは、ニューエヌスクミ島へ引っ越しを考えている。
引っ越しは、$m$匹以下乗りの舟$n$隻を使って、以下の手順で行う。
・舟は全て、初めエヌスクミ島にある。
・舟は、$1$匹以上の動物が乗っていれば、エヌスクミ島とニューエヌスクミ島をちょうど片道$1$日で移動できる。
・衝突の危険があるため、$1$日に同時に$2$隻以上を海に出すことはできない。
・動物全員がニューエヌスクミ島に到着した時点で、引っ越し終了とする。
・舟を全隻使う必要はない。つまり、エヌスクミ島に余った舟は置き去りにしてもよい。
取り決めを守りながら引っ越しするのに必要な最短日数を求めよ。
また、引っ越しが不可能であれば$-1$を出力せよ。
入力
n m
$2 \le n \le 100000$
$2 \le m \le 50$
出力
取り決めを守りながら、引っ越しするのに必要な最短日数を求めよ。
また、引っ越しが不可能であれば$-1$を出力せよ。
最後に改行してください。
サンプル
サンプル1
入力
3 2
出力
-1
三竦みの場合を考えます。
例えば、動物$1$と動物$2$がまず舟に乗って移動しようとしたとします。
しかし、動物$1$は動物$2$を一方的に捕食できるので、舟で動物$2$は死の恐怖に怯えることになります。
例えば、動物$1$だけがまず舟に乗って移動しようとしたとします。
しかし、エヌスクミ島に取り残された動物$2$は動物$3$を一方的に捕食できるので、エヌスクミ島で動物$3$は死の恐怖に怯えることになります。
他のケースも同様に、どう頑張っても引っ越しはできません。
サンプル2
入力
3 3
出力
1
三竦みの場合を考えます。
船は3人乗りなので、3人同時に乗ることによって、常に三竦みを維持しながら船に乗ることができます。したがって、$1$日で引っ越しが可能です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。