問題一覧 > 通常問題

No.2056 Powerless Red

レベル : / AI推定難易度 : 800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 170
作問者 : taiga0629kyopro / テスター : ygussany
お気に入りにしたユーザー ProblemId : 8419 / 自分の提出
問題文最終更新日: 2022-09-23 02:12:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 358 (順位表) の他の問題:

Problem Statement

The hero taiga is trying to defeat $N$ monsters. taiga's combat power is $X$, and his mp is $M$. The combat power of monster $i$ is $A_i$. Before fighting the monsters, taiga can use the following spell $0$ or more times.

  • Choose an integer $k$ satisfying $1 \le k \le \mathrm{min}(N,M)$, and for every integer $i$ satisfying $1 \le i \le k$, replace $A_i$ with $\left\lfloor \frac{A_i}{2} \right\rfloor$. Then, replace $M$ with $M-k$.

When taiga fights the monsters, he can defeat all $N$ monsters if and only if $X > \displaystyle \max_{1 \le i\le N}A_i$; otherwise, he loses without defeating even $1$ monster. Can taiga defeat the $N$ monsters by using the spell appropriately before the fight?

Input

$N$ $X$ $M$
$A_1$ $A_2$ $\dots$ $A_N$

  • $1 \le N \le 2×10^5$
  • $1 \le X \le 10^9$
  • $0 \le M \le 10^9$
  • $1 \le A_i \le 10^9$
  • All inputs are integers.

    • Output

    Output Yes if taiga can defeat the $N$ monsters, and No otherwise.

    Sample

    Sample 1
    Input
    3 3 3
6 4 2
    Output
    Yes

    First, choosing $k=2$ gives $A=(3,2,2)$. Next, choosing $k=1$ gives $A=(1,2,2)$, which achieves $\max(A) < X$.

    Sample 2
    Input
    3 3 2
1 1 4
    Output
    No

    To achieve $\max(A) < X$, it is necessary to choose $k=3$ to obtain $A=(0,0,2)$, but this is impossible since $M < 3$.

    Sample 3
    Input
    4 3 3
3 1 4 1
    Output
    Yes

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。