#F. [CZOI2020 / WJOI2020 E] 勇士斗恶龙

    传统题 1000ms 256MiB

[CZOI2020 / WJOI2020 E] 勇士斗恶龙

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 X 穿越到了异世界,国王命令他招揽勇士,杀死恶龙,救回公主。

异世界是高度数据化的。恶龙有一个攻击力 ATKATK,一个生命值 HPHP。类似的, 每个勇士也有一个攻击力 AiA_i,一个生命值 HiH_i

战斗是回合制的,并且每次只能由一个勇士和恶龙单挑。战斗中,每个回合 恶龙的生命值会减去这个勇士的攻击力,这个勇士的生命值会减去恶龙的攻击力。如果回合结束的时候恶龙的生命值小于等于 00,那么恶龙就被杀死了;如果这个勇士的生命值小于等于 00,那么这个勇士就被击败了,需要换上另一个勇士继续战斗。当然,如果恶龙还没有被杀死,勇士却全部被击败了,那么这场战役就彻底失败了。

不过聪明的小 X 安排了一个特殊的战术:在一名勇士被击败后立刻让另一名勇士发起攻击,这样恶龙在勇士们的车轮战术下疲于招架,受到第二个勇士的伤害变为两倍,受到第三个勇士的伤害变为三倍……以此类推。

现在一共有 nn 名勇士报名,小 X 想问问你,如果合理安排勇士出战的顺序,最少要招揽多少名勇士才能杀死恶龙?

输入格式

第一行为一个正整数 nn,表示一共有 nn 名勇士报名。

第二行两个正整数 ATKATKHPHP 表示恶龙的攻击力和生命值。

接下来共有n 行,每行两个正整数 AiA_iHiH_i 表示这名勇士的攻击力和生命值。

输出格式

输出一个整数,表示最少要招揽多少名勇士才能杀死恶龙。如果不可能杀死恶龙,输出 Fail

2 
1 9 
2 2 
1 1
2

数据范围

$1 \le n \le 10^5,1 \le ATK,H_i,A_i \le 10^6,1 \le HP \le 10^{18}$。

二分答案

未认领
状态
已结束
题目
11
开始时间
2023-11-10 0:00
截止时间
2023-12-4 23:59
可延期
24 小时