DoorsBreakingandRepairingCodeForces-1102C(思维)

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

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 ai.

During your move you can try to break one of the doors. If you choose door x is given).

During Slavik's move he tries to repair one of the doors. If he chooses door 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 wants to minimize the number of such doors. What is the number of such doors in the end if you both play optimally?

Input

The first line of the input contains three integers y, respectively.

The second line of the input contains i-th door.

Output

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.

Examples

Input

6 3 2
2 3 1 3 4 2

Output

Input

5 3 3
1 2 4 2 3

Output

Input

5 5 6
1 2 6 10 3

Output

Note

Clarifications about the optimal strategy will be ignored.

题目链接：https://vjudge.net/problem/CodeForces-1102C

题意：给你一个含有N个数的数组，每一个元素代表一个门的当前防御值

每一次你可以对门攻击x个点数，而一个神仙可以对门进行y个点数的防御值提升。

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

问：当你和神仙都采取最优的策略的时候，你最多可以砸坏几个门？

思路：

分2种情况

1： X>Y ，这样的话，每一个门你都可以给砸坏。（不用解释吧）

2：当x<=y，这样你的最优策略就是每一次去砸那些当前防御值比你的攻击力x值小的门，一次就可以给砸坏，

而神仙的最优策略使去提升那些当前防御值比你的攻击力x值小的门，一次来减少你的数量。

通过样例我们可以推出公式，如果初始化的时候有cnt个门当前防御值比你的攻击力x值小，那么答案就是(ans+1)/2

我的AC代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define gg(x) getInt(&x)
using namespace std;
typedef long long ll;
inline void getInt(int* p);
const int maxn=1000010;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int n,x,y;
int a[maxn];
int main()
{
    gbtb;
    cin>>n>>x>>y;
    repd(i,1,n)
    {
        cin>>a[i];
    }
    if(x<=y)
    {
        int ans=0;
        repd(i,1,n)
        {
            if(a[i]<=x)
            {
                ans++;
            }
        }
        ans=(ans+1)/2;
        cout<<ans<<endl;
    }else
    {
        cout<<n<<endl;
    }
    return 0;
}

inline void getInt(int* p) {
    char ch;
    do {
        ch = getchar();
    } while (ch == ' ' || ch == '\n');
    if (ch == '-') {
        *p = -(getchar() - '0');
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 - ch + '0';
        }
    }
    else {
        *p = ch - '0';
        while ((ch = getchar()) >= '0' && ch <= '9') {
            *p = *p * 10 + ch - '0';
        }
    }
}