No.9 モンスターのレベル上げ
yuki2006問題文
HeliaはRPGゲームをしている。そのRPGゲームは味方のモンスターのレベル上げていきゲームを進めるゲームである。
Heliaは手持ちに\(N\)匹のモンスターのパーティーがいてレベル上げしたいと思っている。
レベル上げは、敵のモンスターと1対1で戦い、敵のレベルの半分小数切り捨てを獲得できる。（自分の戦ったモンスターのレベルに加算する）
例えば、自分のモンスターのレベルが\(1\)で相手のモンスターのレベルが\(5\)の時、
戦ったあと、自分のモンスターのレベルは\(3\)になる。
戦いに関してはアイテムを駆使してでも勝つため、レベル差に関係なく勝てるとする。
ここで、敵のモンスターが円状に時計回りに並んでいて、最初に戦うモンスターを決めると時計回りの順番に全員と一度だけ戦うことができる狩場がある。
（最初に戦えるモンスターは自由に選べる）
Heliaは、自分の手持ちのモンスターの中から、１戦毎、その時に一番レベルが低い、複数いる場合は、一番戦いをしてないモンスターを戦わせるとする。
この狩場のモンスターを全て倒すとして、手持ちのパーティー中で戦闘回数が一番多い回数がもっとも低くなるよう狩場で最初に戦うモンスターを選んだとき、その中で一番戦闘回数が多い数を求めてください。
注意：速い言語でないと時間的に厳しいかもしれません。
入力
\(N\) \(A_1\ A_2\ \dots\ A_N\) \(B_1\ B_2\ \dots\ B_N\)
\( N\ (1 \leq N \leq 1500) \) パーティーのモンスター数です。
\( A_i\ (1 \leq Ai \leq 10000, 1 \leq i \leq N) \) 味方のパーティーのモンスターのそれぞれのレベルです。
\( B_i\ (1 \leq Bi \leq 10000, 1 \leq i \leq N) \) 敵の狩場のモンスターのそれぞれのレベルです。
狩場のモンスター数と味方のモンスター数は同じとする。
この順番は時計回りに並んでるとする。
出力
数値を文字列で出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 6 1 5 9 2 7
出力
2
例えば狩場の最初のモンスターを左から\(3\)番目を選ぶとすると、
\(7,9,2\)と戦う
以下()内は戦闘回数
\( 6(0),1(0),5(0) \rightarrow 6(0),4(1),5(0) \rightarrow 6(0),8(2),5(0) \rightarrow 6(0),8(2),6(1) \)
となり、少なくとも、戦いが一番多いモンスターは\(2\)回は戦うことになる。
サンプル2
入力
5 6 1 5 9 2 7 7 9 4 4
出力
2
狩場の最初のモンスターを左から\(4\)番目を選ぶとすると、
\(4,4,7,7,9\)と順番に戦う
\( 6(0),1(0),5(0),9(0),2(0) \rightarrow 6(0),3(1),5(0),9(0),2(0) \rightarrow 6(0),3(1),5(0),9(0),4(1) \rightarrow \)
\( 6(0),6(2),5(0),9(0),4(1) \rightarrow 6(0),6(2),5(0),9(0),7(2) \rightarrow 6(0),6(2),9(1),9(0),7(2) \)
となり、一番戦う回数が多いのが\(2\)となる。
(どのモンスターと最初に戦っても、一番試合数が多いのは少なくとも\(2\)回となる）
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。