問題一覧 > 通常問題

No.771 Bookmarks

レベル : / AI推定難易度 : 1150 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 132
作問者 : Shuz* / テスター : tatyam
お気に入りにしたユーザー ProblemId : 2580 / 自分の提出
問題文最終更新日: 2026-10-19 08:26:54
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2018 (順位表) の他の問題:

Problem Statement

Shuz* has $N$ books with bookmarks inserted in them, and the $i$-th book is called book $i$.
In each book $i$, a bookmark is inserted at the position whose thickness from the front cover is $A_i$.
The thickness of a bookmark is considered to be $0$. Also, the thickness of each book $i$ from its front cover to its back cover is $B_i$.

These books had been left untouched for a long time, but Shuz* now wants to put these $N$ books on a bookshelf, lining them up in a row with no gaps and with their front covers on the left.
To make them look good, when lining up the $N$ books in a row with no gaps and with their front covers on the left, Shuz* wants to make the ugliness, defined below, as small as possible.

  • For $2$ adjacent books, the thickness from the bookmark of the left book to the bookmark of the right book is called the bookmark distance.
  • When the $N$ books are lined up in a row with no gaps and with their front covers on the left, the largest of the $N-1$ bookmark distances is called the ugliness of that arrangement.


    • $\ N$ books are lined up in a row with no gaps and with their front covers on the left. What is the minimum possible ugliness?

    Constraints

  • $2 \le N \le 18$
  • $1 \le A_i \le B_i \le 1000$
  • All input values are integers

    • Input

    The input is given from standard input in the following format. 
    $N$
$A_1\ B_1$
$A_2\ B_2$
$\vdots$
$A_N\ B_N$

    $\ 1$ The first line contains $N$, the number of books with bookmarks that Shuz* has.
    In the following $N$ lines, the $1 + i$-th line contains $A_i,\ B_i$ separated by a space.

    Output

    Output the minimum value of the ugliness when the $N$ books are lined up in a row with no gaps and with their front covers on the left.

    Sample

    Sample 1
    Input
    3
1 4
2 4
3 4
    Output
    3

    If the books are arranged in the order book $3$ , book $2$ , book $1$ from the left, all bookmark distances are $3$.
    In this case the ugliness is minimized, and its value is $3$.

    Sample 2
    Input
    3
1 2
1 4
3 4
    Output
    2

    If the books are arranged in the order book $3$ , book $1$ , book $2$ from the left, all bookmark distances are $2$.
    In this case the ugliness is minimized, and its value is $2$.

    Sample 3
    Input
    4
2 10
4 13
8 10
9 13
    Output
    11

    If the books are arranged in the order book $3$ , book $4$ , book $2$ , book $1$ from the left, the bookmark distances are as follows.

  • Between book $3$ and book $4$, the bookmark distance is $\ldots 11$
  • Between book $4$ and book $2$, the bookmark distance is $\ldots 8$
  • Between book $2$ and book $1$, the bookmark distance is $\ldots 11$
    • In this case the ugliness is minimized, and its value is $11$.

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