CATWOMANS EARLY DAYS
All submissions for this problem are available.
Catwoman in her early days started off with stealing from super-markets before she became a master thief. Being the intelligent thief she is, she stakes the super-market out and plans her robbery beforehand. She makes a list of worthwile things to steal - their weight, cost and whether the item can be divided into smaller parts of any weight(such as rice, oil) or can not be divided into parts(such as spoons,tumblers). She can only transport a maximum weight of W. Given this list and the maximum weight can u figure out what is the maximum total cost of stolen goods she can steal?
The first line of input contains the number of test cases T(1<=T<=100). T test cases follow.
The first line of every test case consists of two integers - N(1<=N<=50) and W(1<=W<=10000).
The next N lines are formatted as followed:
The ith line contains 2 integers and a character separated by a single space between them - weight[i], cost[i] and ch[i]
weight[i] - weight of the ith item. (1<=weight[i]<=10000)
cost[i] - cost of the ith item. (1<=cost[i]<=10000)
ch[i] - 'Y' if the item can be divided or 'N' if the item cannot be divided.
Note: For divisible items, assume that cost of the item is directly proportional to its weight.
For each test case, output a single line consisting of a single number - the maximum total cost of stolen goods possible. The value must have a relative or absolute error less the 1e-6.
1 1 N
1 1 Y
10 1 Y
100 1 Y
150 10 Y
200 1 N
50 100 N
100 45 Y
200 1000 N
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP 6.3, CPP14, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.