Problem Description

You are tasked with finding the minimum number of bandages required to defeat a dragon using a sword. The sword deals:

• 1 damage if the i-th attack is not divisible by 3.
• 2 damage if the i-th attack is divisible by 3.

If your health becomes less than 0 at any point, you must use a bandage to restore it.

Solution Approach

You can solve this problem using a while loop to determine the minimum number of bandages required.

void solve(){
    int h,k,n;cin>>h>>k>>n;
    int ans = 0, l = k, r = 1;
    while(h > 1){
        r++;
        k -= n;
        if(k <= 0){
            k = l - n;
            ans++;
        }
        if(r % 3 == 0){
            h-=2;
        }else{
            h--;
        }
    }
    cout<<ans<<endl;
}

Good problem! :
Average problem :
Bad problem... :

Problem Statement

OwlBear is attacking a village. The village has n cannons, each dealing a_i damage. At the k-th second, the OwlBear is protected from the cannon at index (*k*-1) mod n. Given q queries, each with a damage threshold h, find the minimum number of seconds required to deal at least h damage.

Analysis

The key idea is to precompute the prefix sums of the damage dealt in each second, excluding the blocked cannon. Let sum be the total damage all cannons can deal in one second. Then, the damage dealt in the i-th second is sum - a[i % n]. We can create a prefix sum array p where p[i] stores the total damage dealt from second 1 to second i.

To answer a query with damage h, we can first calculate how many full cycles of n seconds are needed. This can be done by ans = h / p[n-1]. The remaining damage is h -= (ans * p[n-1]). Then, we multiply ans by n to get the number of seconds in full cycles. If there is still remaining damage (h > 0), we use binary search (specifically lower_bound) on the prefix sum array p to find the minimum number of additional seconds needed.

Solution

1. Read n and the damage array a.
2. Calculate the total damage sum and create the prefix sum array p where p[i] = sum - a[i] and accumulate the prefix sums.
3. For each query h:
   • Calculate the number of full cycles: ans = h / p[n-1].
   • Update the remaining damage: h -= (ans * p[n-1]).
   • Multiply ans by n.
   • If h > 0, use lower_bound on p to find the index of the first value greater than or equal to h. Add this index + 1 to ans to get the final answer.

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tc;
    cin >> tc;
    while (tc--) {
        int n;
        cin >> n;
        vector<ll> a(n), p(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        ll sum = 0;
        for (int i = 0; i < n; i++) sum += a[i];
        for (int i = 0; i < n; i++) p[i] = sum - a[i];
        for (int i = 1; i < n; i++) p[i] += p[i - 1];
        int q;
        cin >> q;
        while (q--) {
            ll h;
            cin >> h;
            ll ans = h / p[n - 1];
            h -= (ans * p[n - 1]);
            ans *= n;
            if (h) ans += lower_bound(p.begin(), p.end(), h) - p.begin()+1;
            cout << ans << '\n';
        }
    }
}

Good problem! :
Average problem :
Bad problem... :

Good problem! :
Average problem :
Bad problem... :

Good problem! :
Average problem :
Bad problem... :

Good problem! :
Average problem :
Bad problem... :

Good problem! :
Average problem :
Bad problem... :