PROBLEM LINK:
Author: Kaushik N Doddamani
Tester: Kaushik N Doddamani
Editorialist: Kaushik N Doddamani
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Basic Math, Logic, Arrays, Lists, Sorting.
PROBLEM:
MavericK wants to reach location X from Chef’s Laddu Factory.It is not possible to reach location X directly from the Laddu Factory. The travel is divided into N checkpoints. Each checkpoint is associated with 3 parameters for example, the ith checkpoint C_i is associated with the time required to reach that check point T_i, easiness in reaching that checkpoint E_i, Energy required to reach the checkpoint Er_i.
MavericK decides to reach a checkpoint based on a criterion that:
-
Only those checkpoints would be reached first that requires less time, less energy and high ease of reaching.
-
After reaching a particular checkpoint, he decides to go to next checkpoint based on the above-mentioned criteria.
-
No checkpoint would be reached twice.
MavericK clubs all the three parameters into a one single parameter M based on a hypothetical formula as mentioned below: -
M = E_i/(T_i*Er_i)
On basis of this new parameter M, he maps his route of travel satisfying the above criteria. Can you help MavericK by designing a software which could do the task for him?
QUICK EXPLANATION:
Combine all the three parameter values namely, Time, Easiness and Energy into a single parameter called M based on the given hypothetical formula for each checkpoint and store in a list or array or equivalent datatype. Then sort the check point values based on this parameter M and return the corresponding check point number i.e. index of array or list + 1.
EXPLANATION:
We read the first line which contains the total number of checkpoints N.
For the next N lines, we read the values of parameters like, Time, Easiness and Energy. We then combine these 3 parameter values into a single parameter called M, where,
M = E_i/(T_i*Er_i)
The values of M for all the checkpoints is computed and updated in a list. We then sort the list in descending order. Because according the question, only those check points would be covered first which requires less time, less energy and more easiness of travel. Therefore, as the values of M is directly proptional to Easiness, inversely proportional to Time and inversely proportional to Energy, only those checkpoints which has highest value of M would be covered first.
After sorting we then return the indices of the sorted list + 1, because the checkpoint starts from 1 not 0.
ALTERNATE EXPLANATION:
Instead of importing the numpy library one could make use of key parameter of the sorted function, as shown below:
sorted(range(len(s)), key=lambda k: s[k])
SOLUTIONS:
Setter's Solution
import numpy as np
N = int(input())
M = []
for i in range (N):
T, E, Er = input().split()
T, E, Er = float(T), float(E), float(Er)
M.append(E/(T*Er))
m = np.array(M)
sorted_index = list(np.argsort(m))
sorted_index.reverse()
for i in range(len(sorted_index)):
print(sorted_index[i],end=' ')
Suggestions are always welcomed