Advertisement
Guest User

Untitled

a guest
Feb 27th, 2020
76
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.48 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4.  
  5. int search(const int *monsters, long long leftPos, long long rightPos);
  6.  
  7. bool hitsCheck(const int *monsters, long long hits);
  8.  
  9. int p = 0;
  10. int q = 0;
  11. int n = 0;
  12.  
  13. int main() {
  14.     std::cin >> n >> p >> q;
  15.  
  16.     int monsters[n] = {};
  17.     long long sum = 0;
  18.     for (int i = 0; i < n; ++i) {
  19.         std::cin >> monsters[i];
  20.         sum += monsters[i];
  21.     }
  22.  
  23.     long long maxHits = sum / p + 1;
  24.  
  25.     int minHits = search(monsters, 0, maxHits);
  26.     std::cout << minHits;
  27.  
  28.     return 0;
  29. }
  30.  
  31. int search(const int *monsters, long long leftPos, long long rightPos) {
  32.     if (leftPos == rightPos)
  33.         return leftPos;
  34.  
  35.     if (leftPos + 1 == rightPos) {
  36.         return hitsCheck(monsters, leftPos) ? leftPos : rightPos;
  37.     }
  38.  
  39.     long long newPos = (leftPos + rightPos) / 2;
  40.     if (hitsCheck(monsters, newPos)) {
  41.         return search(monsters, leftPos, newPos);
  42.     }
  43.  
  44.     return search(monsters, newPos, rightPos);
  45.  
  46. }
  47.  
  48. bool hitsCheck(const int *monsters, long long hits) {
  49.     long long damage = hits * q;
  50.     long long extraHits = 0;
  51.     for (int i = 0; i < n; ++i) {
  52.         if (p == q) {
  53.             if (monsters[i] - damage > 0) return false;
  54.             continue;
  55.         }
  56.  
  57.         if (monsters[i] - damage > 0) {
  58.             extraHits += std::ceil(static_cast<double> ((monsters[i] - damage)) / static_cast<double> (p - q));
  59.         }
  60.     }
  61.  
  62.     return extraHits <= hits;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement