問題一覧 > 通常問題

No.2796 Small Matryoshka

レベル : / AI推定難易度 : 1650 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 102
作問者 : noya2 / テスター : shobonvip 👑 potato167
お気に入りにしたユーザー ProblemId : 10983 / 自分の提出
問題文最終更新日: 2024-06-28 21:02:28
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 435 (順位表) の他の問題:

Problem Statement

There are $N$ matryoshka dolls on a desk. The $i$-th matryoshka has an inner diameter of $r_i$ and an outer diameter of $R_i$. Here, $r_i\lt R_i$ holds.

Consider performing the following operations A and B, each $0$ or more times in any order, so that exactly $1$ matryoshka remains on the desk.

Operation A

  • Choose distinct matryoshkas $X,Y$ on the desk and remove them from the desk. Here, the outer diameter of $X$ must be less than or equal to the inner diameter of $Y$.
  • Put $X$ inside $Y$. The inner diameter of the resulting new matryoshka equals the inner diameter of $X$, and its outer diameter equals the outer diameter of $Y$.
  • Place the new matryoshka on the desk.

Operation B

  • Choose a matryoshka $X$ on the desk.
  • Choose a real number $k\ (0\lt k\lt 1)$.
  • Scale the size of $X$ by a factor of $k$. The inner and outer diameters of the resulting new matryoshka are $k$ times the original inner and outer diameters, respectively.


Find the minimum possible number of times operation B is performed.

Constraints

  • All inputs are integers.
  • $1\le N\le 2\times 10^5$
  • $1\le r_i\lt R_i\le 10^9$

Input

$N$
$r_1$ $R_1$
$\vdots$
$r_N$ $R_N$

Output

Output the minimum possible number of times operation B is performed.

Sample

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

First, perform operation B to scale the size of the $3$-rd matryoshka by a factor of $0.1$.

Next, perform operation A to put the $1$-st matryoshka inside the $2$-nd matryoshka.

Finally, perform operation A to put the $3$-rd matryoshka inside the $1$-st matryoshka.

Sample 2
Input
4
6 28
2 6
82 86
62 66
Output
0

Sample 3
Input
5
6 28
6 28
6 28
6 28
6 28
Output
4

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