Idea:FP7317
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;
}
Idea:reyleigh
Claim: The damage dealt follows a cyclic pattern, and focusing on full cycles and a prefix of one cycle is optimal.
In one cycle of n seconds: 1. Every cannon fires once, and the shield deflects one cannon per second. 2. The total effective damage in a cycle is: Cycle Damage = Sum of all cannon damages — Maximum cannon damage.
Key Insight
The problem can be split into: 1. Full Cycles: The damage accumulated in multiple full cycles of n seconds. 2. Partial Cycle: Any additional damage required can be obtained by firing for a few more seconds, which can be precomputed using prefix sums of one cycle.
Algorithm
Step 1: Precompute Values 1. Compute Sum, the total damage from all cannons, and Max, the maximum damage by any cannon. 2. Compute Cycle Damage = Sum — Max. 3. Construct a prefix sum array p where p[i] represents the damage dealt in the first i+1 seconds of a single cycle.
Step 2: Answer Queries
For each query h: 1. Calculate the number of full cycles required: Full Cycles = h // Cycle Damage Subtract the damage contributed by full cycles: Remaining Damage = h — (Full Cycles * Cycle Damage). 2. If Remaining Damage > 0, use binary search on p to find the minimum seconds required to cover it. 3. Combine the results: Total Time = (Full Cycles * n) + Partial Cycle Time.
Complexity Analysis 1. Preprocessing: O(n) per test case for computing Cycle Damage and prefix sums. 2. Query Handling: O(log n) per query using binary search. 3. Overall Complexity: O(n + q log n) per test case.
Since the sum of all n and q over all test cases is at most 2 * 10^5, the solution is efficient.
#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';
}
}
}
Idea:pramod_17
Idea:sanju77
Idea:wuhudsm
Idea:pramod_17
