No.180 Beautiful Whitespace (2)
タグ : / 解いたユーザー数 114
作問者 :
ぴろず
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もしくは右上の雲マークをクリックしてアカウントを作成してください。