yukicoder-9

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
    display: block;
    padding: 9.5px;
    margin: 0 0 10px;
    font-size: 13px;
    line-height: 1.42857143;
    color: #333;
    word-break: break-all;
    word-wrap: break-word;
    background-color: #f5f5f5;
    border: 1px solid #ccc;
    border-radius: 4px;
}
</style>
}}}

== [https://yukicoder.me/problems/no/9 No.9 モンスターのレベル上げ] ==

=== Description ===

{{{
#!html
<p>Helia在玩游戏，他有$N$个英雄，第$i$个的攻击力是$A_i$，一开始它们等级都是$0$。有$N$个怪从$1$到$N$顺时针排成一个圈，第$i$个的攻击力是$B_i$。</p>

<p>你可以一开始随便选择一个怪，然后按照顺时针顺序打。每次你会选择一个攻击力最低的英雄去打，如果有多个，会选择等级最低的。如果你的英雄攻击力是$a$，等级是$l$，怪的攻击力是$b$，那么结束战斗后，英雄的攻击力变为$a+\lfloor \frac{b}{2} \rfloor$，等级变为$l+1$。</p>

<p>找到一个初始位置使得$N$个怪都死了以后，等级最高的英雄的等级尽可能小。</p>
}}}

=== Input ===

{{{
#!html
<p class="input">
$N$<br>
$A_1$ $A_2$ $\dots$ $A_N$<br>
$B_1$ $B_2$ $\dots$ $B_N$<br>
</p>

<p>$1 \le N \le 1500, 1 \le A_i, B_i \le 10000$。</p>
}}}

=== Output ===

{{{
#!html
<p>输出最低的等级。</p>
}}}

=== Sample ===

==== Sample 1 ====
输入
{{{
#!html
<pre>
3
6 1 5
9 2 7
</pre>
}}}
输出
{{{
#!html
<pre>
2
</pre>
}}}

==== Sample 2 ====
输入
{{{
#!html
<pre>
5
6 1 5 9 2
7 7 9 4 4
</pre>
}}}
输出
{{{
#!html
<pre>
2
</pre>
}}}

No.9 モンスターのレベル上げ

Description

Helia在玩游戏，他有$N$个英雄，第$i$个的攻击力是$A_i$，一开始它们等级都是$0$。有$N$个怪从$1$到$N$顺时针排成一个圈，第$i$个的攻击力是$B_i$。

你可以一开始随便选择一个怪，然后按照顺时针顺序打。每次你会选择一个攻击力最低的英雄去打，如果有多个，会选择等级最低的。如果你的英雄攻击力是$a$，等级是$l$，怪的攻击力是$b$，那么结束战斗后，英雄的攻击力变为$a+\lfloor \frac{b}{2} \rfloor$，等级变为$l+1$。

找到一个初始位置使得$N$个怪都死了以后，等级最高的英雄的等级尽可能小。

Input

$N$
$A_1$ $A_2$ $\dots$ $A_N$
$B_1$ $B_2$ $\dots$ $B_N$

$1 \le N \le 1500, 1 \le A_i, B_i \le 10000$。

Output

输出最低的等级。

Sample

Sample 1

输入

36 1 59 2 7

输出

2

Sample 2

输入

56 1 5 9 27 7 9 4 4

输出

2