PROBLEM LINK:
Author: Sandeep Singh
Tester: Arkapravo Ghosh
Editorialist: Sandeep Singh
DIFFICULTY:
SIMPLE
PREREQUISITES:
Priority Queue
PROBLEM:
There are N soldiers with power levels A_1, A_2....., A_N, When ith soldier attacks Pain, his strength ( Z ) gets reduced by the corresponding power of the attacking soldier. The power of the attacking soldier also gets halved. What is the minimum no. of attacks required, if at all possible, to defeat Pain.
QUICK EXPLANATION:
The solution to this problem is a simple implementation of a priority queue. The highest power, P_M, is popped and subtracted from strength Z and [P_M/2] is pushed in the queue. This is repeated until Z reduces to 0 or less or P_M pops out to be 0. The answer is the no. of times the loop runs or āEvacuateā based on the value of Z after the above operation is over.
EXPLANATION:
To minimize the no. of attacks, the optimum choice would be to attack with the current highest power available. To get the highest power each time in optimal time we insert all the powers in the Priority Queue. After that, we keep popping out the highest power from the Queue returning half of it to the queue till Pain is defeated or no more attacks are possible i.e. all powers are reduced to 0 (Max popped power is 0).
If Z is reduced to 0 or less, this means Pain can be defeated and the minimum no. of attacks required to do so is the no. of times the loop was run or Priority Queue was popped. Else Pain cannot be defeated and āEvacuateā is to be printed.
Working with Priority queue is very simple and self explanatory. Below is a snippet of working of priority queue A.
Time complexity is O(N * logN * logA)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
//freopen("ip5.in", "r", stdin);
//freopen("op5.out", "w", stdout);
int t ;
cin>>t;
while(t--) {
int N, i,Z,temp;
cin>>N>>Z;
priority_queue<int> A;
for(i=0;i<N;i++){
cin>>temp;
A.push(temp);
}
int hits=0;
while(A.top()!=0 && Z>0){
hits++;
temp = A.top();
Z-=temp;
A.pop();
A.push(temp/2);
}
if(Z>0)
cout<<"Evacuate"<<endl;
else
cout<<hits<<endl;
}
return 0;
}
Tester's Solution
CodeChef submission 26040101 (C++14) plaintext list. Status: AC, problem SAVKONO, contest
ENAU19TS. By horsbug98 (horsbug98), 2019-08-20 22:22:53.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
cin.tie(0); cout.tie(0);
#define T int tt; cin>>tt; while(tt--)
int main() {
fastio;
//find_primes();
//binomial_pre();
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
T {
int n, z, x, res = 0;
cin >> n >> z;
priority_queue<int> pq;
for(int i = 0; i < n; ++i) {
cin >> x;
pq.push(x);
}
while(!pq.empty()) {
if(z <= 0)
break;
x = pq.top(); pq.pop();
z -= x;
x >>= 1;
if(x) pq.push(x);
++res;
}
if(z > 0)
cout << "Evacuate\n";
else
cout << res << '\n';
}
return 0;
}
