問題一覧 > 通常問題

No.771 しおり

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 121
作問者 : Shuz*Shuz* / テスター : tatyamtatyam
5 ProblemId : 2580 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-12-26 00:32:40

問題文

Shuz*君はしおりが挟まれている本を $N$ 冊持っていて、 $i$ 番目の本は本 $i$ と呼ばれます。
各本 $i$ には、表紙からの厚さが $A_i$ の場所にしおりが挟まれています。
しおりの厚さは $0$ とします。また、各本 $i$ の表紙から裏表紙までの厚さは $B_i$ です。

長らくの間これらの本は放置されていたのですが、Shuz*君はこれら $N$ 冊の本を本棚に置き、表紙を左側にしてすきまなく一列に並べたいと思いました。
Shuz*君は見栄えがよくなるよう、 $N$ 冊の本を表紙を左側にしてすきまなく一列に並べたときに、以下に定義される醜さができるだけ小さくなるようにしたいと思っています。

  • 隣り合っている $2$ 冊の本に対し、左側の本のしおりから右側の本のしおりまでの厚さをしおり間距離とする。
  • $N$ 冊の本を表紙を左側にしてすきまなく一列に並べたとき、 $N-1$ 個存在するしおり間距離のうち、最大のものをその並べ方の醜さとする。


    • $\ N$ 冊の本を表紙を左側にしてすきまなく一列に並べたときの、醜さの最小値はどのくらいでしょうか。

    制約

  • $1 \le N \le 18$
  • $1 \le A_i \lt B_i \le 1000$
  • 入力はすべて整数

    • 入力

    入力は以下の形式で標準入力から与えられます。 
    $N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_N\ B_N$

    $\ 1$ 行目に、Shuz*君の持っている、しおりが挟まれている本の冊数 $N$ が与えられます。
    続く $N$ 行に、$1 + i$ 行目には $A_i,\ B_i$ が空白区切りで与えられます。

    出力

    $N$ 冊の本を表紙を左側にしてすきまなく一列に並べたときの、醜さの最小値を出力してください。

    サンプル

    サンプル1
    入力
    3
1 4
2 4
3 4
    出力
    3

    左から本 $3$ , 本 $2$ , 本 $1$ の順に並べると、すべてのしおり間距離が$3$になります。
    このとき醜さは最小になり、その値は $3$ となります。

    サンプル2
    入力
    3
1 2
1 4
3 4
    出力
    2

    左から本 $3$ , 本 $1$ , 本 $2$ の順に並べると、すべてのしおり間距離が$2$になります。
    このとき醜さは最小になり、その値は $2$ となります。

    サンプル3
    入力
    4
2 10
4 13
8 10
9 13
    出力
    11

    左から本 $3$ , 本 $4$ , 本 $2$ , 本 $1$ の順に並べると、しおり間距離は以下のようになります。

  • 本 $3$ と本 $4$ のしおり間距離 $\ldots 11$
  • 本 $4$ と本 $2$ のしおり間距離 $\ldots 8$
  • 本 $2$ と本 $1$ のしおり間距離 $\ldots 11$
    • このとき醜さは最小になり、その値は $11$ となります。

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。