### PROBLEM LINKS

**Author**: Constantine Sokol

**Tester**: Roman Rubanenko

**Editorialist**: Praveen Reddy Vaka

### DIFFICULTY:

simple

### PREREQUISITES:

Greedy Algorithms

### HINT

Sort the array and see if you can figure out some property which will allow you to compute the solution in a greedy manner.

### EXPLANATION

We will solve this in a greedy manner. The key idea is to have as many non-failed packages as possible for this we have to just have maximum number of half-solved (+1 for odd numbers) packages which is possible only if pick up the packages with smaller number of tasks first. Hence we will sort array first and start seeing how many packages can we half-solve without crossing our limit of X. At this moment it is possible that we have not exceeded the quota of X tasks. So we will again start from package will smallest number of tasks and see how many packages we can completely solve.

Here is a complete algorithm.

Sort the array A in ascending order.

Let the value of completedTasks be 0 initially

Let the value of failedPackages be N initially

Now traverse the array A from left to right, for each array entry (denoting a package)

- taskCount = Number of tasks needed to be solved so that the package is not a failure
- if (completedTasks + taskCount > X) break out of the for loop
- increase the value of completedTasks by taskCount
- decrease the value of failedPackages by 1

Let the value of successfulPackages be 0 initially

Now traverse the array A from left to right (you would not need to go beyond the point where you broke out in the previous iteration), for each array entry (denoting a package),

- taskCount = (Number of tasks in the package - Number of tasks needed to be solved so that the package is not a failure) //more tasks that need to be solved to mark the package successfully
- if (completedTasks + taskCount > X) break out of the for loop
- increase the value of completedTasks by taskCount
- increase the value of successfulPackages by 1

Report the values failedPackages and successfulPackages

**Comments on subtasks:**

subtask1: Since A1 + A2 + … + AN ≤ X we can solve all the tasks. So the the number of failed packages will be 0 and the number of successful packages will be N. So the answer is “0 N” for this subtask.

subtask2,3,4: Not sure of any elegant solutions which are worse than our greedy solution in time complexity. If somebody solves this by alternate means we will make a mention here.

### SOLUTIONS

**Setter’s Solution**: MIKE2.cpp

**Tester’s Solution**: MIKE2.cpp

**Editorialist’s Solution**: MIKE2.java