레이팅 미적용설명
JOI 国にはN 人の住人がおり,1 からN までの番号が付けられている.住人i (1 ≦i ≦N) は数直線上の
座標Xi に住んでおり,その影響力はEi である.同じ座標に複数の住人が住んでいることもある.影響力が
高い住人ほど宣伝効果が大きい一方で,本を買うのに慎重になる.
理恵さんは情報科学の本を出版した.本を多くの人に買ってもらうため,何人かの住人に献本をすること
ができる.住民i (1 ≦i ≦N) に献本した場合,住人i は理恵さんの本を手に入れる.さらに,まだ理恵さ
んの本を持っていない住人のうち,次の条件を満たすようなすべての住人j (1 ≦j ≦N) は理恵さんの本を
買って手に入れる.
住人i と住人j との数直線上での距離がEi −E j 以下である.すなわち|Xi −Xj| ≦Ei −E j である.
もし理恵さんの本がJOI 国のすべての住人に読まれれば,情報オリンピックの知名度は大きく向上するだ
ろう.JOI 国の住人全員が理恵さんの本を手に入れるために,最小で何人に献本する必要があるかを求める
プログラムを作成せよ.
제약
• 1 ≦N ≦500 000.
• 1 ≦Xi ≦109 (1 ≦i ≦N).
• 1 ≦Ei ≦109 (1 ≦i ≦N).
• 入力される値はすべて整数である.
- (10 点) E1 = E2 = · · · = EN.
- (23 点) N ≦16.
- (36 点) N ≦1 000.
- (31 点) 追加の制約はない.
입력 형식
入力は以下の形式で標準入力から与えられる.
N
X1 E1
X2 E2
...
XN EN
출력 형식
標準出力に,理恵さんが献本すべき住人の人数の最小値を1 行で出力せよ.
第22 回日本情報オリンピック(JOI 2022/2023) 本選
2023 年2 月12 日(オンライン開催)
예제 1
입력
4
4 2
2 3
3 4
6 5
출력
2
예제 2
입력
3
7 10
10 10
7 10
출력
2
예제 3
입력
10
31447678 204745778
430226982 292647686
327782937 367372305
843320852 822224390
687565054 738216211
970840050 766211141
563662348 742939240
103739645 854320982
294864525 601612333
375952316 469655019
출력
5
문제 정보