公式

C - バッテリー残量と省エネモード / Battery Level and Power Saving Mode 解説 by physics0523


以下のシミュレーションを行えばよいです。

  • 各タスクについて、順に以下の通りにモードを決定する。
    • \(H \le A\) である場合、省エネモードが使えるのでそうする。
    • そうでなく \(H \le M\) である場合、パワフルモードを使う必要がある。
      • \(M\) を \(\lfloor M/2 \rfloor\) で置き換える。
    • そうでない場合、このタスクを処理することができないため、 -1 を出力して終了する。

時間計算量は \(O(N)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int main(){
  ll N,M,A,res=0;
  cin >> N >> M >> A;
  for(ll i=0;i<N;i++){
    ll H;
    cin >> H;
    if(H<=A){continue;}
    else if(H<=M){
      M/=2;
      res++;
    }
    else{cout << "-1\n"; return 0;}
  }
  cout << res << "\n";
  return 0;
}