33OJ
登录 注册

#P17495. [ICPC 2026 Wuhan I] Believe in You

    ID: 20223 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 显示难度普及− 上传者: 标签>模拟贪心Special JudgeICPC2026省赛/邀请赛湖北

[ICPC 2026 Wuhan I] Believe in You

题目描述

《杀戮尖塔 2》是一款风靡全球的游戏。游戏中,你需要扮演攀爬高塔的角色,并用卡牌击败沿途的怪物,直到获得胜利。

现在你不得不面对一个强大的敌人,很不幸的是,你剩下的生命值无法抵挡任何一次未被格挡的攻击。幸运的是,你知道了未来 nn 回合内你能抽到的牌和怪物的行动,你希望快速判断能否在 nn 回合内击败怪物,且自己不会死亡。

游戏的卡牌分为两种:

  • 打击(Strike):打出会造成 SS 点伤害。
  • 防御(Defend):打出会为自己提供 DD 点格挡。

击败敌人的条件是你造成的总伤害大于等于敌人的生命值 HPHP。

在第 ii 个回合,玩家的行动定义为:

  • 清空当前手上的牌以及上一回合剩余的格挡(如果有)。
  • 获得 aia_i 张打击,5−ai5-a_i 张防御。
  • 选择不超过 33 张卡牌打出,每张卡牌只能被打出一次。
  • 结束行动。

在第 ii 个回合,怪物的行动定义为:

  • 对玩家造成 kik_i 点伤害。一旦 kik_i 大于玩家当前的格挡值,你就会死亡,游戏立即结束。
  • 结束行动。

在每个回合,双方的行动顺序是:

  1. 玩家行动。
  2. 若怪物死亡,则玩家胜利,游戏结束。
  3. 怪物行动。
  4. 若玩家死亡,则游戏结束。

你需要判断在 nn 个回合内你能否击败怪物。若可以,输出 “Yes”,并输出最快在哪个回合能击败怪物;若不能在 nn 回合内击败怪物或者中途玩家死亡,则输出 “No”。

输入格式

第一行包含一个整数 nn(1≤n≤1001 \le n \le 100),表示预测的游戏回合数。

第二行包含三个正整数 S,D,HPS,D,HP(1≤S,D≤101 \le S,D \le 10,1≤HP≤1001 \le HP \le 100),分别表示打击造成的伤害、防御提供的格挡和怪物的血量。

接下来 nn 行,每行包含两个非负整数 ai,kia_i,k_i(0≤ai≤50 \le a_i \le 5,0≤ki≤500 \le k_i \le 50),描述第 ii 轮的抽牌情况(抽到 aia_i 张打击)和怪物的攻击伤害。

输出格式

若能在 nn 回合内击败怪物,输出一行 “Yes”,并在下一行输出一个整数,表示最快在哪个回合能击败怪物。

若不能在 nn 回合内击败怪物或者中途玩家死亡,则输出一行 “No”。

4
5 5 25
4 0
1 10
2 12
2 12
Yes
3
5
1 5 4
1 4
2 0
5 3
0 4
0 1
Yes
3
4
1 5 5
0 1
3 3
0 5
2 1
No
5
1 4 4
5 4
1 5
3 1
4 4
5 4
No
4
4 5 4
1 2
1 0
4 5
1 1
Yes
1

提示

对于第一组样例,最优的打牌策略如下:

  • 第一回合:玩家抽到 44 张打击,11 张防御。怪物攻击力为 00。玩家打出 33 张打击,造成 1515 点伤害。回合结束时怪物剩余 1010 点血量。玩家受到 00 点伤害,存活。
  • 第二回合:玩家抽到 11 张打击,44 张防御。怪物攻击力为 1010。为了存活,玩家必须打出 22 张防御获得 1010 点格挡,剩余 11 次出牌机会打出 11 张打击,造成 55 点伤害。回合结束时怪物剩余 55 点血量。玩家受到 1010 点攻击,被格挡抵消,存活。
  • 第三回合:玩家抽到 22 张打击,33 张防御。由于只要怪物死亡就不会进行攻击阶段,玩家可以直接打出 22 张打击,造成 1010 点伤害。此时累计总伤害达到 3030,怪物死亡,游戏在第 33 回合结束。