Sherlock and Prince of Persia
All submissions for this problem are available.
Sherlock is playing Prince of Persia where there are N levels. Each level requires certain amount of time to finish. Every level is also characterised by two other parameters XP_needed and XP_gain. The time units need to finish, minimum experience needed and experience gain of the i-th level is given by T[ i ] , XP_needed[ i ] and XP_gain[ i ], respectively. Sherlock can play the i-th level if his current XP is greater than or equal to XP_needed[ i ]. Once he finishes the i-th level his XP will increase by XP_gain[ i ]. Sherlock is busy working on a case and he has X time units to spare. His initial XP is Y. He wants to complete as many levels as possible within the time. Help him find out the maximum number of levels he can play and the minimum XP that he would have required to finish that many levels within X units of time. (XP cannot be negative)
- First line contains three space separated integers N, X and Y.
- Next N lines contains three space separated integers. The (i+1)th line contains the description of the i-th level - XP_needed[ i ], T[ i ] and XP_gain[ i ].
Print two space separated integers - The maximum number of levels Sherlock can attend and the minimum XP he would have needed to finish these levels.
- 1 ≤ N ≤ 100
- 0 ≤ T[i] ≤ X ≤ 10000
- 0 ≤ XP_needed[ i ], XP_gain[ i ], Y ≤ 10^7
Input: 4 13 6 6 11 2 5 10 1 8 1 2 8 1 2
Output: 3 6
Sherlock will complete three levels:
one of the possible order is :
He needs at least 6 Xp to complete three levels.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.