Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- int search(const int *monsters, long long leftPos, long long rightPos);
- bool hitsCheck(const int *monsters, long long hits);
- int p = 0;
- int q = 0;
- int n = 0;
- int main() {
- std::cin >> n >> p >> q;
- int monsters[n] = {};
- long long sum = 0;
- for (int i = 0; i < n; ++i) {
- std::cin >> monsters[i];
- sum += monsters[i];
- }
- long long maxHits = sum / p + 1;
- int minHits = search(monsters, 0, maxHits);
- std::cout << minHits;
- return 0;
- }
- int search(const int *monsters, long long leftPos, long long rightPos) {
- if (leftPos == rightPos)
- return leftPos;
- if (leftPos + 1 == rightPos) {
- return hitsCheck(monsters, leftPos) ? leftPos : rightPos;
- }
- long long newPos = (leftPos + rightPos) / 2;
- if (hitsCheck(monsters, newPos)) {
- return search(monsters, leftPos, newPos);
- }
- return search(monsters, newPos, rightPos);
- }
- bool hitsCheck(const int *monsters, long long hits) {
- long long damage = hits * q;
- long long extraHits = 0;
- for (int i = 0; i < n; ++i) {
- if (p == q) {
- if (monsters[i] - damage > 0) return false;
- continue;
- }
- if (monsters[i] - damage > 0) {
- extraHits += std::ceil(static_cast<double> ((monsters[i] - damage)) / static_cast<double> (p - q));
- }
- }
- return extraHits <= hits;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement