問題一覧 > 通常問題

No.531 エヌスクミ島の平和協定

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 356
作問者 : はむこはむこ / テスター : 👑 Nafmo2Nafmo2
15 ProblemId : 1472 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-06-25 00:22:36

問題文

エヌスクミ島は、特殊な生態系で平和が保たれている。

・$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もしくは右上の雲マークをクリックしてアカウントを作成してください。