[CEOI 2023] Grading Server

Luogu

IDLGP9730

Time4000ms

Memory1024MB

DifficultyP7

2023O2优化CEOI（中欧）

竞赛委员会的主席注意到了一些可疑的网络活动 —— 有人想要攻击评测系统！评测系统拥有特定的算力 $c_G$。黑客会尝试将 $c_G$ 降为 $0$（甚至更低）。系统被 $f_G$ 个防火墙保护着，每个防火墙都会将攻击的影响降低 $S$。每个时刻，黑客可以进行以下两种操作之一： - 击破一个防火墙，将 $f_G$ 降低 $1$（但不能低于 $0$），或者 - 用他所有的算力 $c_H$ 攻击系统，将 $c_G$ 降低 $\max(c_H - f_G\cdot S, 0)$。但委员会主席可以反击：击破黑客的 $f_H$ 个防火墙之一；或者用系统的算力攻击黑客，类似地将 $c_H$ 降低 $\max(c_G - f_H \cdot S,0)$。委员会主席和黑客轮流行动，黑客先行动。为了安排防御，委员会成员需要一个程序告诉他们，在 $Q$ 个不同的 $(c_H, f_H, c_G, f_G)$ 情况下，就算委员会主席采取了最优的行动，黑客是否依然能够击垮评测系统（将 $c_G$ 降低为 $0$ 或更低）。 ## Input 第一行两个整数 $S, Q$。接下来 $Q$ 行，每行四个整数 $c_H, f_H, c_G, f_G$ 描述一个情况，分别为黑客的算力和防火墙数量，以及评测系统的算力和防火墙数量。 ## Output 你的程序应当输出 $Q$ 行，每行一个字符串 `YES` 或 `NO`。`YES` 表示无论委员会主席的行动如何，采取最优策略的黑客总能够让 $c_G$ 降为 $0$ 或更低；否则输出 `NO`。 [samples] ## Background 翻译自 CEOI2023 Day1 T2 [Grading Server](https://www.ceoi2023.de/wp-content/uploads/2023/09/2-grading-server.pdf)。 ## Note #### 样例解释考虑样例一的第一个情况： - 首先，黑客攻击评测系统，将 $c_G$ 降低 $42 - 1\cdot 17 = 25$ 为 $8$； - 接下来，委员会主席无法通过攻击降低 $c_H$，所以明智的选择是击破黑客的唯一的防火墙； - 然而，黑客可以继续攻击评测系统，将 $c_G$ 降低 $25$ 为 $-17\leq 0$，击垮评测系统并毁掉第一天比赛日。对于第二个情况： - 一开始，黑客唯一能做的就是击破一个评测系统的防火墙； - 接下来，委员会主席攻击黑客，将 $c_H$ 降低为 $26$； - 接下来两轮，黑客同样只能攻击评测系统的防火墙。同时委员会主席每次攻击黑客，将 $c_H$ 降低为不大于 $0$ 的值，成功防御黑客的攻击。 #### 数据范围与约定 - Subtask 1（5 分）：$S, c_H, c_G, f_H, f_G\leq 75$； - Subtask 2（5 分）：$S, c_H, c_G, f_H, f_G\leq 300$； - Subtask 3（10 分）：$S = 1$； - Subtask 4（25 分）：$S, c_H, c_G, f_H, f_G\leq 2000$； - Subtask 5（20 分）：$S\leq 400$； - Subtask 6（20 分）：$f_H, f_G\leq 125$； - Subtask 7（15 分）：无特殊限制。对于所有数据，$1\leq S\leq 3\times 10 ^ 4$，$1\leq c_H, c_G\leq 10 ^ {12}$，$0\leq f_H, f_G\leq 10 ^ {12}$，$1\leq Q\leq 2.5\times 10 ^ 5$。 #### 限制时间：4s 空间：1GB

Samples

Input #1

17 2
42 1 33 1
42 1 33 7

Output #1

YES
NO

Input #2

1 1
999999999999 999999999999 999999999999 999999999999

Output #2

YES

Input #3

2 1
1000000000000 0 1 1000000000000

Output #3

NO

API Response (JSON)

{
  "problem": {
    "name": "[CEOI 2023] Grading Server",
    "description": {
      "content": "竞赛委员会的主席注意到了一些可疑的网络活动 —— 有人想要攻击评测系统！ 评测系统拥有特定的算力 $c_G$。黑客会尝试将 $c_G$ 降为 $0$（甚至更低）。系统被 $f_G$ 个防火墙保护着，每个防火墙都会将攻击的影响降低 $S$。 每个时刻，黑客可以进行以下两种操作之一： - 击破一个防火墙，将 $f_G$ 降低 $1$（但不能低于 $0$），或者 - 用他所有的算力 $c_H$ 攻",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9730"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "竞赛委员会的主席注意到了一些可疑的网络活动 —— 有人想要攻击评测系统！\n\n评测系统拥有特定的算力 $c_G$。黑客会尝试将 $c_G$ 降为 $0$（甚至更低）。系统被 $f_G$ 个防火墙保护着，每个防火墙都会将攻击的影响降低 $S$。\n\n每个时刻，黑客可以进行以下两种操作之一：\n\n- 击破一个防火墙，将 $f_G$ 降低 $1$（但不能低于 $0$），或者\n- 用他所有的算力 $c_H$ 攻...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments