CF1102C.Doors Breaking and Repairing
普及-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are policeman and you are playing a game with Slavik. The game is turn-based and each turn consists of two phases. During the first phase you make your move and during the second phase Slavik makes his move.
There are n doors, the i-th door initially has durability equal to ai.
During your move you can try to break one of the doors. If you choose door i and its current durability is bi then you reduce its durability to max(0,bi−x) (the value x is given).
During Slavik's move he tries to repair one of the doors. If he chooses door i and its current durability is bi then he increases its durability to bi+y (the value y is given). Slavik cannot repair doors with current durability equal to 0.
The game lasts 10100 turns. If some player cannot make his move then he has to skip it.
Your goal is to maximize the number of doors with durability equal to 0 at the end of the game. You can assume that Slavik wants to minimize the number of such doors. What is the number of such doors in the end if you both play optimally?
你是一名警察,正在与斯拉维克进行一场游戏。游戏采用回合制,每个回合包含两个阶段:第一阶段由你行动,第二阶段由斯拉维克行动。
共有 n 扇门,第 i 扇门的初始耐久度为 ai。
在你的行动阶段,你可以尝试破坏其中一扇门。若你选择第 i 扇门,且其当前耐久度为 bi,则其耐久度将变为 max(0,bi−x)(其中 x 是给定值)。
在斯拉维克的行动阶段,他会尝试修复其中一扇门。若他选择第 i 扇门,且其当前耐久度为 bi,则其耐久度将变为 bi+y(其中 y 是给定值)。斯拉维克无法修复当前耐久度为 0 的门。
游戏共进行 10100 回合。若某位玩家无法执行其行动,则必须跳过该回合。
你的目标是最大化游戏结束时耐久度恰好为 0 的门的数量。假设斯拉维克的目标是最小化此类门的数量。若双方均采取最优策略,游戏结束时耐久度为 0 的门的数量是多少?
输入格式
The first line of the input contains three integers n, x and y (1≤n≤100, 1≤x,y≤105) — the number of doors, value x and value y, respectively.
The second line of the input contains n integers a1,a2,…,an (1≤ai≤105), where ai is the initial durability of the i-th door.
输入的第一行包含三个整数 n、x 和 y(1≤n≤100,1≤x,y≤105),分别表示门的数量、数值 x 和数值 y。
输入的第二行包含 n 个整数 a1,a2,…,an(1≤ai≤105),其中 ai 表示第 i 扇门的初始耐久度。
输出格式
Print one integer — the number of doors with durability equal to 0 at the end of the game, if you and Slavik both play optimally.
输出一个整数——如果双方都采取最优策略,游戏结束时耐久度为 0 的门的数量。
输入输出样例
输入#1
6 3 2 2 3 1 3 4 2
输出#1
6
输入#2
5 3 3 1 2 4 2 3
输出#2
2
输入#3
5 5 6 1 2 6 10 3
输出#3
2
说明/提示
Clarifications about the optimal strategy will be ignored.
关于最优策略的澄清将被忽略。
输入解题思路,AI测评打分。不知道怎么写?