問題一覧 > 通常問題

No.3640 Babies don't like Bat Beat

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 12
作問者 : kazuppa / テスター : Tamiji153 Unbakedbread
ProblemId : 13648 / Paken新入生コンday2 (順位表) / 自分の提出
問題文最終更新日: 2026-08-25 18:36:50
Paken新入生コンday2の他の問題:

問題文

$N$ 人の子供がいます。子供 $i$ は曲のスピード（以下、BPM）が $L_i$ 以上 $R_i$ 未満の曲を好み、 $R_i$ 以上 $2L_i$ 未満の曲を嫌います。（ここで、$L_i\leq R_i\leq 2L_i$ が保証されています。）

また、任意の子供についてBPMが $x$ の曲と $2x$ の曲が好きかどうかは同値です。

これからあなたは子供の内何人かと正の実数 $x$ を選び、選んだ子供たちのみにBPMが $x$ の曲を聞かせます。この時、選んだ子供全員がこの曲を好んでいた場合、またその時に限り成功とします。

適切に子供と曲のBPMを選んだ時、最大子供何人で成功させることができるかを求めてください。

制約

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

小課題

この問題にはサブタスクによる部分点が設定されています。

小課題名 配点 制約
小課題115 %$N=2$
小課題210 %$N\leq18$
小課題310 %$100\leq L_i\leq R_i\leq200$
小課題420 %$100\leq L_i\leq R_i\leq400$
小課題520 %$R_i\leq10^5$
小課題625 %追加の制約はない

入力

$N$
$L_1\ R_1$
$L_2\ R_2$
$\vdots$
$L_N\ R_N$

出力

答えを一行に出力してください。

サンプル

サンプル1
入力
5
220 300
120 200
169 231
120 240
170 250
出力
4

子供 $1,2,4,5$ と $x=240$ を選ぶことで $4$ 人で成功させることができます。

$4$ 人より多い人数で成功させることはできないので、$4$ が答えになります。

サンプル2
入力
3
240 240
250 250
260 260
出力
0

どの子供と $x$ を選んでも成功させることができません。

サンプル3
入力
6
591 1000
839 1472
8293 12049
6561 10201
1 2
4893 9020
出力
6

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