spoj soldier help a soldier

general
, ,
1

problem link SPOJ.com - Problem SOLDIER also on codechef

gor, 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 this 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.

my accepted solution WIygQJ - Online C++0x Compiler & Debugging Tool - Ideone.com or CodeChef: Practical coding for everyone
i doubt the correctness of solution
please explain why is the solution correct, or is it incorrect and test cases were weak

2

some one please answer

3

Hi @ankursmooth

The first impression of the problem was a standard dp (Knapsack type). But then you said it’s greedy still not able to get how a greedy solution will pass because my selection at one stage is dependent on the future.

As for your solution . This test case is giving me wrong answer: (it’s funny you are not even considering price as a variable)

6 4

1 3 1

2 3 2

3 3 1

4 3 3

5 3 3

6 3 2

Your answer : 1

Correct Answer : 0

Reply if I am missing something.

4

http://a2oj.com/Category.jsp?ID=56 at this site i found it in greedy category and yes thats the funny thing that raised my eyes that such solutions are accepted by both sites. i dont know if there is a greedy solution or not.