I hate Bishop (Very Hard)

2 secs 1024 MB
riano

問題文


以下の文章は、"I hate Bishop"の問題文から、「が偶数である」という記述を削除したものです。


riano君は幅マス、長さマスのチェス盤でmilkcoffee君とチェスをすることにしました。

しかし、後述する通り、このゲームでは永遠に勝敗が決まらず、いずれ同じ局面を繰り返す「千日手」となります。 今回、「盤上の駒の配置」と「手番」が同じである状況を「同一の局面」と定義し、「同一の局面」が回現れた時点で「千日手」による引き分けとします。

暇を持て余す先手のriano君は、出来る限りこのゲームを長手数に引き延ばそうとし、忙しい後手のmilkcoffee君は、最短手数で引き分けを成立させたいと思っています。 双方が目的に対して最適に指し手を選ぶとき、このゲームは何手で終わるか求めてください。

ゲームの詳細を以下に記します。

1.先手・後手ともポーンとルークを一つずつ使います。縦に並んだマスのうち、最もプレイヤー側のマスにルークを、その一つ前にポーンをそれぞれ置きます。 その間に並ぶマスは初め何も駒が置かれません。

2.ポーンは前にマスだけ進むことが出来ますが、前のマスに駒(自分のものでも、相手のものでも)がある時は動けません。 (このルールにより、今回のゲームでは一切駒の取り合いが起こりえません。)

3.ルークは前後に何マスでも、駒を飛び越えない限り動くことが出来ます。

4.ゲームは、先手と後手が交互に、「一つ駒を選び、動かす」ことを繰り返して進行します。「駒を動かさない」選択は出来ません。

5.手数は先手の着手数で数えます。すなわち、ゲーム開始から先手が1回駒を動かし、後手が1回駒を動かしてゲームが終了した場合「手」となります。

6.問題文に明記されていない限り、現実のチェスのルールは無視されます。例えば、本来のチェスではポーンは最初の手のみマス前進できますが、このゲームではそのような動きは禁止されます。

制約


入力


入力はすべて整数である。

出力


双方が最適に行動したときの、ゲーム終了までの手数(先手の指した手の数)を出力してください。

サンプル


入力1
6
出力1
3

の場合、ゲームは以下のように進行します。先手のルーク・ポーンをRP、 後手のルーク・ポーンをrp、空きマスを.で表すと、

開始局面:      RP..pr

一手目:先手の着手後 R.P.pr

       後手の着手後 R.Pp.r  ―Ⓐ

双方、ポーンを前に進めます。この時点で、双方のポーンどうしが向かい合うため、ポーンはこれ以降動くことが出来ません。

二手目:先手の着手後 .RPp.r

       後手の着手後 .RPpr.

三手目:先手の着手後 R.Ppr.

       後手の着手後 R.Pp.r

と進行し、一手目の終わりⒶと同じ盤面となります。また、手番も同じ(どちらも、次に先手が指す番である)ため、「千日手」が成立します。

よってと答えてください。

※入力が奇数に限られるわけではないことに注意してください。

提出


Go (1.14)