You are entering a competition, and are given two positive integers initialEnergy and initialExperience denoting your initial energy and initial experience respectively.
You are also given two 0-indexed integer arrays energy and experience, both of length n.
You will face n opponents in order. The energy and experience of the ith opponent is denoted by energy[i] and experience[i] respectively. When you face an opponent, you need to have both strictly greater experience and energy to defeat them and move to the next opponent if available.
Defeating the ith opponent increases your experience by experience[i], but decreases your energy by energy[i].
Before starting the competition, you can train for some number of hours. After each hour of training, you can either choose to increase your initial experience by one, or increase your initial energy by one.
Return the minimum number of training hours required to defeat all n opponents.
Example 1:
Input: initialEnergy = 5, initialExperience = 3, energy = [1,4,3,2], experience = [2,6,3,1] Output: 8 Explanation: You can increase your energy to 11 after 6 hours of training, and your experience to 5 after 2 hours of training. You face the opponents in the following order: - You have more energy and experience than the 0th opponent so you win. Your energy becomes 11 - 1 = 10, and your experience becomes 5 + 2 = 7. - You have more energy and experience than the 1st opponent so you win. Your energy becomes 10 - 4 = 6, and your experience becomes 7 + 6 = 13. - You have more energy and experience than the 2nd opponent so you win. Your energy becomes 6 - 3 = 3, and your experience becomes 13 + 3 = 16. - You have more energy and experience than the 3rd opponent so you win. Your energy becomes 3 - 2 = 1, and your experience becomes 16 + 1 = 17. You did a total of 6 + 2 = 8 hours of training before the competition, so we return 8. It can be proven that no smaller answer exists.
Example 2:
Input: initialEnergy = 2, initialExperience = 4, energy = [1], experience = [3] Output: 0 Explanation: You do not need any additional energy or experience to win the competition, so we return 0.
Constraints:
n == energy.length == experience.length1 <= n <= 1001 <= initialEnergy, initialExperience, energy[i], experience[i] <= 100program main
implicit none
integer :: initialEnergy, initialExperience, energy(100), experience(100)
integer :: i, j, n, totalHours, minHours
read(*,*) initialEnergy
read(*,*) initialExperience
read(*,*) n
do i = 1, n
read(*,*) energy(i)
read(*,*) experience(i)
end do
! Initialize variables
totalHours = 0
minHours = 1000000
! Loop over all opponents
do i = 1, n
! Check if current opponent can be defeated
if (initialEnergy > energy(i) .and. initialExperience > experience(i)) then
! Update initial energy and experience
initialEnergy = initialEnergy - energy(i)
initialExperience = initialExperience + experience(i)
! Increment total hours
totalHours = totalHours + 1
else
! Exit loop if current opponent cannot be defeated
exit
end if
end do
! Check if all opponents can be defeated
if (totalHours < minHours) then
minHours = totalHours
end if
! Print result
write (*,*) minHours
end program mainAt line 7 of file temp.f95 (unit = 5, file = 'stdin') Fortran runtime error: End of file Error termination. Backtrace: #0 0x7a3ef21a9960 in ??? #1 0x7a3ef21aa4d9 in ??? #2 0x7a3ef23fe17b in ??? #3 0x7a3ef23f7684 in ??? #4 0x7a3ef23f82aa in ??? #5 0x593602af620d in MAIN__ #6 0x593602af6584 in main
program minTrainingHours
implicit none
integer, parameter :: n = 4
integer, parameter :: initialEnergy = 5
integer, parameter :: initialExperience = 3
integer, parameter :: energy(n) = [1, 4, 3, 2]
integer, parameter :: experience(n) = [2, 6, 3, 1]
integer :: i, j, totalHours, trainingHours
integer :: currentEnergy, currentExperience
! Initialize variables
currentEnergy = initialEnergy
currentExperience = initialExperience
totalHours = 0
! Loop through each opponent
do i = 1, n
! Check if current energy and experience are greater than the opponent's
if (currentEnergy > energy(i) .and. currentExperience > experience(i)) then
! Defeat the opponent
currentEnergy = currentEnergy - energy(i)
currentExperience = currentExperience + experience(i)
totalHours = totalHours + 1
else
! Not enough energy or experience to defeat the opponent
exit
end if
end do
! Check if all opponents were defeated
if (i == n + 1) then
! Return the total hours of training
trainingHours = totalHours
else
! Not all opponents were defeated
trainingHours = -1
end if
! Print the output
write (*,*) trainingHours
end program minTrainingHours
-1
def min_training_hours(initial_energy, initial_experience, energy, experience):
n = len(energy)
ans = int(1e9)
for exp_gain in range(initial_energy + initial_experience + 1):
training_hours = exp_gain
energy_left = initial_energy - exp_gain
curr_experience = initial_experience + exp_gain
for i in range(n):
while curr_experience <= experience[i] or energy_left <= energy[i]:
energy_left -= 1
training_hours += 1
energy_left -= energy[i]
curr_experience += experience[i]
ans = min(ans, training_hours)
return ans
The main idea of the algorithm is to try all possible distributions of gained experience and energy from training hours. For each possible distribution of experience gain (i.e., each number of hours spent on gaining experience), we calculate the corresponding number of hours spent on gaining energy (since we only have two attributes to improve). Then, for each distribution, we simulate the competition and keep track of the minimum number of training hours required.
For each iteration, we simulate the competition by going through each opponent in order. When facing an opponent, if our current experience and energy level are not enough to defeat them (i.e., strictly greater than the opponent's experience and energy level), we spend more hours training on energy by decrementing the amount of energy left and incrementing the training hours.
After simulating the competition for each possible experience gain, we return the minimum training hours needed to defeat all opponents.
The time complexity of the algorithm is O(n^2) as we first iterate through all possible distributions with a maximum number of n, and then for each distribution, we iterate through all the opponents, which is also n. Space complexity is O(1) as we only use constant extra space for storing variables.
#include <vector>
int minTrainingHours(int initialEnergy, int initialExperience, std::vector<int>& energy, std::vector<int>& experience) {
int n = energy.size();
int ans = 1e9;
for (int expGain = 0; expGain <= initialEnergy + initialExperience; ++expGain) {
int trainingHours = expGain;
int energyLeft = initialEnergy - expGain;
int currExperience = initialExperience + expGain;
for (int i = 0; i < n; ++i) {
while (currExperience <= experience[i] || energyLeft <= energy[i]) {
energyLeft--;
trainingHours++;
}
energyLeft -= energy[i];
currExperience += experience[i];
}
ans = std::min(ans, trainingHours);
}
return ans;
}
The main idea of the algorithm is to try all possible distributions of gained experience and energy from training hours. For each possible distribution of experience gain (i.e., each number of hours spent on gaining experience), we calculate the corresponding number of hours spent on gaining energy (since we only have two attributes to improve). Then, for each distribution, we simulate the competition and keep track of the minimum number of training hours required.
For each iteration, we simulate the competition by going through each opponent in order. When facing an opponent, if our current experience and energy level are not enough to defeat them (i.e., strictly greater than the opponent's experience and energy level), we spend more hours training on energy by decrementing the amount of energy left and incrementing the training hours.
After simulating the competition for each possible experience gain, we return the minimum training hours needed to defeat all opponents.
The time complexity of the algorithm is O(n^2) as we first iterate through all possible distributions with a maximum number of n, and then for each distribution, we iterate through all the opponents, which is also n. Space complexity is O(1) as we only use constant extra space for storing variables.