CFR 492 D. Vanya and Computer Game ( Binary Search )

Problem - 492D - Codeforces

題意：
甲 1 / X 秒攻擊一次，乙 1 / Y 秒攻擊一次。
對於第 i 隻怪獸，其耐打 A[ i ] 次，問最後一擊是誰的。

制約：
1 ≤ N ≤ 1e5
1 ≤ X, Y ≤ 1e6
1 ≤ A[ i ] ≤ 1e9

解法：
二分搜打死怪獸的最早時間。
只要知道這個時間，判斷一下餘數，就可以知道最後一擊是誰的。
只是，如果是分數的話就不像整數，會需要判情形。
因為等倍率放大，結束時間的餘數不會改變，所以考慮當作甲 Y 秒攻擊一次，乙 X 秒攻擊一次。

複雜度：
O( N * lg MAXA )

#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 1e5 );

int N, X, Y;
int A;

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> X >> Y;
  for( int i = 0; i < N; ++i ) {
    cin >> A;
    long long lb = -1, ub = 1LL << 50;
    while( lb + 1 != ub ) {
      long long mid = lb + ub >> 1;
      ( mid / Y + mid / X >= A ? ub : lb ) = mid;
    }
    if( ub % X == 0 and ub % Y == 0 ) {
      cout << "Both" << endl;
    } else if( ub % Y == 0 ) {
      cout << "Vanya" << endl;
    } else {
      cout << "Vova" << endl;
    }
  }
  return 0;
}