問題一覧 > 通常問題

No.180 Beautiful Whitespace (2)

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 114
作問者 : ぴろず
お気に入りにしたユーザー ProblemId : 425 / 自分の提出
問題文最終更新日: 2026-06-26 17:58: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
yukicoder contest 96 (順位表) の他の問題:

Problem Statement

Taro's younger brother Jiro is absorbed in writing beautiful programs in the esoteric programming language Whitespace.
Whitespace uses only spaces, tabs, and newlines for its syntax and ignores everything else.

Taro used to mix full-width spaces into his source code, but Jiro noticed that this causes errors on some interpreters.
Jiro has written source code consisting of $N$ lines. The $i$-th line contains $a_i$ spaces and $b_i$ tabs. The source code contains no characters other than spaces, tabs, and newlines.

Jiro wants to minimize the "ugliness" of the source code by changing the tab width $x(x$ is a positive integer$)$ of his editor.
The "ugliness" of the source code is the maximum line width of the source code minus the minimum line width.
More precisely, for a tab width $x(x$ is a positive integer$)$, the "ugliness" $f(x)$ is given by the following formula.
$\displaystyle f(x) = \left( \max_{1 \leq i \leq N} (a_i + b_ix) \right) - \left( \min_{1 \leq i \leq N} (a_i + b_ix) \right)$
Note that, unlike in ordinary editors, the positions of tabs and so on do not affect the width; the "ugliness" is determined only by the numbers of spaces and tabs.

Write a program that outputs the smallest positive integer $x$ among those that minimize the "ugliness" $f(x)$ of the source code.

Input

$N$
$a_1$ $b_1$
$\vdots$
$a_N$ $b_N$
The $1$st line gives $N$, the number of lines in the source code Jiro wrote.
The following $N$ lines give information on each line of the source code: the $i$-th line has $a_i$ spaces and $b_i$ tabs.

$1 \leq N \leq 1000$
$0 \leq a_i, b_i \leq 10^9$
Jiro's source code contains no characters other than spaces, tabs, and newlines.
Jiro's source code is not necessarily grammatically valid Whitespace.

Output

Output the smallest positive integer $x$ among those that minimize the "ugliness" $f(x)$ of the source code. Print a newline at the end.

Sample

Sample 1
Input
2
1 1
3 0
Output
2

The $1$st line has $1$ space and $1$ tab.
The $2$nd line has $3$ spaces and $0$ tabs.
With a tab width of $2$, the width of the $1$st line is $1 + 1 \times 2 = 3$ and the width of the $2$nd line is $3 + 0 \times 2 = 3$, so the "ugliness" is 0.
Also, $2$ is the only tab width that makes the "ugliness" 0, so output $2$.

Sample 2
Input
4
0 0
0 0
0 0
0 0
Output
1

All $4$ lines are empty.
In this case, $f(x)=0$ for any $x(\geq 1)$.
We output the smallest $x$ among those that minimize $f(x)$, so output $1$.

Sample 3
Input
2
1 4
9 1
Output
3

$f(x)$ attains its minimum only at $x = 3$, where $f(x) = 13 - 12 = 1$.

Sample 4
Input
10
4321123 46
9506183 4
2469242 61
1111211 72
1234721 71
3333474 54
1111260 72
123559 80
1728545 67
7407433 21
Output
123456

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