問題一覧 > 通常問題

No.2796 Small Matryoshka

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 92
作問者 : noya2noya2 / テスター : shobonvipshobonvip 👑 potato167potato167
2 ProblemId : 10983 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-06-28 21:02:28

問題文

机の上に $N$ 個のマトリョーシカが置かれており、 $i$ 番目のマトリョーシカの内径は $r_i$ 、外径は $R_i$ です。ここで $r_i\lt R_i$ を満たします。

次の操作A,Bのいずれかをそれぞれ好きな順序で $0$ 回以上行って、机の上のマトリョーシカを $1$ 個にすることを考えます。

操作 A

  • 机の上にある異なるマトリョーシカ $X,Y$ を選び、机の上から取り除く。ここで $X$ の外径は $Y$ の内径以下でなくてはならない。
  • $Y$ の中に $X$ を入れる。こうしてできた新しいマトリョーシカの内径は $X$ の内径に一致し、外径は $Y$ の外径に一致するものとする。
  • 新しいマトリョーシカを机の上に置く。

操作 B

  • 机の上にあるマトリョーシカ $X$ を選ぶ。
  • 実数 $k\ (0\lt k\lt 1)$ を選ぶ。
  • $X$ の大きさを $k$ 倍にする。こうしてできた新しいマトリョーシカの内径と外径はもとの内径と外径のそれぞれ $k$ 倍とする。


操作B を行う回数として考えられる最小値を求めてください。

制約

  • 入力はすべて整数
  • $1\le N\le 2\times 10^5$
  • $1\le r_i\lt R_i\le 10^9$

入力

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

出力

操作B を行う回数として考えられる最小値を出力してください。

サンプル

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

まず操作Bを行って $3$ 番目のマトリョーシカの大きさを $0.1$ 倍にします。

次に操作Aを行って $1$ 番目のマトリョーシカを $2$ 番目のマトリョーシカの中に入れます。

最後に操作Aを行って $3$ 番目のマトリョーシカを $1$ 番目のマトリョーシカの中に入れます。

サンプル2
入力
4
6 28
2 6
82 86
62 66
出力
0

サンプル3
入力
5
6 28
6 28
6 28
6 28
6 28
出力
4

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