SOLDIER - Help the soldier
Igor, a famous Russian soldier, must go to war in Afghanistan (we are in late 80’s). His superiors allowed him to buy himself his equipment. So, he must buy 6 items: helmet, bulletproof vest, trousers, boots, tunic and a firearm. This items are represented with numbers from 1 to 6. There are N (6 < N < 101) items of these 6 types. Each item is characterized by its price p[i] (in rublas) and is quality q[i]. Igor has T (0 < T < 1001) rublas and he wants to maximize the total quality of his equipment. The total quality is the quality of the item with the lowest quality. Help him.
Input
On the first line there are two integers N and T. On the lines 2 ... N+1 there are 3 integers, type[i] (from 1 to 6) p[i] and q[i]. (0 < p[i], q[i] < T )
Output
Output the total quality.
Example
Input: 7 53 5 8 2 2 4 8 6 8 13 1 13 12 4 5 1 3 2 7 3 13 5 Output: 1
Note
If there is no answer, output 0.
There can be less than 6 types of items.
[ Edited by EB ]
Warning: Some input files are incomplete and broken.
hide comments
|
zicowa:
2014-06-27 09:48:36
i request to the setter do not add such problems which include this much ambiguity it is quite difficult to solve such problem and even if there exists ambiguity then either correct it or mention it in comments thanx:P
|
|
|
zicowa:
2014-06-27 09:46:49
and here is something about the problem that it essentially asked you to find the minimum quality when item of each type are considered it means it is neccessary that each type of item must be include and then find the minimum . |
|
|
zicowa:
2014-06-27 09:45:17
hey i get to know either the test data for this problem is wrong or week here is a proof one submitted solution is giving this 10 for this test case but actual answer is 0 youu can verify your own.
|
|
|
zicowa:
2014-06-27 07:26:08
i think constraints allowed me to apply dp with a upperbound of O(n*(tmax)) O(10^5) |
|
|
zicowa:
2014-06-27 07:24:40
I first thought to apply greedy but that is failing my own test case and i thought of applying DP which i think is sufficient to solve this problem but i dont know why i am getting WA any critical test case any one of you may have ?? |
|
|
zicowa:
2014-06-27 06:54:26
as one said question is incomplete i too feel this .it is not mentioned in the problem whether it is neccessay to buy items of each and every type if this is the case then for all the cases in which items are of less than 6 types answer is simply zero .so, please do mention such kinds of things in the statement itself!! |
|
paras meena:
2014-05-28 19:12:28
Simple Greedy No need to DP |
|
SHOBHIT SAXENA:
2014-04-17 19:57:06
Input test cases contain invalid items numbers. <1 or >6
|
|
Daniel Barboza Franco:
2014-03-18 04:20:27
There is something strange with the input. Be careful with the method you are using to parse/split the input. For those using Java, Scanner will do the job. Last edit: 2014-03-18 04:21:04 |
|
Rishav Goyal:
2014-02-18 10:13:52
@problem setter : problem is incomplete in itself!!!
|
| Added by: | Pripoae Toni |
| Date: | 2008-09-14 |
| Time limit: | 0.109s |
| Source limit: | 2048B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
| Resource: | Original |
RSS