CF1102C Doors Breaking and Repairing

    • 68通过
    • 82提交
  • 题目来源 CodeForces 1102C
  • 评测方式 RemoteJudge
  • 标签
  • 难度 提高+/省选-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    给你一个含有N个数的数组,每一个元素代表一个门的当前防御值。

    每一次你可以对门进行攻击,降低x个点数的防御值;而你的对手(斯拉维克)可以对门进行修复,提升y个点数的防御值。

    当一次你对门的攻击使这个门的防御值小于等于0的时候,这个门就坏掉了,就再也没法修复了。

    问:当你和对手都采取最优的策略的时候,你最多可以砸坏几个门?

    题目描述

    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 $ a_i $ .

    During your move you can try to break one of the doors. If you choose door $ i $ and its current durability is $ b_i $ then you reduce its durability to $ max(0, b_i - 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 $ b_i $ then he increases its durability to $ b_i + y $ (the value $ y $ is given). Slavik cannot repair doors with current durability equal to $ 0 $ .

    The game lasts $ 10^{100} $ 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?

    输入输出格式

    输入格式:

    The first line of the input contains three integers $ n $ , $ x $ and $ y $ ( $ 1 \le n \le 100 $ , $ 1 \le x, y \le 10^5 $ ) — the number of doors, value $ x $ and value $ y $ , respectively.

    The second line of the input contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^5 $ ), where $ a_i $ is the initial durability of the $ i $ -th door.

    输出格式:

    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.

    输入输出样例

    输入样例#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.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。